Obsah:
Definícia - Čo znamená spätné sledovanie?
Spätné sledovanie je algoritmus na zachytenie niektorých alebo všetkých riešení daných výpočtových problémov, najmä v prípade otázok uspokojenia obmedzení. Algoritmus sa dá použiť iba na problémy, ktoré dokážu akceptovať koncepciu „čiastočného kandidátneho riešenia“ a umožňuje rýchly test, či je kandidátske riešenie kompletným riešením. Spätné sledovanie sa považuje za dôležitú techniku na vyriešenie problémov a hádaniek s obmedzením. To je tiež považované za skvelú techniku pre analýzu a tiež tvorí základ mnohých logických programovacích jazykov.
Techopedia vysvetľuje spätné sledovanie
Spätné sledovanie pomáha pri riešení celkového problému nájdením riešenia prvého čiastkového problému a potom rekurzívnym pokusom vyriešiť ďalšie čiastkové problémy na základe riešenia prvého problému. Ak sa súčasný problém nedá vyriešiť, krok sa zruší a ďalšie možné riešenie sa použije na predchádzajúce kroky a potom pokračuje ďalej. V skutočnosti je jednou z kľúčových vecí pri spätnom sledovaní rekurzia. Považuje sa tiež za metódu dôkladného vyhľadávania pomocou delenia a dobývania. Algoritmus spätného sledovania končí, keď už neexistujú žiadne ďalšie riešenia prvého problému.
Spätné sledovanie je algoritmus, ktorý môže pomôcť dosiahnuť implementáciu nedeterminizmu. Vyžaduje hĺbkové prvé hľadanie daného priestoru vydania. Používa sa väčšinou v logických programovacích jazykoch ako Prolog. Kdekoľvek je možné uplatniť spätné sledovanie, je to rýchlejšie ako technika hrubej sily, pretože pomocou jediného testu sa vylučuje veľké množstvo kandidátov.
