Τι πρέπει να ξέρω:

Ο Άπληστος Αλγόριθμος- Greedy :

1) Είναι αλγόριθμος ευρετικής αναζήτησης

2) Αναπτύσσει τον κόμβο που έχει μικρότερο ευρετικό κόστος

3) Συνάρτηση πραγματικού κόστους h*(v) του κόμβου v ορίζουμε ως το κόστος του βέλτιστου μονοπατιού από τον κόμβο v προς τον κόμβο στόχο

4) Ευρετική συνάρτηση h(v) του κόμβου v ορίζεται ως μια εκτίμηση του πόσο απέχει ο κόμβος από ένα κόμβο–στόχο

5) Μια ευρετική συνάρτηση λέγεται παραδεκτή αν h(v) ≤ h*(v) για κάθε κόμβο του v

6) Σε προβλήματα λαβυρίνθων ορίζουμε ως ευρετική συνάρτηση την απόσταση Manhattan του κόμβου από τον κόμβο – στόχο

manhattan ((x1, y1), (x2, y2)) = |x1-x2|+|y1-y2|

Ακολουθεί αναλυτικό παράδειγμα εκτέλεσης βήμα-βήμα το Άπληστου -Greedy αλγορίθμου καθώς και τι θα πρέπει να προσέξετε κατά την υλοποίηση του.