Повратни алгоритми: рекурзивно и претраживање објашњено примерима

Примери где се враћање уназад може користити за решавање загонетки или проблема укључују:

  1. Слагалице попут осам краљица, укрштенице, вербална аритметика, Судоку [нб 1] и Пег Солитаире.
  2. Проблеми комбинаторне оптимизације попут рашчлањивања и проблема са напртњачом.
  3. Логички програмски језици као што су Ицон, Планнер и Пролог, који интерно користе повратно праћење за генерисање одговора.

Пример проблема (проблем витезове турнеје)

Витез је постављен на први блок празне табле и, крећући се према правилима шаха, мора тачно једном посетити сваки квадрат.

Путања коју је следио Најт да покрије све ћелије

Следи шаховска табла са 8 к 8 ћелија. Бројеви у ћелијама означавају број потеза Книгхт-а.

Решење витешке турнеје - Еулер

Наивни алгоритам за витешку турнеју

Наивни алгоритам је генерисати све туре једну по једну и проверити да ли генерисана турнеја задовољава ограничења.

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

А ево и видео објашњења за вас