Tagasiotsingu algoritmid: rekursiivsed ja otsingud koos näidetega

Näited, kus tagasiteed saab kasutada mõistatuste või probleemide lahendamiseks, on järgmised:

  1. Mõistatused, näiteks kaheksa kuninganna puzzle, ristsõnad, verbaalne aritmeetika, Sudoku [nb 1] ja Peg Solitaire.
  2. Kombinatoriaalsed optimeerimisprobleemid, näiteks sõelumine ja seljakoti probleem.
  3. Loogika programmeerimiskeeled nagu Icon, Planner ja Prolog, mis kasutavad vastuste loomiseks sisemist tagasiteed.

Näiteprobleem (Rüütli tuuri probleem)

Rüütel asetatakse tühja laua esimesele klotsile ja malereeglite järgi liikudes peab külastama igat ruutu täpselt ühe korra.

Tee, millele järgneb Knight, et katta kõik lahtrid

Järgneb 8 x 8 lahtriga malelaud. Lahtrites olevad numbrid näitavad rüütli käigunumbrit.

Rüütli ringkäigu lahendus - autor Euler

Rüütli tuuri naiivne algoritm

Naiivne algoritm peab genereerima kõik ekskursioonid ükshaaval ja kontrollima, kas loodud tuur vastab piirangutele.

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

Rüütli turnee tagurpidi algoritm

Järgneb Knighti turneeprobleemi tagasitee algoritm.

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

Ja siin on teile video selgitus