Backtracking search , backtracking je obecná metoda pro nalezení řešení problému, který vyžaduje úplný výčet všech možných možností v určité množině M. Zpravidla umožňuje řešit problémy, které kladou otázky typu: „Vypsat všechny možné možnosti . ..“ , „Kolik způsobů ...“, „Existuje způsob ...“, „Existuje objekt ...“, atd.
Termín backtracking byl vytvořen v roce 1950 americkým matematikem Derrickem Henrym Lehmerem .
Drobné modifikace metody backtracking související s reprezentací dat nebo implementačními prvky mají jiné názvy: metoda větvení a vazby , hloubkové vyhledávání , metoda pokusu a omylu atd. Vyhledávání zpětného sledování bylo vynalezeno mnoha výzkumníky téměř současně a nezávisle ještě před jeho formálním popisem.
Řešení problému metodou backtracking je redukováno na postupné rozšiřování dílčího řešení. Pokud v dalším kroku takové rozšíření selže, vrátí se ke kratšímu dílčímu řešení a pokračují v hledání dále. Tento algoritmus vám umožňuje najít všechna řešení problému, pokud existují. Pro urychlení metody se snaží organizovat výpočty tak, aby co nejdříve identifikovali zjevně nevhodné možnosti. Často to může výrazně zkrátit čas na nalezení řešení.
Klasickým příkladem použití backtrackingového algoritmu je problém osmi královen . Jeho znění je následující: „Na standardní 64-buňkové šachovnici rozmístěte 8 dam tak, aby žádná z nich nebyla napadena jinou.“ Nejprve se na šachovnici položí jedna dáma a poté se snaží umístit každou další dámu tak, aby ji neporazily již usazené dámy. Pokud v dalším kroku nelze takové nastavení provést, vrátí se o krok zpět a pokusí se umístit dříve nainstalovanou královnu na jiné místo.
Metoda backtracking navíc umožňuje vyřešit mnoho dalších problémů s výčtem. Například pomocí něj můžete získat všechny podmnožiny , umístění , permutace , kombinace dané množiny M.
Metoda backtrackingu je obecná. Je poměrně snadné navrhnout a naprogramovat algoritmy pro řešení problémů pomocí této metody. Doba k nalezení řešení však může být i při malých rozměrech problému (množství počátečních dat) velmi dlouhá a je tak dlouhá (může to být roky i staletí), že o praktické aplikaci nemůže být řeč. . Proto je při návrhu takových algoritmů nutné teoreticky odhadnout dobu jejich práce na konkrétních datech. Existují také výběrové problémy, pro které můžete vytvořit jedinečné, "rychlé" algoritmy, které vám umožní rychle získat řešení i při velkých rozměrech problému. Metoda backtrackingu je v takových problémech neefektivní.
| Algoritmy pro vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||