====== Dijkstra amélioré : A* ======

[[https://www.youtube.com/watch?v=A60q6dcoCjw&t=937s&ab_channel=polylog|Vidéo en anglais]]

La vidéo explique très bien le principe. Pour l'instant je ne fais pas d'explication supplémentaire.

===== Heuristique =====

Dans la vidéo, vous pouvez voir qu'on utilise une fonction pour « surélever » les nœuds. Cela permet de donner une sorte de pente qui oriente les chemins dans la direction du nœud que l'on cherche à atteindre.

Cette fonction doit être simple à calculer. Elle exprime la distance entre un certain nœud en cours d'analyse et le nœud que l'on cherche à atteindre.

Dans la vidéo où on cherche le chemin le plus court entre deux points sur une carte, la fonction correspond simplement à la distance en ligne droite.

On considère donc que l'on dispose d'une fonction ''heuristic(node)'' qui renvoie une estimation optimiste d'une mesure de distance entre ''node'' et le nœud cible.

===== Implémentation =====

<code lang-none>
ALGORITHME A*
ENTRÉES
    g: le graphe
    start: nœud de départ
    end: nœud de fin
    heuristic: la fonction heuristique
SORTIES
    liste des nœuds, de start à end, réalisant le plus court chemin
DÉBUT
    Créer un dictionnaire visited vide
    Créer un dictionnaire to_visit contenant tous les sommets associées à +infini
    Créer un dictionnaire origine contenant tous les sommets associés à None
    Modifier dans to_visit, associer à start la valeur 0
    TANT QUE to_visit n'est pas vide RÉPÉTER
        sélectionner le nœud n de plus petites valeurs dans to_visit
        SI n est end ALORS
            # chemin trouvé !
            # construire le chemin en utilisant origin
            soit chemin une liste vide,
            TANT QUE n n'est pas None RÉPÉTER
                ajouter n à la suite de chemin
                n = origin[n]
            FIN
            RENVOYER chemin à l'envers
        FIN
        extraire ce nœud de to_visit et le placer, avec la même valeur, dans visited
        POUR CHAQUE voisin v non visité de n RÉPÉTER
            calculer p = valeur associée à n + poids de l'arête (n, v) + heuristic(v)
            SI p < valeur associée ALORS
                dans to_visit, changer la valeur de v en la mettant à p
                dans origin, changer la valeur de v en la mettant à n
            FIN
        FIN
    FIN
    # aucun chemin trouvé !
FIN
</code>

<WRAP box>
Faites l'implémentation.
</WRAP>