Σε αυτό το σεμινάριο, θα μάθετε τι είναι ο αλγόριθμος backtracking. Επίσης, θα βρείτε ένα παράδειγμα προσέγγισης backtracking.
Ένας αλγόριθμος backtracking είναι ένας αλγόριθμος επίλυσης προβλημάτων που χρησιμοποιεί μια προσέγγιση brute force για την εύρεση της επιθυμητής παραγωγής.
Η προσέγγιση Brute force δοκιμάζει όλες τις πιθανές λύσεις και επιλέγει τις επιθυμητές / καλύτερες λύσεις.
Ο όρος backtracking υποδηλώνει ότι εάν η τρέχουσα λύση δεν είναι κατάλληλη, τότε ακολουθήστε και δοκιμάστε άλλες λύσεις. Έτσι, η αναδρομή χρησιμοποιείται σε αυτήν την προσέγγιση.
Αυτή η προσέγγιση χρησιμοποιείται για την επίλυση προβλημάτων που έχουν πολλές λύσεις. Εάν θέλετε μια βέλτιστη λύση, πρέπει να ακολουθήσετε δυναμικό προγραμματισμό.
Κρατικό διαστημικό δέντρο
Ένα δέντρο κατάστασης διαστήματος είναι ένα δέντρο που αντιπροσωπεύει όλες τις πιθανές καταστάσεις (λύση ή μη επίλυση) του προβλήματος από τη ρίζα ως αρχική κατάσταση έως το φύλλο ως τελική κατάσταση.
Κρατικό διαστημικό δέντρο
Αλγόριθμος Backtracking
Backtrack (x) εάν το x δεν είναι λύση επιστρέφει ψευδές εάν το x είναι μια νέα λύση προσθήκη στη λίστα λύσεων backtrack (επέκταση x)
Παράδειγμα προσέγγισης επιστροφής
Πρόβλημα: Θέλετε να βρείτε όλους τους πιθανούς τρόπους τακτοποίησης 2 αγοριών και 1 κοριτσιού σε 3 παγκάκια. Περιορισμός: Το κορίτσι δεν πρέπει να βρίσκεται στο μεσαίο πάγκο.
Λύση: Υπάρχουν συνολικά 3! = 6 δυνατότητες. Θα δοκιμάσουμε όλες τις δυνατότητες και θα βρούμε τις πιθανές λύσεις. Δοκιμάζουμε αναδρομικά όλες τις δυνατότητες.
Όλες οι δυνατότητες είναι:
Όλες οι δυνατότητες
Το ακόλουθο διαστημικό δέντρο δείχνει τις πιθανές λύσεις.
Αναφέρετε το δέντρο με όλες τις λύσεις
Εφαρμογές αλγορίθμου Backtracking
- Για να βρείτε όλες τις διαδρομές Hamiltonian σε ένα γράφημα.
- Για την επίλυση του προβλήματος Ν Queen.
- Επίλυση προβλήματος λαβυρίνθου.
- Το πρόβλημα της περιοδείας του Ιππότη.
