Obsah:
Definice - Co znamená zpětné sledování?
Zpětné sledování je algoritmus pro zachycení některých nebo všech řešení zadaných výpočetních problémů, zejména pro problémy s omezením spokojenosti. Algoritmus lze použít pouze pro problémy, které dokážou přijmout koncept „řešení částečného kandidáta“ a umožňuje rychlý test, aby se zjistilo, zda kandidátské řešení může být úplným řešením. Zpětné sledování je považováno za důležitou techniku řešení problémů s uspokojením omezení a hádanek. To je také považováno za skvělou techniku pro analýzu a také tvoří základ mnoha logických programovacích jazyků.
Techopedia vysvětluje Backtracking
Zpětné sledování pomáhá při řešení celkového problému tím, že najde řešení prvního dílčího problému a poté se rekurzivně pokouší vyřešit další dílčí problémy na základě řešení prvního problému. Pokud nelze aktuální problém vyřešit, je tento krok zpětný a další možné řešení je použito v předchozích krocích a poté pokračuje dále. Ve skutečnosti je jednou z klíčových věcí při zpětném sledování rekurze. To je také považováno za metodu vyčerpávajícího hledání používat rozdělit a dobýt. Algoritmus zpětného sledování končí, když již neexistují žádná řešení prvního dílčího problému.
Zpětné sledování je algoritmus, který může pomoci dosáhnout nedeterminismu. Vyžaduje hloubkové první hledání daného prostoru vydání. Používá se většinou v logických programovacích jazycích, jako je Prolog. Tam, kde lze použít zpětné sledování, je to rychlejší než technika brutální síly, protože vylučuje velké množství kandidátů pomocí jediné zkoušky.
