Backtracking Algorithms: Αναδρομική και αναζήτηση εξηγείται με παραδείγματα

Παραδείγματα όπου το backtracking μπορεί να χρησιμοποιηθεί για την επίλυση παζλ ή προβλημάτων περιλαμβάνουν:

  1. Παζλ όπως παζλ οκτώ βασίλισσες, σταυρόλεξα, λεκτική αριθμητική, Sudoku [nb 1] και Peg Solitaire.
  2. Συνδυαστικά προβλήματα βελτιστοποίησης όπως η ανάλυση και το πρόβλημα σακιδίων.
  3. Γλώσσες προγραμματισμού λογικής, όπως το Icon, το Planner και το Prolog, οι οποίες χρησιμοποιούν εσωτερικά backtracking για τη δημιουργία απαντήσεων.

Παράδειγμα προβλήματος (Το πρόβλημα της περιοδείας του Ιππότη)

Ο ιππότης τοποθετείται στο πρώτο τετράγωνο ενός άδειου σκάφους και, κινώντας σύμφωνα με τους κανόνες του σκακιού, πρέπει να επισκεφτεί κάθε τετράγωνο ακριβώς μία φορά.

Διαδρομή που ακολουθείται από τον Knight για να καλύψει όλα τα κελιά

Ακολουθεί η σκακιέρα με 8 x 8 κελιά. Οι αριθμοί σε κελιά υποδεικνύουν τον αριθμό κίνησης του Ιππότη.

Η λύση περιοδείας του ιππότη - από τον Euler

Naive Αλγόριθμος για την περιοδεία του Knight

Ο αλγόριθμος Naive είναι να δημιουργήσει όλες τις περιηγήσεις μία προς μία και να ελέγξει αν η παραγόμενη περιοδεία ικανοποιεί τους περιορισμούς.

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

Backtracking Algorithm για την περιοδεία του Knight's

Ακολουθεί ο αλγόριθμος Backtracking για το πρόβλημα της περιοδείας του Knight.

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

Και εδώ είναι μια εξήγηση βίντεο για εσάς