a backtracking algoritmus felsorolja a részleges jelöltek halmazát, amelyeket elvileg különféle módon lehet kitölteni, hogy az adott problémára minden lehetséges megoldást megadjanak. A Befejezés fokozatosan történik, a jelölt kiterjesztési lépések sorozatával.
fogalmilag a részleges jelölteket egy faszerkezet csomópontjaiként, a potenciális Keresési faként ábrázoljuk. Minden részleges jelölt azoknak a jelölteknek a szülője, amelyek egyetlen kiterjesztési lépéssel különböznek tőle; a fa levelei azok a részleges jelöltek, amelyeket nem lehet tovább kiterjeszteni.
a visszalépési algoritmus rekurzív módon, a gyökértől lefelé, mélység-elsőrendű sorrendben halad át ezen a keresési fán. Minden csomópontnál c, az algoritmus ellenőrzi, hogy C teljesíthető-e érvényes megoldásra. Ha nem, akkor a C-nél gyökerező teljes alfa kihagyásra kerül (metszésre kerül). Ellenkező esetben az algoritmus (1) ellenőrzi, hogy maga a c érvényes megoldás-e, és ha igen, jelentést tesz a felhasználónak; és (2) rekurzív módon felsorolja a c összes alfáját. a két tesztet és az egyes csomópontok gyermekeit a felhasználó által megadott eljárások határozzák meg.
ezért az algoritmus által áthaladó tényleges keresési fa csak egy része a potenciális fának. Az algoritmus teljes költsége a tényleges fa csomópontjainak száma, szorozva az egyes csomópontok megszerzésének és feldolgozásának költségével. Ezt a tényt figyelembe kell venni a potenciális keresési fa kiválasztásakor és a metszési teszt végrehajtásakor.
PseudocodeEdit
a visszalépés egy adott problémaosztályra való alkalmazásához meg kell adni a megoldandó probléma adott példányának p adatait, és hat eljárási paramétert: gyökér, Elutasít, Elfogad, első, Következő és kimenet. Ezeknek az eljárásoknak a P példány adatait kell paraméterként figyelembe venniük, és a következőket kell tenniük:
- gyökér (P): visszaadja a részleges jelöltet a keresési fa gyökerében.
- elutasítás(P,c): true érték csak akkor tér vissza, ha a C részjelöltet nem érdemes kitölteni.
- elfogadom(P,c): visszaadja a true értéket, ha c A P megoldása, ellenkező esetben false.
- első(P,c): A C jelölt első kiterjesztésének generálása.
- következő(P,s): a jelölt következő alternatív kiterjesztésének generálása az s kiterjesztés után.
- kimenet(P, c): az alkalmazásnak megfelelően használja a P c megoldását.
a visszalépési algoritmus csökkenti a problémát a hívás visszalépésére (root(P)), ahol a visszalépés a következő rekurzív eljárás:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
usage considerationsEdit
az elutasítási eljárásnak logikai értékű függvénynek kell lennie, amely csak akkor tér vissza igazra, ha biztos abban, hogy a c lehetséges kiterjesztése nem érvényes megoldás P-re. A helytelen valódi eredmény miatt a bt eljárás elmulaszthat néhány érvényes megoldást. Az eljárás feltételezheti, hogy az elutasítás (P,t) HAMIS értéket adott vissza a keresési fa minden ősére t nak, – nek c.
másrészt a visszalépési algoritmus hatékonysága attól függ Elutasít visszatérő igaz azokra a jelöltekre, amelyek a lehető legközelebb vannak a gyökérhez. Ha az elutasítás mindig hamis értéket ad vissza, az algoritmus továbbra is megtalálja az összes megoldást, de egyenértékű lesz a brute-force kereséssel.
az accept eljárásnak true értéket kell adnia, ha a c teljes és érvényes megoldás a P problémapéldányra, ellenkező esetben false. Feltételezhetjük, hogy a részleges C jelölt és a fában lévő összes őse átment a visszautasítási teszten.
a fenti általános álkód nem feltételezi, hogy az érvényes megoldások mindig a potenciális keresési fa levelei. Más szavakkal, elismeri annak lehetőségét, hogy a P érvényes megoldása tovább bővíthető más érvényes megoldások előállításához.
az első és a következő eljárást a backtracking algoritmus használja a fa C csomópontjának gyermekeinek felsorolására, vagyis azokra a jelöltekre, amelyek egyetlen kiterjesztési lépéssel különböznek a c-től. Az első hívás (P, c) valamilyen sorrendben adja meg a c első gyermekét; a következő(P,s) hívásnak vissza kell adnia az s csomópont következő testvérét, ebben a sorrendben. Mindkét funkciónak vissza kell adnia egy megkülönböztető “NULL” jelöltet, ha a kért gyermek nem létezik.
a gyökér, az első és a következő függvények együttesen határozzák meg a részleges jelöltek halmazát és a potenciális Keresési fát. Úgy kell megválasztani őket, hogy minden P megoldás valahol a fában történjen, és egyetlen részleges jelölt sem fordul elő egynél többször. Ezenkívül be kell vallaniuk egy hatékony és eredményes elutasító állítmányt.
korai leállítás variantsEdit
a pszeudo-kód fenti hívja kimenet minden jelölt, amely a megoldás, hogy az adott példány P. az algoritmus lehet módosítani, hogy hagyja abba megtalálása után az első megoldás, vagy egy meghatározott számú megoldás; vagy tesztelése után egy meghatározott számú részleges jelöltek, vagy miután eltöltött egy adott mennyiségű CPU időt.