A*

Pendant ce TP, l’objectif va être de programmer l’algorithme A*. Des détails sur les contraintes pourront être fournis au cours de la séance, veuillez rafraîchir la page pour voir les mises à jour, si on vous le signale.

On commencera par finir la programmation du problème du fermier, en particulier en implémentant les stratégies exhaustives d’exploration de l’espace des solutions vues en cours. Ensuite, on implémentera l’algorithme A* avec, pour heuristique, la distance au nombre d’éléments du bon côté de la rivière (i.e. au départ, tous les éléments sont du mauvais côté donc l’heuristique vaut trois). Afin d’aider ceux qui ne savent par où commencer, un fichier présentant une implémentation de la fonction générant les successeurs est fournie dans le fichier suivant.py fourni. Attention, l’encodage des positions a été changé.

On va maintenant programmer l’algorithme A*, pour le parcours d’un labyrinthe, par exemple et dans un premier temps, le suivant :

où le départ est dans la case (6, 1), en bas, et l’arrivée en (5, 10), en haut.

On se donne comme heuristique la distance de Manhattan, vue en cours.

Pour les rappels de l’algorithme, également vu en cours, on pourra demander à Wikipédia mais sa présentation en cours était la suivante :

Notez que vous devez inclure la structure du labyrinthe, l’accès aux voisins d’un nœud, l’heuristique, le tout de manière générale, afin qu’on puisse changer le cas d’application. Plus votre code sera générique, mieux vous serez noté.

En cas d’évaluation égale de successeurs du nœud courant, on utilisera l’ordre de priorité vu en cours, soit NOSE (nord, ouest, sud, est ; ou haut, gauche, bas, droite).