A* αλγόριθμος αναζήτησης
Το A* είναι ένα σύνολο βημάτων (ένας αλγόριθμος) που οι υπολογιστές μπορούν να χρησιμοποιήσουν για να υπολογίσουν πώς να φτάσουν γρήγορα κάπου μεταξύ δύο τόπων. Αν έχετε έναν κατάλογο με τοποθεσίες και πόσο δύσκολο είναι να πάτε από τη μία κατευθείαν στην άλλη, η χρήση του Α* μπορεί να σας πει γρήγορα τον ταχύτερο τρόπο. Σχετίζεται με τον αλγόριθμο του Dijkstra, αλλά κάνει έξυπνες εικασίες, ώστε να μην ξοδεύει τόσο χρόνο προσπαθώντας αργούς τρόπους. Είναι μια καλή σειρά βημάτων αν θέλετε μόνο τη διαδρομή μεταξύ δύο τόπων. Αν πρόκειται να ζητήσετε πολλά μονοπάτια από τον ίδιο χάρτη, τότε υπάρχουν ταχύτεροι τρόποι, που βρίσκουν όλες τις απαντήσεις ταυτόχρονα, όπως ο αλγόριθμος Floyd-Warshall. Ο A* δεν θα λειτουργήσει αν θέλετε να επισκεφθείτε πολλά μέρη σε ένα ταξίδι (το πρόβλημα του πλανόδιου πωλητή).
Τα βήματα
Το A* χρειάζεται πρώτα μια λίστα με όλα τα μέρη στα οποία μπορείτε να πάτε, και μετά μια λίστα με την απόσταση του δρόμου μεταξύ του καθενός. Στη συνέχεια, θα σας πει τον ταχύτερο τρόπο για να πάτε από το μέρος Α στο μέρος Ζ.
Για παράδειγμα, θα πούμε ότι το Α συνδέεται με τα μέρη Β και Γ, και τα Β και Γ συνδέονται και τα δύο με τα Δ και Ε. Τα Δ και Ε συνδέονται και τα δύο με το Ζ. Υπάρχουν 4 πιθανοί τρόποι να πάτε από το Α στο Ζ. Μπορείτε να πάτε Α-Β-Δ-Ζ, Α-Γ-Δ-Ζ, Α-Β-Ε-Ζ ή Α-Γ-Ε-Ζ. Ένας υπολογιστής που χρησιμοποιεί το Α* εξετάζει πρώτα πόσο δύσκολο είναι να πάτε από το Α στο Β και από το Α στο Γ. Αυτό είναι το "κόστος" για αυτά τα μέρη. Το κόστος ενός τόπου σημαίνει πόσο δύσκολο είναι να φτάσετε από το Α σε αυτό το μέρος. Αφού καταγράψει και τα δύο κόστη, ο υπολογιστής εξετάζει πόσο δύσκολο είναι να φτάσει κανείς από το Β στο Δ και το προσθέτει στο κόστος του Β. Το γράφει ως κόστος του Δ. Στη συνέχεια, ο υπολογιστής εξετάζει πόσο δύσκολο είναι να πάει κανείς από το Γ στο Δ και το προσθέτει στο κόστος του Γ. Αυτό είναι ένα διαφορετικό κόστος για το Δ, και αν είναι μικρότερο από αυτό που έχει ήδη, θα αντικαταστήσει το παλιό. Ο υπολογιστής θέλει να γνωρίζει μόνο το καλύτερο μονοπάτι, οπότε αγνοεί το μονοπάτι με το υψηλότερο κόστος. Θα θυμάται μόνο ένα από τα A-B-D και A-C-D, όποιο από τα δύο είναι ταχύτερο.
Ο υπολογιστής συνεχίζει και βρίσκει τον ταχύτερο τρόπο για να φτάσει στο Ε. Τέλος, πηγαίνει από το Δ στο Ζ και βρίσκει ένα κόστος, και από το Ε στο Ζ και βρίσκει ένα κόστος. Βρίσκει ένα τελικό κόστος για το Ζ, και αυτό είναι το μικρότερο κόστος που μπορεί να βρει. Τώρα ο υπολογιστής ξέρει ποιος δρόμος είναι ο γρηγορότερος και έχει την απάντηση. Ο υπολογιστής μπορεί να κάνει μια παρόμοια σειρά βημάτων, αλλά με πολλές πολλές περισσότερες θέσεις. Κάθε φορά, θα κοιτάζει το μέρος που είναι πιο κοντά στο Α και θα προσθέτει το κόστος στα γειτονικά μέρη αυτού του μέρους.
Οι άνθρωποι αποκαλούν την παραπάνω σειρά βημάτων αλγόριθμο του Dijkstra. Ο αλγόριθμος του Dijkstra μπορεί να είναι αργός, επειδή θα κοιτάξει σε πολλά μέρη που μπορεί να πηγαίνουν προς τη λάθος κατεύθυνση από το Ζ. Αν ρωτούσατε τον υπολογιστή πώς να πάτε από μια πόλη σε μια κοντινή, ο αλγόριθμος του Dijkstra μπορεί να καταλήξει να ψάχνει σε μια άλλη πολιτεία.
Το A* διορθώνει αυτό το πρόβλημα. Το A* σας επιτρέπει να πείτε στον υπολογιστή μια εικασία για το πόσο μακριά θα είναι από κάθε σημείο μέχρι το τέλος. Ο υπολογιστής μπορεί να χρησιμοποιήσει την εικασία για να πει κατά προσέγγιση πόσο μακριά θα χρειαστεί για να φτάσετε από ένα συγκεκριμένο μέρος στο Ζ. Αντί να επιλέξει απλώς το μέρος που βρίσκεται πιο κοντά στο Α για να το κοιτάξει, θα κοιτάξει εκείνο που πιθανώς θα έχει το χαμηλότερο συνολικό ποσό. Βρίσκει αυτό το σύνολο προσθέτοντας το κόστος στην αναμενόμενη απόσταση που απομένει. Με αυτόν τον τρόπο, μπορεί να κοιτάξει μόνο προς την κατεύθυνση όπου τα πράγματα πιθανώς θα γίνουν καλύτερα. Δεν πειράζει αν η εικασία δεν είναι τέλεια, αλλά ακόμη και μια απλή κακή εικασία μπορεί να κάνει το πρόγραμμα να πάει πολύ πιο γρήγορα. Αν προσπαθείτε να βρείτε μια διαδρομή μεταξύ δύο σημείων στον πραγματικό κόσμο, μια καλή εικασία είναι απλώς η απόσταση μεταξύ τους σε ευθεία γραμμή. Το πραγματικό μονοπάτι πάνω σε δρόμους θα είναι μεγαλύτερο, αλλά αυτό επιτρέπει στο πρόγραμμα να το μαντέψει και δεν θα πάει σε λάθος κατεύθυνση.
Στη βιβλιογραφία των μαθηματικών ή της επιστήμης των υπολογιστών, αυτή η εικασία είναι συχνά μια συνάρτηση του τόπου και ονομάζεται ευρετική. Κάθε τόπος είναι μια κορυφή και κάθε διαδρομή μεταξύ δύο τόπων είναι μια ακμή. Αυτές είναι λέξεις από τη θεωρία γραφημάτων.
