V tomto tutoriáli sa dozviete, čo je algoritmus spätného sledovania. Nájdete tiež príklad prístupu späť.
Algoritmus spätného sledovania je algoritmus na riešenie problémov, ktorý na nájdenie požadovaného výstupu používa prístup hrubou silou .
Prístup brutálnej sily vyskúša všetky možné riešenia a zvolí požadované / najlepšie riešenia.
Termín backtracking naznačuje, že ak súčasné riešenie nie je vhodné, urobte backtrack a vyskúšajte iné riešenia. V tomto prístupe sa teda používa rekurzia.
Tento prístup sa používa na riešenie problémov, ktoré majú viac riešení. Ak chcete optimálne riešenie, musíte ísť na dynamické programovanie.
Štátny vesmírny strom
Strom stavu priestoru je strom predstavujúci všetky možné stavy (riešenie alebo neriešenie) problému od koreňa ako počiatočného stavu po list ako terminálny stav.
Štátny vesmírny strom
Algoritmus spätného sledovania
Backtrack (x) ak x nie je riešením return false ak x je nové riešenie pridať do zoznamu riešení backtrack (rozbaliť x)
Príklad prístupu späť
Problém: Chcete nájsť všetky možné spôsoby usporiadania 2 chlapcov a 1 dievčaťa na 3 lavičkách. Obmedzenie: Dievča by nemalo byť na strednej lavici.
Riešenie: Existujú celkom 3! = 6 možností. Vyskúšame všetky možnosti a získame možné riešenia. Rekurzívne skúšame všetky možnosti.
Všetky možnosti sú:
Všetky možnosti
Nasledujúci strom stavového priestoru zobrazuje možné riešenia.
Stavový strom so všetkými riešeniami
Aplikácie algoritmu spätného sledovania
- Nájsť všetky Hamiltonovské cesty v grafe.
- Vyriešiť problém N Queen.
- Riešenie problému s bludiskom.
- Problém s rytierskym turné.
