Backtracking

backtracking algoritmus vyjmenovává řadu dílčích kandidátů, které v zásadě, by mohl být dokončen v různých způsobů, jak dát všechny možné řešení daného problému. Dokončení se provádí postupně, posloupností kandidátských kroků rozšíření.

koncepčně jsou dílčí kandidáti reprezentováni jako uzly stromové struktury, potenciální vyhledávací strom. Každý částečný kandidát je rodičem kandidátů, kteří se od něj liší jediným krokem rozšíření; listy stromu jsou dílčími kandidáty, které nelze dále rozšiřovat.

backtracking algoritmus prochází tento vyhledávací strom rekurzivně od kořene dolů, do hloubky-první pořadí. V každém uzlu c algoritmus kontroluje, zda lze C doplnit na platné řešení. Pokud to nemůže, celý sub-strom zakořeněný v c je přeskočen(prořezán). V opačném případě algoritmus (1) zkontroluje, zda c sám o sobě je platné řešení, a pokud se tak přenáší ji na uživatele; a (2) rekurzivně vytvoří výčet všech sub-stromy c. Dva testy a děti každého uzlu jsou definovány uživatelem-dané postupy.

skutečný vyhledávací strom, který prochází algoritmem, je tedy pouze částí potenciálního stromu. Celková cena algoritmu je počet uzlů skutečného stromu krát náklady na získání a zpracování každého uzlu. Tuto skutečnost je třeba vzít v úvahu při výběru potenciálního vyhledávacího stromu a provádění testu prořezávání.

PseudocodeEdit

aby bylo možné použít backtracking do určité třídy problémů, musí poskytnout údaje P pro konkrétní instanci problému, který je třeba řešit, a šest procesních parametrů, kořen, odmítnout, přijmout, první, další, a výstup. Tyto postupy by měly brát data instance P jako parametr a měly by provádět následující:

1. root (P): vraťte částečného kandidáta do kořenového adresáře vyhledávacího stromu.
2. reject (P, c): return true pouze v případě, že částečný kandidát c nestojí za dokončení.
3. přijmout (P, c): návrat true, Pokud c je řešení P, a false jinak.
4. first(P,c): vytvářet první rozšíření kandidát c.
5. next(P,s): generovat další alternativní rozšíření kandidáta, po rozšíření s.
6. output(P,c): použijte roztok c P, jako vhodné k aplikaci.

backtracking algoritmus redukuje problém na výzvu backtrack(root(P)), kde backtrack je následující rekurzivní procedura:

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)

Použití considerationsEdit

odmítnout postup by měl být booleovské funkce, která vrací true pouze tehdy, pokud je jisté, že není možné rozšíření c je platné řešení pro P. v Případě, že postup nelze dosáhnout jednoznačného závěru, že by se měla vrátit hodnotu false. Nesprávný skutečný výsledek může způsobit, že procedura bt vynechá některá platná řešení. Postup může předpokládat, že reject (P,t) vrátil false pro každého předka t c ve vyhledávacím stromu.

na druhé straně účinnost algoritmu zpětného sledování závisí na odmítnutí návratu true pro kandidáty, kteří jsou co nejblíže kořenu. Pokud odmítnutí vždy vrátí false, algoritmus stále najde všechna řešení, ale bude ekvivalentní hledání hrubou silou.

přijmout postup by měl vrátit true pokud c je kompletní a platné řešení problému instance P, a false jinak. Může předpokládat, že částečný kandidát c a všichni jeho předci ve stromu prošli testem odmítnutí.

obecný pseudokód výše nepředpokládá, že platná řešení jsou vždy listy potenciálního vyhledávacího stromu. Jinými slovy, připouští možnost, že platné řešení pro P může být dále rozšířeno, aby poskytlo další platná řešení.

první a další postupy jsou používány backtracking algoritmus výčet děti uzlu c stromu, to znamená, že kandidáti, které se liší od c pomocí jediného prodloužení kroku. První volání (P, c)by mělo přinést první dítě c, v určitém pořadí; a volání další (P, s) by mělo vrátit dalšího sourozence uzlu s v tomto pořadí. Obě funkce by měly vrátit rozlišovací“ NULL “ kandidáta, pokud požadované dítě neexistuje.

společně funkce root, first a next definují množinu dílčích kandidátů a potenciální vyhledávací strom. Měly by být vybrány tak, aby se každé řešení P vyskytlo někde ve stromu a žádný částečný kandidát se nevyskytuje více než jednou. Kromě toho by měli připustit účinný a účinný predikát odmítnutí.

Předčasné ukončení variantsEdit

pseudo-kódu výše bude volat výstup pro všechny kandidáty, které jsou řešením dané instance P. algoritmus může být upraven tak, aby zastavit po nalezení prvního řešení, nebo zadaný počet řešení; nebo po testování zadaný počet částečných kandidátů, nebo po strávení dané množství času PROCESORU.