Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει το Backtracking;
Το Backtracking είναι ένας αλγόριθμος για τη λήψη ορισμένων ή όλων των λύσεων σε δεδομένα θέματα υπολογιστικής, ειδικά για θέματα ικανοποίησης περιορισμών. Ο αλγόριθμος μπορεί να χρησιμοποιηθεί μόνο για προβλήματα που μπορούν να δεχθούν την έννοια της "μερικής υποψήφιας λύσης" και επιτρέπουν μια γρήγορη δοκιμή για να διαπιστωθεί εάν η υποψήφια λύση μπορεί να είναι μια ολοκληρωμένη λύση. Το Backtracking θεωρείται σημαντική τεχνική για την επίλυση προβλημάτων ικανοποίησης περιορισμού και παζλ. Θεωρείται επίσης μια μεγάλη τεχνική για την ανάλυση και επίσης αποτελεί τη βάση πολλών λογικών γλωσσών προγραμματισμού.
Η Techopedia εξηγεί το Backtracking
Το Backtracking βοηθά στην επίλυση ενός συνολικού προβλήματος βρίσκοντας μια λύση στο πρώτο υπο-πρόβλημα και στη συνέχεια επιχειρώντας αναδρομικά να επιλύσει άλλα υπο-προβλήματα που βασίζονται στη λύση του πρώτου θέματος. Εάν το τρέχον ζήτημα δεν μπορεί να επιλυθεί, το βήμα παραπέμπεται και η επόμενη δυνατή λύση εφαρμόζεται στα προηγούμενα βήματα και στη συνέχεια προχωράει περαιτέρω. Στην πραγματικότητα, ένα από τα βασικά πράγματα στην ανατροπή είναι η επανάληψη. Θεωρείται επίσης ως μια μέθοδος εξαντλητικής αναζήτησης χρησιμοποιώντας το χάσμα και την κατάκτηση. Ένας αλγόριθμος εκτροπής τελειώνει όταν δεν υπάρχουν άλλες λύσεις στο πρώτο υπο-πρόβλημα.
Το Backtracking είναι ένας αλγόριθμος που μπορεί να συμβάλει στην επίτευξη εφαρμογής του μη εξ ορισμού. Απαιτείται μια πρώτη αναζήτηση βάθους σε ένα συγκεκριμένο χώρο. Χρησιμοποιείται κυρίως σε λογικές γλώσσες προγραμματισμού όπως το Prolog. Οπουδήποτε μπορεί να εφαρμοστεί ο αναστολέας, είναι ταχύτερη από την τεχνική της βίαιης δύναμης, καθώς εξαλείφει μεγάλο αριθμό υποψηφίων με μία μόνο δοκιμασία.
