Plus court chemin
Les algorithmes de recherche du plus court chemin travaillent le plus souvent sur un graphe orienté valué. Pour les adapter à la recherche d’un chemin sur un modèle de terrain, on peut travailler sur une représentation intermédiaire.
Cette représentation peut prendre la forme d’une matrice M de valeurs entières positives correspondants au coût de passage par un élément de cette matrice. La notion de voisinage peut être directe ou indirecte, dans ce second cas il suffit d’appliquer un coût supplémentaire de l’ordre de \(\sqrt{2}\). Afin d’éviter de traiter des cas particuliers, il est recommandé d’ajouter à la matrice initiale une “bordure” de valeurs particulières permettant de normaliser les traitements à effectuer y compris aux bords de la matrice.
Des structures intermédiaires sont à prévoir pour d’une part pouvoir actualiser le coût du chemin du point de départ à un élément de la matrice (futur terrain) et d’autre part retrouver le chemin le plus court une fois le but atteint. Pour le premier point, une matrice de même dimension que la matrice des coûts est nécessaire et pour le deuxième point un simple tableau de correspondance permettra de mémoriser les relations entre voisins successifs du chemin trouvé. Il faut ajouter à cela un modèle de données optimisant la recherche du prochain point du chemin le moins coûteux sous la forme d’un tas (heap).
Exercice 1.
Exercice 2.