Backtracking

Animace řešení 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 (x₁, …, x_n), jehož jednotlivé složky vybíráme z množin S_i, x_i∈S_i. Zpravidla je třeba najít n-tici, která optimalizuje nějakou účelovou funkci P(x₁, …, x_n). 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é x_i žádaný vektor (x₁, …, x_i) 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 x_i-1.

Využití

Backtracking využívají některé programovací jazyky jako Prolog a Planner, obory zabývající se umělou inteligencí a zpracováním přirozeného jazyka.

Odkazy

Související články

• Problém osmi dam
• Jezdcova procházka

Externí odkazy

• Obrázky, zvuky či videa k tématu Backtracking na Wikimedia Commons

Autoritní data	TDKIV: 000003845