Τι είναι ο αλγόριθμος αναζήτησης A*;

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

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

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

Τι είναι ο αλγόριθμος αναζήτησης A*;

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

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

Ως πρώτο βήμα για τη μετατροπή αυτού του λαβύρινθου σε πρόβλημα αναζήτησης, πρέπει να ορίσουμε αυτά τα έξι πράγματα.

1. Ένα σύνολο υποψήφιων καταστάσεων στις οποίες μπορεί να βρισκόμαστε
2. Κατάσταση αρχής και τέλους
3. Ένας τρόπος να αποφασίσουμε αν έχουμε φτάσει στο τελικό σημείο
4. Ένα σύνολο ενεργειών σε περίπτωση πιθανών αλλαγών κατεύθυνσης/διαδρομής
5. Μια συνάρτηση που μας συμβουλεύει για το αποτέλεσμα μιας ενέργειας
6. Ένα σύνολο δαπανών που προκύπτουν σε διαφορετικές καταστάσεις/διαδρομές κίνησης

Για να λύσουμε το πρόβλημα, πρέπει να χαρτογραφήσουμε τις διασταυρώσεις στους κόμβους (που σημειώνονται με τις κόκκινες κουκκίδες) και όλους τους πιθανούς τρόπους με τους οποίους μπορούμε να κάνουμε κινήσεις προς τις άκρες (που υποδηλώνονται με τις μπλε γραμμές).
Το Α υποδηλώνει το σημείο εκκίνησης και το Β το τελικό σημείο. Ορίζουμε τα σημεία έναρξης και τα τελικά σημεία στους κόμβους Α και Β, αντίστοιχα.
Εάν χρησιμοποιούμε έναν αλγόριθμο αναζήτησης χωρίς ενημέρωση, θα είναι σαν να βρίσκουμε μια διαδρομή που είναι τυφλή, ενώ ένας ενημερωμένος αλγόριθμος για ένα πρόβλημα αναζήτησης θα ακολουθούσε τη διαδρομή που σας φέρνει πιο κοντά στον προορισμό σας. Για παράδειγμα, σκεφτείτε τον κύβο του Ρούμπικ. έχει πολλές προοπτικές καταστάσεις στις οποίες μπορείς να είσαι, καθιστώντας τη λύση πολύ δύσκολη. Αυτό απαιτεί τη χρήση ενός αλγορίθμου καθοδηγούμενης αναζήτησης για την εύρεση λύσης. Αυτό εξηγεί τη σημασία του Α*.
Σε αντίθεση με άλλους αλγόριθμους, ο A* αποφασίζει να κάνει ένα βήμα μόνο εάν είναι πειστικά λογικό και λογικό σύμφωνα με τις λειτουργίες του. Αυτό σημαίνει ότι δεν εξετάζει ποτέ κανένα μη βέλτιστο βήμα. Αυτός είναι ο λόγος για τον οποίο το A* είναι μια δημοφιλής επιλογή για συστήματα AI που αναπαράγουν τον πραγματικό κόσμο – όπως τα βιντεοπαιχνίδια και η μηχανική μάθηση.

A* Βήματα αλγόριθμου αναζήτησης

Βήμα 1: Προσθέστε τον αρχικό κόμβο στην ανοιχτή λίστα
Βήμα 2: Επαναλάβετε το ακόλουθο βήμα

Στην ανοιχτή λίστα, βρείτε το τετράγωνο με το χαμηλότερο κόστος F, το οποίο δηλώνει το τρέχον τετράγωνο. Τώρα προχωράμε στην κλειστή πλατεία.

Θεωρήστε 8 τετράγωνα δίπλα στο τρέχον τετράγωνο και Αγνοήστε το εάν είναι στην κλειστή λίστα ή αν δεν είναι εφαρμόσιμο. Κάντε τα εξής εάν είναι εφικτό.

Ελέγξτε αν είναι στην ανοιχτή λίστα. αν όχι, προσθέστε το. Πρέπει να κάνετε το τρέχον τετράγωνο καθώς αυτό το τετράγωνο είναι γονέας. Θα καταγράψετε τώρα τα διαφορετικά κόστη του τετραγώνου, όπως τα κόστη F, G και H.

Εάν βρίσκεται στην ανοιχτή λίστα, χρησιμοποιήστε το κόστος G για να μετρήσετε την καλύτερη διαδρομή. Όσο χαμηλότερο είναι το κόστος G, τόσο καλύτερη είναι η διαδρομή. Εάν αυτή η διαδρομή είναι καλύτερη, κάντε το τρέχον τετράγωνο ως γονικό τετράγωνο. Τώρα πρέπει να υπολογίσετε εκ νέου τις άλλες βαθμολογίες – τις βαθμολογίες G και F αυτού του τετραγώνου.

– Θα σταματήσεις:

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

Δεν υπάρχει διαδρομή εάν η ανοιχτή λίστα είναι κενή και δεν μπορείτε να βρείτε το τετράγωνο προορισμού.

Βήμα 3.Τώρα μπορείτε να αποθηκεύσετε το μονοπάτι και να εργαστείτε προς τα πίσω, ξεκινώντας από το τετράγωνο-στόχο, πηγαίνοντας στο γονικό τετράγωνο από κάθε τετράγωνο που πηγαίνετε, μέχρι να σας οδηγήσει στο τετράγωνο εκκίνησης. Βρήκες τον δρόμο σου τώρα.

Γιατί προτιμάται ο αλγόριθμος αναζήτησης A*;

Είναι εύκολο να δώσετε κίνηση σε αντικείμενα. Αλλά το μονοπάτι δεν είναι απλό. Είναι μια σύνθετη άσκηση. Η παρακάτω κατάσταση το εξηγεί.

Το καθήκον είναι να μεταφέρετε τη μονάδα που βλέπετε στο κάτω μέρος του διαγράμματος στην κορυφή της. Μπορείτε να δείτε ότι τίποτα δεν υποδεικνύει ότι το αντικείμενο δεν πρέπει να ακολουθήσει τη διαδρομή που υποδεικνύεται με ροζ γραμμές. Έτσι επιλέγει να κινηθεί με αυτόν τον τρόπο. Καθώς και όταν φτάσει στην κορυφή, πρέπει να αλλάξει κατεύθυνση λόγω του εμποδίου σε σχήμα «U». Στη συνέχεια αλλάζει κατεύθυνση και περιστρέφεται γύρω από το εμπόδιο για να φτάσει στην κορυφή. Σε αντίθεση με αυτό, ο Α* θα είχε σαρώσει την περιοχή πάνω από το αντικείμενο και θα βρήκε ένα σύντομο μονοπάτι (σημειώνεται με μπλε γραμμές). Έτσι, αλγόριθμοι εύρεσης μονοπατιού όπως ο A* σας βοηθούν να σχεδιάζετε πράγματα αντί να περιμένετε μέχρι να ανακαλύψετε το πρόβλημα. Ενεργούν προληπτικά αντί να αντιδρούν σε μια κατάσταση. Το μειονέκτημα είναι ότι είναι λίγο πιο αργός από τους άλλους αλγόριθμους. Μπορείτε να χρησιμοποιήσετε έναν συνδυασμό και των δύο για να επιτύχετε καλύτερα αποτελέσματα – οι αλγόριθμοι εύρεσης μονοπατιών δίνουν μια μεγαλύτερη εικόνα και μεγάλες διαδρομές με εμπόδια που αλλάζουν αργά και οι αλγόριθμοι κίνησης για τοπική εικόνα και σύντομα μονοπάτια με εμπόδια που αλλάζουν πιο γρήγορα.

Διαβάστε πώς η τεχνητή νοημοσύνη θα δημιουργήσει περισσότερες θέσεις εργασίας έως το 2025.

A* Αλγόριθμος αναζήτησης και οι βασικές του έννοιες

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

Όταν ο Α* μπαίνει σε ένα πρόβλημα, πρώτα υπολογίζει το κόστος για να ταξιδέψει στους γειτονικούς κόμβους και επιλέγει τον κόμβο με το χαμηλότερο κόστος. Εάν το f(n) υποδηλώνει το κόστος, ο A* επιλέγει τον κόμβο με τη χαμηλότερη τιμή f(n). Εδώ το ’n‘ δηλώνει το γειτονικό κόμβους. Ο υπολογισμός της τιμής μπορεί να γίνει όπως φαίνεται παρακάτω:

f(n)=g(n)+h(n)f(n)=g(n)+h(n)
g(n) = δείχνει την τιμή της συντομότερης διαδρομής από τον αρχικό κόμβο στον κόμβο n
h(n) = Η ευρετική προσέγγιση της τιμής του κόμβου

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

Τι είναι μια ευρετική συνάρτηση;

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

Παραδεκτότητα της ευρετικής συνάρτησης

Μια ευρετική συνάρτηση είναι αποδεκτή εάν μπορεί να υπολογίσει αποτελεσματικά την πραγματική απόσταση μεταξύ ενός κόμβου ’n‘ και του τερματικού κόμβου. Ποτέ δεν υπερεκτιμά. αν Αυτό συμβαίνει ποτέ, θα συμβολίζεται με ‚d‘, που υποδηλώνει επίσης την ακρίβεια της λύσης.

Συνέπεια της ευρετικής συνάρτησης

Μια ευρετική συνάρτηση είναι συνεπής εάν η εκτίμηση μιας δεδομένης ευρετικής συνάρτησης αποδεικνύεται ότι είναι ίση ή μικρότερη από την απόσταση μεταξύ του στόχου (n) και ενός γείτονα και το κόστος που υπολογίζεται για την επίτευξη αυτού του γείτονα.

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

Εκτέλεση με την Python

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

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

Ας ξεκινήσουμε με τον κόμβο Α. Εφόσον ο Α είναι ένας αρχικός κόμβος, επομένως, η τιμή του g(x) για τον Α είναι μηδέν, και από το γράφημα, παίρνουμε την ευρετική τιμή του Α είναι 11, επομένως

g(x) + h(x) = f(x)
0+ 11 =11
Thus for A, we can write
A=11
Now from A, we can go to point B or point E, so we compute f(x) for each of them
A → B = 2 + 6 = 8
A → E = 3 + 6 = 9

Since the cost for  A → B is less, we move forward with this path and compute the f(x) for the children nodes of B
Since there is no path between C and G, the heuristic cost is set to infinity or a very high value
A → B → C = (2 + 1) + 99= 102
A → B → G = (2 + 9 ) + 0 = 11
Here the path A → B → G has the least cost but it is still more than the cost of A → E, thus we explore this path further
A → E → D = (3 + 6) + 1 = 10
Comparing the cost of A → E → D with all the paths we got so far and as this cost is least of all we move forward with this path. And compute the f(x) for the children of D
A → E → D → G = (3 + 6 + 1) +0 =10
Now comparing all the paths that lead us to the goal, we conclude that A → E → D → G is the most cost-effective path to get from A to G.

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

Αρχικά, δημιουργούμε δύο σετ, viz-άνοιγμα και κλείσιμο. Το open περιέχει τους κόμβους που έχουν επισκεφθεί, αλλά οι γείτονές τους δεν έχουν ακόμη διερευνηθεί. Από την άλλη πλευρά, το close περιέχει κόμβους που, μαζί με τους γείτονές τους, έχουν επισκεφθεί.

def aStarAlgo(start_node, stop_node):
        
        open_set = set(start_node) 
        closed_set = set()
        g = {} #store distance from starting node
        parents = {}# parents contains an adjacency map of all nodes

        #ditance of starting node from itself is zero
        g[start_node] = 0 
        #start_node is root node i.e it has no parent nodes
        #so start_node is set to its own parent node
        parents[start_node] = start_node
        
        
        while len(open_set) > 0:
            n = None 

            #node with lowest f() is found
            for v in open_set:
                if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
                    n = v
            
                    
            if n == stop_node or Graph_nodes[n] == None:
                pass
            else:
                for (m, weight) in get_neighbors(n):
                    #nodes 'm' not in first and last set are added to first
                    #n is set its parent
                    if m not in open_set and m not in closed_set:
                        open_set.add(m)
                        parents[m] = n
                        g[m] = g[n] + weight
                        
    
                    #for each node m,compare its distance from start i.e g(m) to the
                    #from start through n node
                    else:
                        if g[m] > g[n] + weight:
                            #update g(m)
                            g[m] = g[n] + weight
                            #change parent of m to n
                            parents[m] = n
                            
                            #if m in closed set,remove and add to open
                            if m in closed_set:
                                closed_set.remove(m)
                                open_set.add(m)

            if n == None:
                print('Path does not exist!')
                return None

            # if the current node is the stop_node
            # then we begin reconstructin the path from it to the start_node
            if n == stop_node:
                path = []

                while parents[n] != n:
                    path.append(n)
                    n = parents[n]

                path.append(start_node)

                path.reverse()

                print('Path found: {}'.format(path))
                return path


            # remove n from the open_list, and add it to closed_list
            # because all of his neighbors were inspected
            open_set.remove(n)
            closed_set.add(n)

        print('Path does not exist!')
        return None
        
#define fuction to return neighbor and its distance
#from the passed node
def get_neighbors(v):
    if v in Graph_nodes:
        return Graph_nodes[v]
    else:
        return None
#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes
def heuristic(n):
        H_dist = {
            'A': 11,
            'B': 6,
            'C': 99,
            'D': 1,
            'E': 7,
            'G': 0,
            
        }

        return H_dist[n]

#Describe your graph here  
Graph_nodes = {
    'A': [('B', 2), ('E', 3)],
    'B': [('C', 1),('G', 9)],
    'C': None,
    'E': [('D', 6)],
    'D': [('G', 1)],
    
}
aStarAlgo('A', 'G')

Παραγωγή:

Path Found: [ 'A','E','D','G']

Περαιτέρω ανάγνωση

1. Καλύτερος αλγόριθμος πρώτης αναζήτησης στο AI | Έννοια, Υλοποίηση, Πλεονεκτήματα, Μειονεκτήματα
2. Alpha Beta Pruning σε AI
3. Αλγόριθμος Δέντρου Αποφάσεων Επεξηγημένος με Παραδείγματα
4. Δομές δεδομένων & αλγόριθμος με χρήση Java a Οδηγός για αρχάριους