background image

31 | 

9 4

 

 

 

START 
Generate the initial population 
Compute fitness 
Repeat 

Selection 
Crossover 
Mutation 
Compute fitness 

UNTIL the population has converged 
STOP 
 

Εικόνα 8: Ψευδοκώδικας Γενετικού Αλγορίθμου

 

 

 

2.7 

Ο Αλγόριθμος αναζήτησης A-Star (A*)  

 

Η επίτευξη ενός προορισμού μέσω της συντομότερης διαδρομής είναι μια καθημερινή 

δραστηριότητα που όλοι κάνουμε. Ο A-star (που επίσης  αναφέρεται ως A*) είναι ένας από 

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

κόστος  μεταξύ  κόμβων  ή  γραφημάτων  (Sobey.,  2006).  Θα  τον  χρησιμοποιήσουμε  για  να 

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

ενημερωμένος  αλγόριθμος  αναζήτησης,  καθώς  χρησιμοποιεί  πληροφορίες  σχετικά  με  το 

κόστος της διαδρομής αλλά και ευρετικά κριτήρια για να βρει τη λύση (Russell, 2018). 

Ο  Α*  είναι  βέλτιστος  και  πλήρης  αλγόριθμος,  δύο  πολύτιμες  ιδιότητες  των 

αλγορίθμων αναζήτησης. 

Όταν ένας αλγόριθμος αναζήτησης έχει την ιδιότητα του βέλτιστου, σημαίνει ότι είναι 

εγγυημένη η βέλτιστη δυνατή λύση. Όταν ένας αλγόριθμος αναζήτησης έχει την ιδιότητα της 

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

αλγόριθμος εγγυάται ότι θα τη βρει (Delling, Sanders, Schultes, & Wagner, 2009). 

Μερικές ορολογίες του A* για να καταλάβουμε πώς λειτουργεί: