Backtracking

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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 stromu problému.[1] 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[editovat | editovat zdroj]

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žiny Si, xiSi. Zpravidla je třeba najít n-tici, které optimalizuje nějakou účelovou funkci P(x1,...,xn). Můžou 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.

Využití[editovat | editovat zdroj]

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.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. VIRIUS, Miroslav. Základy algoritmizace. Praha : ČVUT, 1995. ISBN 80-01-01346-4.