Ποια είναι η εξήγηση για τον αλγόριθμο A αναλυτικά;

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

Διαίσθηση

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

Πώς λειτουργεί το A*;

Ο Α* διατηρεί δύο σετ κόμβων κατά την αναζήτησή του:ΑΝΟΙΚΤΟ (Περιθώριο) και ΚΛΕΙΣΤΟ

ΑΝΟΙΧΤΟ περιέχει όλους τους κόμβους που έχουν δημιουργηθεί, αλλά δεν έχουν ακόμη αξιολογηθεί πλήρως. Διατάσσεται με βάση τη βαθμολογία F (αναφέρεται παρακάτω) των μελών της, με τη χαμηλότερη βαθμολογία F στο μπροστινό μέρος.

ΚΛΕΙΣΤΟ περιέχει όλους τους κόμβους που έχουν αξιολογηθεί πλήρως.

Ο αλγόριθμος ξεκινά με την τοποθέτηση του αρχικού κόμβου στο OPEN, ενώ ο κόμβος στόχου βρίσκεται αρχικά στο ΚΛΕΙΣΤΟ. Σε κάθε βήμα του αλγορίθμου, ο A* αφαιρεί τον κόμβο στο OPEN με τη χαμηλότερη βαθμολογία F, τον επεκτείνει και προσθέτει όλους τους γείτονές του στο OPEN. Εάν ένας γείτονας δεν είναι ήδη στο OPEN ή CLOSED, ο A* υπολογίζει μια βαθμολογία G (το πραγματικό κόστος για να φτάσει ο γείτονας από τον αρχικό κόμβο) και μια βαθμολογία H (μια εκτίμηση του κόστους για την επίτευξη του στόχου από τον γείτονα) για αυτό , και το προσθέτει στο OPEN. Εάν ένας γείτονας είναι ήδη στο OPEN, η νέα βαθμολογία G συγκρίνεται με την τρέχουσα βαθμολογία G και εάν η νέα βαθμολογία G είναι χαμηλότερη, ο γείτονας ενημερώνεται. Εάν ένας γείτονας είναι ήδη στο ΚΛΕΙΣΤΟ, η νέα βαθμολογία G συγκρίνεται με την τρέχουσα βαθμολογία G και εάν η νέα βαθμολογία G είναι χαμηλότερη, ο γείτονας μετακινείται από το ΚΛΕΙΣΤΟ στο OPEN και ενημερώνεται.

Τερματισμός

Ο αλγόριθμος τελειώνει με έναν από τους δύο τρόπους. Πρώτον, εάν ένας γείτονας του κόμβου που επεκτείνεται είναι ο στόχος, ο αλγόριθμος επιστρέφει τη διαδρομή προς τον στόχο. Δεύτερον, εάν το OPEN γίνει κενό, ο αλγόριθμος τερματίζεται ανεπιτυχώς, υποδεικνύοντας ότι δεν υπάρχει έγκυρη διαδρομή από τον αρχικό κόμβο προς τον στόχο.

Πολυπλοκότητα

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