Алгоритми зворотного відстеження: рекурсивні та пошукові пояснення на прикладах

Приклади, коли зворотне відстеження може бути використано для вирішення головоломок або проблем, включають:

  1. Головоломки, такі як вісім головоломок королеви, кросворди, словесна арифметика, судоку [nb 1] та пасьянс Peg.
  2. Комбінаторні проблеми оптимізації, такі як синтаксичний розбір та проблема рюкзака.
  3. Мови логічного програмування, такі як Icon, Planner та Prolog, які використовують зворотне відстеження для генерації відповідей.

Приклад проблеми (проблема лицарського туру)

Лицар ставиться на перший блок порожньої дошки і, рухаючись за правилами шахів, повинен відвідати кожен квадрат рівно один раз.

Шлях, яким слідував Найт, щоб охопити всі камери

Далі - шахова дошка з 8 х 8 клітинками. Цифри в клітинках вказують номер ходу Knight.

Рішення про лицарське турне - Ейлер

Наївний алгоритм для лицарського туру

Наївний алгоритм полягає в тому, щоб генерувати всі тури по одному і перевіряти, чи згенерований тур відповідає обмеженням.

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } 

Алгоритм відступу для лицарського туру

Далі наведено алгоритм зворотного відстеження для проблеми туру Найта.

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" ) 

І ось вам відео пояснення