Visszafutás

Visszafutás, angolul backtracking, egy általános algoritmikus technika a problémamegoldás területén. Célja olyan megoldások keresése, amelyek egy lépésről lépésre épülő, jelölésekhez igazodó döntési fán találhatók. A módszer addig halad előre, amíg egy részmegoldás minden korlátot kielégít, és visszalép, ha egy választás nem vihet tovább érvényes megoldáshoz. Ezzel a visszavezetéssel vagy a korábbi döntések megváltoztatásával sokkal gyorsabban találhatók érvényes megoldások vagy megállapítható, hogy nincs megoldás.

Működésének lényege egy rekurzív vagy mélységi keresés a döntési fán. Minden lépésen kiválasztunk egy változót, kiválasztunk egy értéket és megvizsgáljuk, hogy tovább vezet-e a megoldáshoz. Ha a jelenlegi részmegoldás megfelel a kontextus korlátainak, haladunk; ha nem, visszalépünk egy korábbi szintre, és kipróbálunk egy másik értéket. Gyakran alkalmaznak olyan technikákat, mint az előreellenőrzés (forward checking) vagy a konzisztencia-propagagáció, amelyek korlátozzák a lehetséges értékek halmazát a keresés során.

Alkalmazási területek közé tartoznak a combinatorikus problémák és a kontextus-szolgáltatók, például a N királynő feladat (N-Queens), Sudoku, keresztrejtvény- vagy logikai rejtvénymegoldások, valamint általános konzisztencia-szabadítási feladatok (CSP-k) megoldása. A visszafutás egyszerű és sokrétű, de legrosszabb esetben kizárólag exponenciális futási időt is adhat, ezért a gyakorlatban hatékony érték- és változókiválasztási stratégiákkal jelentősen növelhető a teljesítmény.

Kapcsolódó fogalmak közé tartozik a mélységi keresés, a konzisztencia-átvitel és a heuristikák használata a keresési tér csökkentésére.