V tomto tutoriálu se dozvíte, co je algoritmus zpětného sledování. Najdete také příklad přístupu zpětného sledování.
Zpětný sledovací algoritmus je algoritmus pro řešení problémů, který k nalezení požadovaného výstupu používá přístup hrubou silou .
Přístup hrubou silou zkouší všechna možná řešení a vybírá požadovaná / nejlepší řešení.
Termín backtracking naznačuje, že pokud současné řešení není vhodné, pak ustupte a vyzkoušejte jiná řešení. V tomto přístupu se tedy používá rekurze.
Tento přístup se používá k řešení problémů, které mají více řešení. Pokud chcete optimální řešení, musíte jít na dynamické programování.
Státní vesmírný strom
Strom stavu prostoru je strom představující všechny možné stavy (řešení nebo neřešení) problému od kořene jako počátečního stavu po list jako koncového stavu.
Státní vesmírný strom
Algoritmus zpětného sledování
Backtrack (x), pokud x není řešením, návrat false, pokud x je nové řešení, přidat do seznamu řešení backtrack (rozbalit x)
Příklad přístupu zpětného sledování
Problém: Chcete najít všechny možné způsoby uspořádání 2 chlapců a 1 dívky na 3 lavičkách. Omezení: Dívka by neměla být na střední lavici.
Řešení: Existují celkem 3! = 6 možností. Vyzkoušíme všechny možnosti a získáme možná řešení. Rekurzivně vyzkoušíme všechny možnosti.
Všechny možnosti jsou:
Všechny možnosti
Následující strom stavového prostoru ukazuje možná řešení.
Stavový strom se všemi řešeními
Backtracking Algorithm Applications
- Najít všechny Hamiltonovské cesty v grafu.
- Vyřešit problém N Queen.
- Řešení problému s bludištěm.
- Rytířský problém s turné.
