NézetNyomtat

7. óra
Címkék > Óra

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ésd[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            // van még remény
akkor
    d[i] := d[i] + 1    // adott szinten a következő döntés
    Ciklus amíg rossz(i) és d[i] még növelhető
        d[i] := d[i] + 1
    Ciklus vége
    Ha nem rossz(i)     // az i. szinten volt jó döntés
    akkor
        Ha megoldást találtunk
        akkor
            a megoldás kiírás/tárolása
        különben
            bt(i+1) // megyünk tovább a következő szintre
        Elágazás vége
    különben
        d[i] := 0
        bt(i-1)     // visszalépünk az előző döntési szintre
    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    // adott szinten a következő döntés
        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