Programozás‎ > ‎

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é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]
11
211
312
42
521
63
731
832
9321
10322
11323


Egy megoldás keresése

Rekurzív változat

A következő algoritmus váz abban az esetben használható, ha tudjuk, hogy van legalább egy megoldás, és elég az első megoldást megtalálnunk. Szépséghibája, hogy a megoldás megtalálásakor a rekurzió "legmélyén" vagyunk, és ekkor meg kell szakítanunk a rekurzió futását, hogy a megtalált megoldást ne "bontsák le" a visszalépések.

rek_backtrack:

Ha nincs kész 
akkor
    Ciklus a lehetséges lépéseken
        megcsinál( lehetséges lépés )
        rek_backtrack
        visszacsinál( lehetséges lépés) 
    Ciklus vége 
különben
    megoldás feldolgozása
    keresés vége
Elágazás vége

A "megcsinál / visszacsinál" hívások akkor szükségesek, ha az adott állapotot nem tudjuk (vagy nem akarjuk) érték szerinti paraméterként átadni a rekurzív eljárásnak. Ez előfordulhat, például ha sok memória kell az állapot leírásához, és nagy lehet a rekurzió mélysége, vagy akkor, ha a használt nyelv nem támogatja az érték szerinti paraméterátadást. Ilyenkor egy globális adatszerkezetben tárolhatjuk az aktuális keresési állapotot, és a "megcsinál / visszacsinál" hívások ezt a globális adatszerkezetet módosítják.

Ciklusos változat

A rekurzió kiküszöbölhető, ha a valamilyen adatszerkezetben tároljuk eddigi döntéseinket. A d[i] tömb eleme azt tárolja, hogy az i. lépésben "merre mentünk". A vanjóeset() függvény egyesével végigpróbálja a lehetséges döntéseket, és ha igaz értékkel tér vissza, akkor be is állítja a d[i] értéket.

cikl_backtrack:

d[1..n] := 0; i := 1
Ciklus amíg i > 0 és i < N + 1
    Ha vanjóeset(i)
    akkor 
        i := i + 1
    különben
        d[i] := 0
        i := i - 1
    Elágazás vége
Ciklus vége 
VAN := (i > N)

Ha egy adott szinten mindig azonos számú (pl. MAX számú) lépés lehetséges, akkor a vanjóeset() függvény kifejtése a következő lehet:


d[1..n] := 0; i := 1
Ciklus amíg i > 0 és i < N + 1
    Ciklus
        d[i] := d[i] + 1
    amíg d[i] <= MAX és rossz(i)
    Ha d[i] <= MAX
    akkor 
        i := i + 1
    különben
        d[i] := 0
        i := i - 1
    Elágazás vége
Ciklus vége 
VAN := (i > N)

Összes megoldás keresése

Rekurzív változat

kezdetben d[] := 0

Eljárás bt(i) 
    Ha megoldás(i) akkor
        megoldás tárolása vagy 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)

Ciklusos változat


d[1..n] := 0; i := 1; DB := 0
Ciklus amíg i > 0 
    Ciklus
        d[i] := d[i] + 1
    amíg d[i] <= MAX és rossz(i)
    Ha d[i] <= MAX
    akkor
        Ha i = N // megoldás
        akkor
            DB := DB + 1
            megoldás tárolása vagy kiírása
            d[i] := 0    // megyünk tovább 
            i := i - 1
        különben
            i := i + 1
        Elágazás vége
    különben
        d[i] := 0
        i := i - 1
    Elágazás vége
Ciklus vége