Algoritem za iskanje najdaljšega skupnega podniza

Algoritem za iskanje najdaljšega skupnega podniza

Avtor: Petra Sršen

Učni cilji: Cilj je, uporabniku gradiva nadzorno predstaviti delovanje algoritma.

Kaj je podniz?

Podniz je poljubno zaporedje črk iz nekega niza, ki so v istem relativnem vrstnem redu kot so bile podane v prvotnem nizu.

Poglejmo, koliko podnizov vsebuje niz dolžine n.

  • niz dolžine 1 ima 1 podniz.
  • niz dolžine 2 ima 3 podnize.
  • niz dolžine 3 ima 7 podnizov.

Če imamo podan niz 'abcd', ki je dolžine 4 , so vsi njegovi podnizi:
('a','b','c','d','ab','ac','ad','bc','bd','cd','abc','abd','acd','bcd','abcd'). Vseh podnizov je 15.

S pomočjo teh ugotovitev, lahko zapišemo izraz za izračun podnizov za splošen .

Niz dolžine ima podnizov. Torej za velik , je število podnizov .

Reševanje z uporabo grobe sile

Torej, če bi želeli ugotoviti, kateri je najdaljši skupni podniz nizov in , ki sta dolžin in , pri čemer je potrebno opozoriti, da je dolžina daljšega niza, bi bilo protrebno zgenerirati vse podnize niza (časovna zahtevnost ). Algoritem, ki bi ugotovil, ali je neko podzaporedje tudi podzaporedje v nizu B, bi bil časovne zahtevnosti .


Časovna zahtevnost, za reševanje problema z grobo silo, bi bila .


Tega problema se zato raje lotimo z dinamičnim programiranjem.

Dinamično programiranje

Dinamično programiranje je prva metoda, ki sistematično pregleduje vse možne poti v reševanju problema in zato tudi pride do optimalne rešitve.

V splošnih primerih ne moremo dobiti na tekočem koraku delčke rešitve, vidimo le množico potencinalnih rešitev do konca in potem jih rekonstruiramo. Končna rešitev je sestavljena iz komponent rešitve oziroma iz delnih rešitev. Ko na tekočem koraku ugotovimo, da delna rešitev oziroma komponenta neke rešitve ne vodi h cilju, to delno delno rešitev zavržemo.

Dinamično programiranje temelji na pravilu optimalnosti, saj vsako podzaporedje optimalnega zaporedja je tudi optimalno.

Osnova za dinamično programiranje je rekurzivna enačba, ki se imenuje Bellmanova enačba. Vsak problem rešen s pomočjo metode dinamičnega programiranja ima svojo Bellmanovo enačbo.


http://sl.wikipedia.org/wiki/Dinami%C4%8Dno_programiranje, na dan 02.05.2014

Reševanje problema s pomočjo dinamičnega programiranja

Naš problem je iskanje najdaljšega skupnega podniza nizov in , ki vsebujeta znake in .


Ker glavni problem ni enostavno rešljiv, ga razdelimo na dva dela. V prvem delu bomo zgradili matriko L, ki bo predstavljala dolžine skupnih podnizov.

V drugem delu pa bomo s pomočjo matrike L poiskati najdaljši podniz, ki se bo nahajal tako v kot v .

Rešitev glavnega problema mora biti optimalna. Ker bosta tudi rešitvi podproblemov optimalni, bomo upoštevali pravilo optimalnosti.

Bellmanova enačba

Podana imamo niza in , dolžin in . Niza lahko zapišemo kot in .

Problem iskanja najdaljšega, ne nujno strnjenega, skupnega podniza bomo razdelili na dva dela.


  • V prvem delu zgradimo matriko , s katere lahko preberemo dolžino skupnega podniza za poljubne strnjene podnize, ki obsegajo prvih in prvih znakov nizov in . Člen matrike , pa nam pove dolžino najdaljšega skupnega podniza.
(http://www2.nauk.si/files/655/matrika0_0.png)

Gradnji matrike se bomo podrobno posvetili na eni od naslednjih prosojnic.

V tem delu še ne poznamo odgovora na problem iskanja najdaljšega skupnega podniza.


  • V drugem delu, pa bomo znake nizov in , prepisali v sklada, saj bomo niza pregledovali od konca proti začetku. Tako bomo pregledovali zato, ker je dolžina najdaljšega skupnega podzaporedja enaka vrednosti na poziciji .

Kaj bomo počeli

Podana imamo dva niza, pri katerih iščemo skupne podnize, strnjene in tudi nestrnjene.

niz X: KONKURENCA
niz Y: KOMUTATIVNO

Nekaj skupnih podnizov in najdaljši skupni podniz:


(http://www2.nauk.si/files/655/slika1.png)

Torej:
Poiskali bomo tak najdaljši podniz, ki se nahaja tako v niz1, kot tudi v niz2.

Matrika

Poglejmo si, kako bi najdaljši skupni podniz določili bolj učinkovito in z boljšo časovno zahtevnostjo.
V ta namen bomo najprej zgradili matriko , kjer bomo na tem mestu izračunali dolžino najdaljšega skupnega podniza prvih znakov prvega niza in prvih znakov drugega niza.

Iščemo torej .


Za in velja , . Pri čemer sta in dolžini nizov


Matrika bo dimenzije .


V ničti stolpec in ničto vrstico zapišemo same ničle. To naredimo zato, ker lahko rečemo, da v tej vrstici, stolpcu primerjamo enega od podnizov s praznim nizem, in je njuna skupna dolžina 0.

(http://www2.nauk.si/files/655/matrika2_0.png)

Kako gradimo matriko 1

Oglejmo si sedaj, kako bi zgradili matriko. Gradili jo boma vrstico za vrstico. Poglejmo si, kako določimo , torej kako dolg je najdaljši skupni podniz prvih znakov prvega niza in prvih znakov drugega niza.
Ločimo dve možnosti.
1. Če sta znak prvega in znak drugega niza enaka, je očitno, da bo veljalo:



Poglejmo si zakaj.

Za podana niza in z znaki in velja:

Preden primerjamo in , je dolžina najdaljšega skupnega podniza nizov in enaka 0, saj tak podniz ni obstajal. Zato v primeru, ko sta znaka enaka, dolžino najdaljšega skupnega podniza povečamo za 1.

(http://www2.nauk.si/files/655/matrika1_0.png)

Kako gradimo matriko 2

2. V primeru, ko sta znak prvega niza in znak drugega niza različna, pa bo veljalo:


{}

Končna matrika

Ko nadaljujemo s prej opisanim postopkom, zgradimo končno matriko.

Vidimo torej, da je najdaljši skupni podniz nizov KONKURENCA in KOMUTATIVNO dolžine 4.

Iz matrike lahko razberemo tudi na primer, da imata niza KOMUTAT IN KONKUR, najdaljši skupni podniz dolžine 3.

Torej iz končne matrike lahko razberemo dolžine najdaljših skupnih podnizov, za prvih znakov prvega niza in prvih znakov, drugega niza.


(http://www2.nauk.si/files/655/matrika.png)

Sedaj poznamo dolžino najdaljšega skupnega podniza nizov KONKURENCA in KOMUTATIVNO, ki je 4.


Kako pa sedaj določiti ta podniz?

Uporaba sklada

Za določanje najdaljšega skupnega podniza bomo najprej vsakega od nizov prepisali v svoj sklad, nato pa s pomočjo matrike začeli pregledovanje.
Zakaj?

Pregledovanje bomo začeli od zadaj in elemente tudi odstranjevali, zato bo bolj enostavno, če bomo uporabili sklad.

Uporaba sklada in matrike

Sedaj se bomo lotili iskanje najdaljšega skupnega podniza, ki bo kot smo prebrali iz matrike, dolžine 4.

Smo na koraku, kjer že vemo, da je zadnji element najdaljšega skupnega podniza 'A', iz skladov pa smo do sedaj že izbrisali nekaj elementov.

Poglejmo si, kako bomo nadaljevali.


Primer v filmu

Poglejmo si delovanje algoritma še na primeru nizov 'KJE' in 'KAJ'.


Časovna zahtevnost

Poglejmo si še časovno zahtevnost, ko problem iskanja najdaljšega skupnega podniza, rešujemo s pomočjo dinamičnega programiranja.

Velikost problema je odvisna od vhodnih podatkov. To sta niz1 in niz2. Pri čemer določimo, da ima niz1 dolžino n in niz2 dolžino m.

Časovno zahtevnost določimo z gradnjo matrike. Matriko gradimo s pomočjo dveh zank, ena od zank teče po vrsticah, druga pa po stolpcih. Število vrstic je toliko, kolikor je dolžina niza niz1, torej n, število stolpcev pa je odvisna od dolžine niza niz2, torej m.

Časovna zahtevnost je zato

Kviz1

Gradimo matriko, določi vrednost za a.


(http://www2.nauk.si/files/655/k1.png)


Odgovor je pravilen!

Zaključi

Odgovor je napačen!Poizkusi ponovno.

Ponovi

Kviz 2

Kakšna je časovna zahtevnost, če bi se iskanja najdaljšega skupnega podniza lotili z grobo silo? Karakteristični operaciji sta generiranje podnizov ter primerjanje. Velikost problema pa je odvisna od dolžine podanih nizov, ki sta n in m.



Odgovor je pravilen!

Zaključi

Odgovor je napačen!Poizkusi ponovno.

Ponovi

Kviz 3

Kateri formuli uporabimo pri generiranju matrike?



Zaključi

Odgovor je pravilen!

Zaključi

Odgovor je napačen!Poizkusi ponovno.

Ponovi

Kviz 4

Katera od podanih matrik je pravilno zgrajena, za niza 'DACD' in 'ADDA' ?


(http://www2.nauk.si/files/655/k4.png)
(http://www2.nauk.si/files/655/k3.png)
(http://www2.nauk.si/files/655/k2.png)

Odgovor je pravilen!

Zaključi

Odgovor je napačen!Poizkusi ponovno.

Ponovi

Kviz 5

Od česa je odvisna časovna zahtevnost, ko se lotimo reševanja problema iskanja najdaljšega skupnega podniza, s pomočjo dinamičnega programiranja?



Zaključi

Odgovor je pravilen!

Zaključi

Odgovor je napačen!Poizkusi ponovno.

Ponovi

Viri

0%
0%