Backtracking

Technology

12 hours ago

Author

problému osmi dam Backtracking (česky zpětné vyhledávání, metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky) je způsob řešení algoritmických problémů založený na prohledávání stavového prostoru problému. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na prohledávání do hloubky možných řešení.

Algoritmus je možné použít pro řešení velkého množství problémů, nicméně díky jeho (obecně) exponenciální časové složitosti se používá jen tehdy, kdy není znám efektivnější algoritmus (polynomiální) nebo je použit pro data malé velikosti, popřípadě pro něj existuje dobrá heuristika.

Formulace

Metodu je možné použít v případě, že řešením je vektor (x1, …, xn), jehož jednotlivé složky vybíráme z množin Si, xi∈Si. Zpravidla je třeba najít n-tici, která optimalizuje nějakou účelovou funkci P(x1, …, xn). +more Mohou se ale také hledat všechny n-tice, které tuto podmínku splňují. Metoda vytváří n-tice jednu složku po druhé. Přitom používá účelovou funkci (nebo nějakou vhodnou pomocnou funkci) a pro každou nově vytvořenou složku testuje, zda by taková n-tice vůbec mohla být optimální nebo splňovat dané podmínky. Jestliže pro nějaké xi žádaný vektor (x1, …, xi) nemůže být optimální, není třeba už žádný takový vektor testovat a vezmeme další možnou hodnotu i-té složky. Pokud jsou vyčerpány všechny hodnoty i-té složky, vrátí se metoda zpět o jeden krok a zkouší další možnou hodnotu xi-1.