Povratni algoritmi: rekurzivno i pretraživanje objašnjeno primjerima

Primjeri gdje se vraćanje unatrag može koristiti za rješavanje zagonetki ili problema uključuju:

  1. Slagalice poput osam kraljica puzzle, križaljke, verbalna aritmetika, Sudoku [nb 1] i Peg Solitaire.
  2. Problemi kombinatorne optimizacije poput raščlanjivanja i problema s naprtnjačom.
  3. Logički programski jezici kao što su Icon, Planner i Prolog, koji interno koriste povratno kopiranje za generiranje odgovora.

Primjer problema (problem viteške turneje)

Vitez je postavljen na prvi blok prazne ploče i krećući se prema pravilima šaha, mora točno posjetiti svaki kvadrat.

Put koji slijedi Knight da pokrije sve stanice

Slijedi šahovnica s 8 x 8 ćelija. Brojevi u ćelijama označavaju broj poteza Knight-a.

Rješenje viteške turneje - Euler

Naivni algoritam za vitešku turneju

Naivni algoritam generira sve ture jednu po jednu i provjerava zadovoljava li generirana turneja ograničenja.

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

Algoritam povratka za vitešku turneju

Slijedi Backtracking algoritam za Knight-ov problem turneje.

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

A evo i video objašnjenja za vas