SHPORA.net :: PDA

[ Back ]

Ammendav otsing (variantide läbivaatus)

Teatud ülesannete korral on ainsaks täpseks lahendusmeetodiks "proovimise meetod", s.t. kõigi võimalike lahendusvariantide süstemaatiline läbivaatus (ammendav otsing). Kuna lõplikul n-elemendilisel hulgal on 2^n alamhulka, siis on ammendava otsingu ülesanne üldjuhtumil eksponentsiaalse keerukusega. Konkreetset keerukust saab teatud juhtudel vähendada otsinguruumi ahendamisega.

Kaht liiki ülesanded:

* esimese sobiva lahendi leidmine

* kõigi lahendite leidmine

Variandigeneraator - funktsioon lahendusvariantide süstemaatiliseks genereerimiseks.

Tagasivõtt, backtracking: uue variandi valik antud tasemel, kui kõik alamjuhtumid on ammendatud.



Näide. 8 lippu - kõigi lahendite leidmine.

Paigutada malelauale 8 lippu nii, et ükski neist ei oleks mõne teise lipu tules.













Idee: paigutada lippe järjekorras "vasakult paremale" nii, et n-nda lipu jaoks otsitakse kohta olukorras, kus eelnevad n-1 lippu on nõuetekohaselt paigutatud. Kui sobivat kohta n-ndas veerus ei leidu, siis vähendada n väärtust (backtracking) ning leida järgmine sobiv paigutus "eelmisele" lipule.



Kujutame malelaua seisu ühemõõtmelise massiivina laud, mille iga element kodeerib ühe malelaua veeru järgmiselt:

laud[j]=0 - veerus j ei ole lippu paigutatud

laud[j]=i - veerus j paikneb lipp i-ndas reas (1 <= i <= 8)



Predikaat onTules(n) : kas lipp number n on mõne eelneva lipu tules (samal real või diagonaalil, samas veerus ei saa olla juba seisu kujutusviisi tõttu).