Ο αλγόριθμος αναζήτησης A* είναι μια δημοφιλής τεχνική αναζήτησης διαδρομής και διατομής γραφημάτων που χρησιμοποιείται σε διάφορες εφαρμογές όπως ⁇ μποτική, ανάπτυξη παιχνιδιών και δρομολόγηση δικτύου. Συνδυάζει τα χαρακτηριστικά της αναζήτησης ενιαίου κόστους και άπληστης αναζήτησης με καλύτερο τρόπο για να βρει αποτελεσματικά τη συντομότερη διαδρομή από έναν κόμβο έναρξης σε έναν κόμβο στόχου. Αυτός ο οδηγός παρέχει μια διαδικασία βήμα προς βήμα για την εφαρμογή του αλγόριθμου A* με υπολογισμούς παράδειγμα για να απεικονίσει κάθε στάδιο.

Κατανόηση του Αλγόριθμου Α*

Ο αλγόριθμος A* χρησιμοποιεί συνάρτηση κόστους, f(n) = g(n) + h(n), όπου:

  • g(n): Το πραγματικό κόστος από τον κόμβο έναρξης έως τον κόμβο n.
  • h(n): Η εφορευτική εκτίμηση του κόστους από κόμβο ν στο τέρμα.

Ο αλγόριθμος διερευνά κόμβους με τη χαμηλότερη τιμή f(n) , εξισορρόπηση πραγματικό και εκτιμώμενο κόστος για να βρει τη βέλτιστη διαδρομή αποτελεσματικά.

Εφαρμογή βήμα προς βήμα

Ακολουθήστε αυτά τα βήματα για την εφαρμογή του αλγόριθμου A*:

1. Αρχικοποίηση των ανοιχτών και κλειστών καταλόγων

Η ανοικτή λίστα περιέχει κόμβους που πρέπει να αξιολογηθούν, ξεκινώντας με τον αρχικό κόμβο. Η κλειστή λίστα περιέχει κόμβους που έχουν ήδη αξιολογηθεί.

2. Επιλέξτε τον κόμβο με το χαμηλότερο f(n)

Αφαιρέστε αυτόν τον κόμβο από την ανοιχτή λίστα και προσθέστε τον στην κλειστή λίστα.

3. Δημιουργία γειτονικών κόμβων

Υπολογίστε το g(n) και το h(n) για κάθε γείτονα. Αν ένας γείτονας δεν βρίσκεται στον ανοικτό κατάλογο ή έχει χαμηλότερο g(n), ενημερώστε τις τιμές του και ρυθμίστε τον γονέα του στον τρέχοντα κόμβο.

4. Επαναλάβετε μέχρι να επιτευχθεί ο στόχος

Συνεχίστε τη διαδικασία μέχρι να προστεθεί ο κόμβος στόχου στον κλειστό κατάλογο, υποδεικνύοντας την συντομότερη διαδρομή που έχει βρεθεί.

Παράδειγμα υπολογισμών

Εξετάστε ένα απλό πλέγμα με κόμβο έναρξης Α και κόμβο στόχο G. Η ηρωιστική h(n) είναι η ευθεία απόσταση. Οι αρχικοί υπολογισμοί είναι οι εξής:

Ξεκινώντας από τον κόμβο Α, g(A) = 0, h(A) = 4. Οι f(A) = 4. Οι γειτονικοί κόμβοι Β και Γ αξιολογούνται:

Για κόμβο Β: g(B) = g(A) + κόστος(A, B) = 0 + 1 = 1, h(B) = 3, f(B) = 4.

Για κόμβο Γ: g(C) = 1, h(C) = 2, f(C) = 3. Ο κόμβος Γ έχει το χαμηλότερο f(n), οπότε επιλέγεται μετά.

Η διαδικασία αυτή συνεχίζεται, ενημερώνοντας τις τιμές g, h, και f, μέχρι να επιτευχθεί ο κόμβος στόχου G με την συντομότερη διαδρομή που έχει εντοπιστεί.