Cette partie s'intéresse à une extension de l'algorithme de Dijkstra dans lequel les sommets ne sont plus seulement ordonnés en fonction de leur coût par rapport à l'origine mais en fonction de deux coûts : le coût par rapport à l'origine et le coût estimé à la destination. Dans ce cas, le déroulement de l'algorithme de plus court chemin est guidé par la destination du trajet.
Ce principe est une application spécifique de l'algorithme A* (A-star) qui sera étudiée dans sa généralité l'année prochaine en 4ème année IR, parcours Informatique dans le cours d'Intelligence Artificielle.
▸Estimation du coût à la destination
Le coût estimé entre un sommet donné et la destination se base sur un trajet à vol d'oiseau entre les deux sommets et doit être une borne inférieure du coût réel pour garantir l'optimalité du résultat (cette propriété sera démontrée l'année prochaine mais vous pouvez toujours y réfléchir dès maintenant).
Pour éviter de dire des âneries à la soutenance, notez d'emblée que cet algorithme dérivé de A-star doit fournir le plus court chemin (et non pas une simple approximation).
▸Les labels
- Vous avez besoin d'une nouvelle structure LabelStar, qui hérite de Label, pour prendre en compte cette nouvelle information de coût.
- Sans modifier la classe BinaryHeap faites en sorte que les sommets soient maintenant ordonnés selon l'ordre coût depuis l'origine + coût estimé à la destination croissant. En cas d'égalité, on considèrera en premier le sommet ayant le plus petit coût estimé à la destination.
- Une siouxe solution consiste à définir une méthode getTotalCost() dans Label, à l'utiliser dans compareTo de Label, puis à redéfinir getTotalCost dans LabelStar.
La classe LabelStar continue donc d'implémenter l'interface Comparable<Label>.
▸Visualisation et expérimentation
- Visualisez le déroulement de l'algorithme. Sur certaines cartes ou certains trajets, la différence doit être frappante.
Validation (2)
- Effectuez les tests automatiques déjà écrits pour Dijkstra. Votre code étant modulaire, vous pouvez facilement le réutiliser. (réutiliser ne signifie pas copier-coller)
- Un nouveau test comparant les résultats de Dijkstra et A* est pertinent.