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 |