Алгоритми за проследяване: Рекурсивно и търсене, обяснено с примери

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

  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; } } 

Алгоритъм за връщане назад за рицарско турне

Следва алгоритъмът Backtracking за проблема на Knight's tour.

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" ) 

И ето видео обяснение за вас