Backtracking algoritmer: Rekursiv og søgning forklaret med eksempler

Eksempler hvor backtracking kan bruges til at løse gåder eller problemer inkluderer:

  1. Puslespil som otte dronningspuslespil, krydsord, verbal aritmetik, Sudoku [nb 1] og Peg Solitaire.
  2. Kombinerende optimeringsproblemer såsom parsing og rygsækproblemet.
  3. Logiske programmeringssprog som Icon, Planner og Prolog, der bruger backtracking internt til at generere svar.

Eksempel på problem (The Knight's tour problem)

Ridderen placeres på den første blok på et tomt bræt og skal bevæge sig efter skakreglerne og skal besøge hver firkant nøjagtigt en gang.

Sti efterfulgt af Knight for at dække alle cellerne

Følgende er skakbræt med 8 x 8 celler. Tal i celler angiver antallet af riddere.

Ridderens turløsning - af Euler

Naiv algoritme til Knights tur

Den naive algoritme er at generere alle ture en efter en og kontrollere, om den genererede tur opfylder begrænsningerne.

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

Backtracking algoritme til Knights tur

Følgende er Backtracking-algoritmen for Knights turproblem.

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

Og her er en videoforklaring til dig