Αλγόριθμοι πληροφορημένης (ή ευρετικής) αναζήτησης

[voulaji]

Όπως είναι γνωστό, η μοναδική διαφορά (σε επίπεδο υλοποίησης) των αλγορίθμων αναζήτησης πρώτα σε πλάτος και πρώτα σε βάθος είναι ότι ο πρώτος τοποθετεί τους νέους (γκρι) κόμβους στο τέλος του μετώπου (frontier) αναζήτησης ενώ ο δεύτερος στην αρχή. Υπάρχουν ωστόσο και άλλες επιλογές, οι οποίες οδηγούν σε ολόκληρη κατηγορία νέων αλγορίθμων, όπως η Αναζήτηση πρώτα στο καλύτερο (best-first search) και η Αναζήτηση Α* (Α* search).

Το πρόβλημά μου είναι το εξής:

Πως μπορώ να υλοποιήσω αυτούς τους δύο αλγορίθμους, (Χρησιμοποιώντας τις λέξεις best και astar στην είσοδο για να τους δηλώσω.)

Αναλυτικότερα:

Αναζήτηση πρώτα στο καλύτερο (best-first search)

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

 

Αναζήτηση Α* (Α* search)

Παρόμοια με την αναζήτηση πρώτα στο καλύτερο, η μοναδική διαφορά της αναζήτησης Α* είναι ότι στον βαθμό κάθε κόμβου συνυπολογίζεται (προστίθεται) και το πόσες κινήσεις εκτελέσατε από την αρχική κατάσταση για να φτάσετε στον τρέχοντα κόμβο. Για παράδειγμα, εάν ένας κόμβος έχει προκύψει ύστερα από 4 μετακινήσεις του κενού (σε σχέση με την αρχική διάταξη), ενώ η ευρετική απόσταση του από την τελική διάταξη είναι 7, ο συνολικός βαθμός του κόμβου είναι 11. Στην αναζήτηση A* το μέτωπο αναζήτησης διατηρείται ταξινομημένο με βάση το παραπάνω άθροισμα.

[3c0r1z]

Για A* δες εδώ: http://www.gamedev.net/reference/articles/article2003.asp