Backtracking

Zpětná stopa funguje na principu hloubkového prvního vyhledávání

Pojem resetovací procedura nebo backtracking popisuje metodu řešení problému v rámci algoritmů .

Obecný algoritmus

Backtracking je založen na principu pokusů a omylů , což znamená, že je učiněn pokus vyvinout dílčí řešení do celkového řešení. Pokud lze předvídat, že částečné řešení nemůže vést ke konečnému řešení, provede se poslední krok nebo poslední kroky a místo toho se vyzkouší alternativní přístupy. Tím je zajištěno, že lze vyzkoušet všechna možná řešení (princip vlákna Ariadne ). S algoritmy zpětného sledování je buď nalezeno existující řešení (pravděpodobně po velmi dlouhém běhu), nebo lze definitivně konstatovat, že žádné řešení neexistuje. Backtracking je obvykle nejsnadnější implementovat rekurzivně a jedná se o typický případ použití rekurze.

Funktion FindeLösung (Stufe, Vektor)
  1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist:
               I) erweitere Vektor um Wahl;
              II) falls Vektor vollständig ist, return true; // Lösung gefunden!
                  sonst:
                       falls (FindeLösung(Stufe+1, Vektor)) return true; // Lösung!
                       sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!

Časová složitost

V případě hledání první hloubky se uzly rozšíří z každého dílčího řešení a strom řešení s maximální hloubkou, v nejhorším případě uzly s maximální možnou větví . ${\ displaystyle z}$ ${\ displaystyle N}$ ${\ displaystyle 1 + z + z ^ {2} + z ^ {3} + \ dotsb + z ^ {N}}$

Pátrání do hloubky, a tedy i ustupování mají k exponenciálnímu dobu běhu v nejhorším případě se a jedním stupněm větvení . Čím větší je hloubka hledání , tím déle bude trvat nalezení řešení. Proto je zpětné sledování primárně vhodné pro problémy s malým stromem řešení. ${\ displaystyle O (z ^ {N})}$ ${\ displaystyle z> 1}$ ${\ displaystyle n}$

Existují však metody, pomocí kterých lze snížit časovou složitost algoritmu zpětného sledování. Mezi ně patří mimo jiné:

Heuristika
Přijetí přibližných řešení a odolnost proti chybám
Průměrné vstupní množství

Příklady

Mezi známé problémy, které lze vyřešit pomocí zpětného sledování, patří:

Dámský problém: Řešení problému žen pomocí zpětného sledování

K dispozici je šachovnice s poli (každý sloupec a řádek). Nyní postavte ženy tak, aby se nemohly navzájem bít. Dámský problém patří do třídy problémů s uspokojením omezení . ${\ displaystyle n \ krát n}$ ${\ displaystyle n}$ ${\ displaystyle N}$

Problém s propojkou: Dána je šachovnice s čtverci. Skokan může mít různé skoky z určité polohy , pokud tyto nepovedou přes okraj desky. Hledáme cestu, ve které jsou všechna pole navštěvována přesně jednou (Springerweg). Pomocí zpětného sledování lze systematicky vyzkoušet všechny možné cesty. Tah je platný, pokud je nové pole v hracím poli a ještě není navštíveno. Existují však mnohem efektivnější metody řešení tohoto problému. ${\ displaystyle m \ krát n}$ ${\ displaystyle N = 8}$

Problém s batohem: Batoh s kapacitou je uveden . Dále jsou objektům dány hodnoty a váhy. Nyní by měly být vybrány objekty, které se zvyšují na maximální hodnotu, ale jejichž celková hmotnost nepřesahuje nosnost batohu. ${\ displaystyle B}$ ${\ displaystyle N}$

Problém s barvením: Je uvedena mapa se zeměmi, které by měly být vybarveny různými barvami. Hledáme barevnou kombinaci, ve které jsou všechny země, které mají společnou hranici, barevně odlišeny. ${\ displaystyle B}$ ${\ displaystyle N}$

Desková hra solitaire: Na začátku je na desce 32 kamenů (pera nebo koule); jeden z nich je odstraněn v 31 tazích skokem přes něj jiným kamenem.

Sudoku: Čísla od 1 do 9 by měla být zadána do pole (rozděleného do devíti polí) podle určitých pravidel . ${\ displaystyle 9 \ krát 9}$ ${\ displaystyle 3 \ krát 3}$

Str8ts: Čísla od 1 do 9 by měla být zadána do pole podle určitých pravidel . Tento typ skládačky lze také dobře vyřešit pomocí zpětného sledování. ${\ displaystyle 9 \ krát 9}$

Hledejte z bodu A do bodu B v grafu: Zpětná stopa se také používá k hledání trasy z bodu A do bodu B v grafu, například k vyhledání spojení v jízdním řádu nebo k určení trasy v plánovači tras nebo trase bludištěm .

Mnoho z těchto problémů je NP-úplné .

prolog

Programovací jazyk Prolog využívá ustupování ke generování odpovědí. Tlumočník po sobě zkouší všechny možné důkazy. Rozhodovací body se označují jako výběrové body . K !vyřazení vybraných bodů lze použít takzvaný operátor řezu .

literatura

Robert Sedgewick : Algoritmy. 2. vydání. Addison-Wesley, Mnichov 2002, ISBN 3-8273-7032-9 .
Niklaus Wirth : Algoritmy a datové struktury. 3. přepracované vydání. Teubner, Stuttgart 1983, ISBN 3-519-02250-8 .

webové odkazy

Commons : Backtracking - sbírka obrázků, videí a zvukových souborů

Interaktivní kurz zpětného sledování projektu Math Prism na University of Wuppertal

Languages