7. óra
Visszalépéses keresés
A visszalépéses keresés egy olyan általános algoritmus, amivel (elméletileg) minden programozási feladat megoldható. A gyakorlatban sok esetben nem elég gyors, átlagosan exponenciális lépésszámú, tehát "csodafegyvernek" nem kell gondolni. Jól használható "kis" bemenetek esetén, illetve akkor, ha a megoldandó feladatról van olyan többlettudásunk, amivel lényegesen csökkenthető a futási idő. Ez általában azt jelenti, hogy a keresés bizonyos "ágait" nem kell bejárni.
A visszalépéses kereséssel már foglalkoztunk egy
korábbi szakkörön, most kicsit alaposabban megvizsgáljuk.
Egymás utáni döntések sorozata
A visszalépéses keresés algoritmusa akkor használható, ha a problémát meg tudjuk fogalmazni egymás utáni döntések sorozataként. Az, hogy egy adott állapotban hányfelé léphetünk tovább, függhet a korábbi döntésektől. A lehetőségeket egy döntési fán ábrázolhatjuk:
Az i. döntés értékét (vagyis azt, hogy a lehetőségek közül hányadikat választottuk) jelölje d[i].
A fenti ábrán a hupikék állapot megtalálása a következő lépésekben történt:
| Lépés | d[1] | d[2] | d[3] |
| 1 | 1 | | |
| 2 | 1 | 1 | |
| 3 | 1 | 2 | |
| 4 | 2 | | |
| 5 | 2 | 1 | |
| 6 | 3 | | |
| 7 | 3 | 1 | |
| 8 | 3 | 2 | |
| 9 | 3 | 2 | 1 |
| 10 | 3 | 2 | 2 |
| 11 | 3 | 2 | 3 |
Hibás(!) meta-algoritmus
kezdetben d[] := 0
Eljárás bt(i)
Ha i > 0
akkor
d[i] := d[i] + 1
Ciklus amíg rossz(i) és d[i] még növelhető
d[i] := d[i] + 1
Ciklus vége
Ha nem rossz(i)
akkor
Ha megoldást találtunk
akkor
a megoldás kiírás/tárolása
különben
bt(i+1)
Elágazás vége
különben
d[i] := 0
bt(i-1)
Elágazás vége
Elágazás vége
Eljárás vége
megoldás: bt(1)
Javított meta-algoritmus
kezdetben d[] := 0
Eljárás bt(i)
Ha megoldás(i) akkor
megoldás tárolása / kiírása
különben
d[i] := d[i] + 1
Ciklus amíg d[i] <= MAX
Ha jó(i) akkor
d[i+1] := 0
bt( i + 1 )
Elágazás vége
d[i] := d[i] + 1
Ciklus vége
Elágazás vége
Eljárás vége
megoldás: bt(1)
Feladat
