Code : A*

Ce notebook illustre l'algorithme A avec différentes heuristiques, sur une grille de taille $n\times n$ où l'objectif est de trouver le plus court chemin de la case en haut à gauche $(0, 0)$ à celle en bas à droite $(n - 1, n - 1)$. Chaque sommet $(i, j)$ est relié aux $4$ (au plus) sommets adjacents.
Remarque : toutes les arêtes ont un poids égal à 1. On pourrait donc utiliser un parcours en largeur pour trouver un plus court chemin. Mais, comme on va le voir, A permet de visiter moins de sommets (et donc d'être plus rapide).
Dans la grille, les obstacles sont en noir, les sommets visités par l'algorithme en bleu et le sommet en cours de traitement en vert. À la fin, le chemin trouvé par A* est colorié en vert.
Les fonctions suivantes sont définies dans le module cpge :

• generate_grid(n) renvoie une matrice de taille $n\times n$ avec des obstacles aléatoires.
• anim_astar(G, h) affiche l'animation de A* avec comme heuristique $h$, c'est-à-dire que $h(i, j)$ est censé donner une approximation de la distance de la case $(i, j)$ à la case $(n-1, n-1)$.

Génération de la grille¶

In [13]:

try:
    __import__("cpge")
except ImportError:
    ! pip install git+https://github.com/fortierq/itc-code &> /dev/null
from cpge import generate_grid, anim_astar

n = 10 # taille de la grille
G = generate_grid(n)

try: __import__("cpge") except ImportError: ! pip install git+https://github.com/fortierq/itc-code &> /dev/null from cpge import generate_grid, anim_astar n = 10 # taille de la grille G = generate_grid(n)

Heuristique nulle¶

Si on choisit $h = 0$ (fonction nulle), A* est identique à Dijkstra. Et comme les poids sont égaux à 1, les sommets sont visités dans l'ordre d'un parcours en largeur.

In [14]:

anim_astar(G, lambda i, j: 0)

anim_astar(G, lambda i, j: 0)

Out[14]:

Once Loop Reflect

Heuristique : Distance euclidienne¶

On choisit maintenant $h(i, j)$ comme étant la distance euclidienne entre $(i, j)$ et $(n - 1, n - 1)$. Il s'agit d'une heuristique admissible, car inférieure à la vraie distance de $(i, j)$ à $(n - 1, n - 1)$. Le chemin renvoyé est donc bien un plus court chemin.
On observe que moins de sommets sont visités qu'avec l'algorithme de Dijkstra.

In [20]:

anim_astar(G, lambda i, j: ((n - 1 - i)**2 + (n - 1 - j)**2)**0.5)

anim_astar(G, lambda i, j: ((n - 1 - i)**2 + (n - 1 - j)**2)**0.5)

Out[20]:

Once Loop Reflect

Heuristique : Distance de Manhattan¶

Même chose que précédemment, mais en utilisant la distance de Manhattan : $$d((i_1, j_1), (i_1, j_1) = |i_1 - i_2| + |j_1 - j_2|$$ Il s'agit aussi d'une heuristique admissible.

In [21]:

anim_astar(G, lambda i, j: (n - 1 - i) + (n  - 1 - j))

anim_astar(G, lambda i, j: (n - 1 - i) + (n - 1 - j))

Out[21]:

Once Loop Reflect

Heuristique : Distance euclidienne au carré¶

En utilisant le carré de la distance euclidienne (plus rapide à calculer puisque on éviter la racine), on obtient une heuristique qui peut renvoyer un chemin non optimal. Cependant, on peut espérer que l'algorithme va trouver un chemin plus rapidement. Cela revient en fait à peu près à un Best First-Search, qui prend en compte uniquement la distance à l'objectif et non au sommet de départ.

In [18]:

anim_astar(G, lambda i, j: (n - i)**2 + (n  - j)**2)

anim_astar(G, lambda i, j: (n - i)**2 + (n - j)**2)

Out[18]:

Once Loop Reflect