Plus Court Chemin Dans Une Grille – Mathman à la rescousse

Introduction

La nuit à Gomath, seule la lueur de la lune perce l'obscurité. Les ombres sont noires et menaçantes. Différents sons se font entendre dans l'air épais de la nuit : des vitres brisées, des néons pulvérisés, des voix amères, dures et ses sirènes de police. Toujours des sirènes de police. La plupart des gens qui fréquentent Gomath la journée ont fui depuis longtemps dans leurs banlieues ou dans leurs appartements sécurisés. En effet, l'endroit n'est pas sûr une fois la nuit tombée.

Une et une seule personne empêche Gomath de sombrer dans une mer de corruption et de désespoir. Un être sombre drapé dans le mystère autant que dans les ténèbres. Tel une fonction récursive, il surgit de la nuit pour fondre sur le mal de Gomath. Pour certains, il est simplement une légende, pour d'autres, il est un vengeur dévoué. Mais pour les criminels, il est leur pire cauchemar. Il est… Mathman !

Mathman
Mathman

Gomath est en danger ! Le MathSignal s'allume, Mathman et son fidèle acolyte Rhobin doivent se dépêcher pour arriver à temps pour sauver Gomath de la noirceur de la nuit. Y arriveront-t-ils à temps ?

Pour cela il devra trouver le plus court chemin dans la grille que représente Gomath. Par les toits ou dans les rues Mathman doit pouvoir trouver son chemin. Pour cela il utilisera comme à son habitude ses mathInstruments tel que son mathGrapin ou son mathGPS.

Plan

  1. La Grille : Mathman étudie la structure de Gomath comme une grille. On verra ici la représentation d'une grille en graphe.
  2. Grille Sans Obstacle : Mathman cherche à trouver le plus court chemin, il utilise son Mathgrapin pour passer au dessus des murs. Ici nous verrons la longueur d'un plus court chemin dans une grille.
  3. Nombre de Chemins : Mathman pense à toutes les éventualités et cherche le nombre de chemins qu'il peut prendre. Ici nous verrons une borne supérieure du nombre de chemins dans une grille.
  4. Le parcours en largeur : Mathman explique le principe de l'algorithme du mathGPS qui lui permet de trouver un plus court chemin vers le MathSignal. Ici nous parlerons du parcours en largeur.
  5. Au pire cas : Mathman veut savoir combien de temps peut prendre son mathGPS pour trouver le plus court chemin. Ici nous verrons la complexité du parcours en largeur.
  6. Algorithme naïf : Rhobin a perdu son mathGPS, il essaye de trouver le plus court chemin avec la mathCarte, combien de temps prendra-t-il ? Ici nous verrons la complexité d'un algorithme naïf pour trouver un plus court chemin.
  7. Algorithme A* : Mathman cherche à améliorer son mathGPS et choisi de regarder si un autre algorithme plus efficace existe. Ici nous ferons une ouverture sur l'algorithme A*.

1. La Grille

Definition

Un graphe non orienté est une paire (S,A) tel que

  • S est un ensemble dont les éléments sont appelés sommets
  • A est un ensemble de paires de sommets distincts, appelées arêtes

Représentation d'une grille en graphe

Plan de Gomath
Plan de Gomath avec comme rues les droites sur le plan.

Une grille comme celle-ci peut être représentée comme un graphe non orienté comme ci-dessous tel que :

  • L'intersection de deux lignes forment un sommet (cercle).
  • Une arête est un segment de ligne entre deux sommets côte à côte représentée par une ligne.
  • L'absence d'arête entre deux sommets côte à côte représente un mur.
Graphe de la ville de gomath
Le Graphe du plan de Gomath

Représentation du graphe en Labyrinthe

On peut aussi représenter un graphe comme un labyrinthe.

Labyrinthe du plan de Gomath
Labyrinthe du plan de Gomath
  • Une case correspond à un sommet du graphe : ici la case bleue est la case de départ, la case verte celle d'arrivée et la case rosée est l'intersection entourée dans la grille précédente.
  • Une arête entre deux sommets est l'absence de mur entre 2 cases côtes à côte.
  • Une absence d'arête est un mur (en blanc ici)

2. Grille Sans Obstacles

Mathman cherche à trouver le plus court chemin, il utilise son Mathgrapin pour passer au dessus des murs. Il n'a donc pas à se soucier de ceux-ci.

Comment aller au plus vite ?

Plus court chemin dans une grille vide

Definition

Un plus court chemin entre deux sommets s et v est un chemin tel qu'il n'existe pas de chemin parcourant moins de sommets pour aller de s à v.

DANS UNE GRILLE VIDE

Le plus court chemin dans une grille vide est un chemin dont les sommets choisis nous rapproche toujours du point d’arrivée.

Donc pour un sommet appartenant à un plus court chemin dans un graphe vide, on a toujours deux directions à savoir de haut en bas et de gauche à droite car un déplacement dans d’autres directions nous éloignerait du point d’arrivée.

Plus court Chemin avec le parcours en largeur

Fonctionnalités :

  • Cliquer sur l'image ci-dessus pour lancer le parcours ou faire pause
  • Cliquer pour relancer une génération à la fin de la précédente
  • Rester appuyé pour accélérer
  • touche r pour relancer avant la fin

Représentation du parcours en largeur :

  • Cases bleues -> Sommets traités
  • Cases rosées -> Sommets dans la file
  • Cases rouges -> Plus court chemin

Les numéros correspondent aux dates de découverte des sommets.

Longueur du plus court chemin

Le plus court chemin entre 2 extrémités opposées du graphe quitte le sommet de départ afin d’atteindre le sommet d’arrivée qui se trouve toujours à une hauteur h et une largeur l du sommet de départ.

Donc ce chemin parcourt toute la largeur et toute la hauteur du graphe vide. Sachant qu'un sommet de ce chemin représente à la fois un sommet de la longueur et le premier sommet de la hauteur, il ne sera compté qu’une seule fois.

Ce qui fait que la longueur du chemin minimal sera toujours égale à la somme de la hauteur (h) et de la largeur (l) moins un sommet :

Longueur du plus court chemin = (l+h)-1

EXEMPLE

exemple de chemin le plus court dans un graphe vide
Labyrinthe 4*4

Ici on a un carré de 4*4 et on obtient bien un chemin minimal (en rouge) de longueur 4+4-1=7

Remarque

Si on considère la possibilité d'aller en diagonale alors la longueur du plus court chemin est plus petite.

3. Nombre de Chemins

BatMath veut être prêt à changer de route au cas où des criminels l'attendent en embuscade. Il se demande donc le nombre maximum de chemins empruntables sans revenir sur ses pas.

Combien de chemins puis-je prendre ?

Si on veut que le nombre de chemins soit maximal on suppose dans un premier temps que la grille est vide. Étant donné qu'ajouter un mur enlève les chemins passant par cet endroit de la carte.

Longueur d'un chemin de longueur maximale

Définition

Un chemin de longueur maximale est un chemin dont le nombre de sommets/arrêtes traversés est le plus grand.

Ici nous calculerons la longueur en nombre de sommets, comme dans le reste du blog.

Longueur

On sait que le chemin de longueur maximale parcours tous les sommets hors, dans une grille, le nombre de sommets est égale à l*h.

Donc la longueur d'un chemin de longueur maximale est l*h.

Première borne supérieure

On sait que dans une grille vide pour n’importe quel sommet on a au maximum 4 choix de sommets pour la suite (celui de droite, de gauche, du haut et du bas).

directions possible pour un chemin
Les 4 choix pour continuer le chemin en rouge.

Or la borne de la taille d'un chemin est l*h.

Puisque l'on cherche une borne supérieure on peut généraliser la taille des chemins à l*h.

Or à chaque sommet que l'on croise il est possible de prendre 4 chemins possibles, on a donc à chaque sommet rencontré un nombre 4 fois plus grands de possibilités.

Donc la borne supérieure dans ce cas est 4l*h.

Réduction de la borne supérieure

On va montrer que le nombre de choix possible pour le prochain sommet à partir d'un sommet peut être réduit à trois.

  • Pour le sommet de départ, on a au maximum 2 choix de chemins.
  • Pour tous les autres sommets, il y a déjà un voisin appartenant au chemin déjà parcouru (vu qu'il ne s'agit pas du sommet de départ). Sachant que sur un chemin un sommet n’apparait qu’une seule fois, le sommet déjà rencontré ne peut pas l’être encore une fois. Donc on enlève un des 4 choix.
directions possible avec un chemin en moins
On enlève le chemin d'où l'on vient.

Donc on ne peut avoir que trois choix d’arêtes pour ces sommets.

Deuxième borne supérieure

On sait que dans une grille vide pour n’importe quel sommet on a au maximum 3 choix d’arêtes pour la suite. Donc avec le même raisonnement que pour la première borne, la borne supérieure est 3l*h.

4. Le parcours en largeur

Le Mathgrapin est cassé ! Heureusement Mathman a son MathGPS qui lui indique le chemin le plus court.

Comment fonctionne le MathGPS ?

Le mathGPS utilise l'algorithme de parcours en largeur pour fonctionner, nous allons donc parler de cet algorithme dans cette partie.

L’algorithme de parcours en largeur permet d'explorer un graphe niveau par niveau et peut, par exemple, trouver un plus court chemin entre deux points distincts.

Les niveaux étant les sommets de même distance du sommet de départ.

Niveaux par distance du sommet 0

Pour la grille du plan de GothMath City, le parcours va donc commencer de la case de départ où se trouve Mathman, à partir de cette case on va chercher toutes les cases atteignables depuis cette dernière (c'est-à-dire toutes les cases adjacentes à la case de départ et dont aucun mur ne sépare la case avec la case de départ). Quand toutes les cases atteignables seront  visitées, on passe aux cases qui leur succèdent et on répète l’opération jusqu’à ce qu'elles soient toutes visitées.

Principe de l'algorithme

L’algorithme utilise une file dans laquelle on va mettre les sommets visités dont on n’a pas encore explorés les voisins.

Definition

Une file ou FIFO (First In, First Out) est une structure de données tel que le premier élément à être mis dans la file est le premier à en sortir.

Exemple

Un très bon exemple est la queue au super marché, le premier à être entré dans la queue est le premier à en sortir lors de son passage en caisse.

Couleur des sommets

Afin de distinguer les sommets déjà visités de ceux que l'on n'a pas encore visité et dont le traitement n’est pas encore fini, on les marque à l’aide de trois couleurs.

  • Gris :  sommets non découverts.
  • Rosé : sommets découverts dont les voisins n’ont pas encore été visités (dans la file).
  • Bleu :  sommets découverts dont les voisins ont aussi été découverts.

Ainsi on ne mettra que les sommets gris dans la file au moment de sa rencontre.

Exemple

Dans notre exemple le sommet vert est le mathsignal.

On va parcourir le graphe suivant avec la numérotation ci-dessous :

Numérotation pour exemple du parcours en largueur

On commence le parcours de la case de départ 0, qui est directement rosée.

Contenu de la file : 0.


Traitement de 0.

On enlève 0 de la file et on y ajoute ses voisins. On colorie la case de droite (1) en rose et on l'ajoute dans la file. La case sous 0 n'est pas coloriée en rose car il n'y a pas d'arête entre ces deux sommets (il y a un mur entre ces deux cases).

La case 0 n'a pas d'autres voisins son traitement se termine et le sommet devient bleu

Exemple du parcours en largueur : étape 1
Traitement de 0.

Contenu de la file : 1.


Traitement de 1.

On passe maintenant au traitement de 1, les cases en dessous (3) et à droite (2) sont grises donc on change leur couleur en rose et on les ajoute dans la file.

La case 0 n'est pas à nouveau mise dans la file car lors de son traitement le sommet est devenu bleu or seul les sommets gris (et voisins de la case en cours de traitement) sont mis dans la file et deviennent rosés.

1 devient bleue.

Exemple du parcours en largueur : étape 2
Traitement de 1.

Contenu de la file : 2 3.


Traitement de 2.

On défile la tête de la file 2, une seule case voisine en gris et relié à 2, la case en dessous (4) de 2.

On a fini le traitement de 2, sa couleur devient alors bleue.

Exemple du parcours en largueur : étape 3
Traitement de 2.

Contenu de la file : 3 4.


Traitement de 3.

On défile 3 de la file, la case 3 a deux voisins non bleu et qui lui sont reliés, la case de droite (4) qui est déjà coloriée en rose et la case du bas (5) qui est encore grise.

Or seules les cases grises sont mis dans la file et coloriées en rose. Donc seule la case du bas (5) devient rosé et est ajouté à la file.

Aucun voisin de 3 restants, on colorie 3 en bleue.

Exemple du parcours en largueur : étape 4
Traitement de 3.

Contenu de la file : 4 5.


Traitement de 4.

On colorie donc la case du dessous (6) en rose et on l'ajoute à la file.

4 devient bleue.

Exemple du parcours en largueur : étape 5
Traitement de 4.

Contenu de la file : 5 6.


Traitement de 5

On passe à la case 5, on la défile, on ajoute son voisin 7 à la file. La case de droite (6) étant rosée elle n'est pas ajouté à la file, et 3 étant bleue, elle non plus n'est pas ajoutée.

5 devient bleue.

Exemple du parcours en largueur : étape 6
Traitement de 5.

Contenu de la file : 6 7.

On s'arrête ici pour l'exemple. Mais voici un exemple d'exécution du parcours en largeur complet sur le graphe précédent pour trouver le plus court chemin de la case en haut à gauche à la case verte :

Fonctionnalités :

  • Cliquer sur l'image ci-dessus pour lancer le parcours ou faire pause
  • Cliquer pour relancer une génération à la fin de la précédente
  • Rester appuyé pour accélérer
  • touche r pour relancer avant la fin

Représentation du parcours en largeur :

  • Cases bleues -> Sommets traités
  • Cases rosées -> Sommets dans la file
  • Cases rouges -> Plus court chemin

Les numéros correspondent aux dates de découverte des sommets.

Pseudo-code

  • G :  le graphe
  • s : le sommet depuis lequel commence le parcours
  • couleur[] : un tableau des couleurs des sommets afin de les distinguer lors du parcours
ParcoursLargeur (G,s) 
 debut

 pour chaque sommet x != s faire 
     couleur [x] = gris ; 
 fait ;
 //initialement tous les sommets sont grises sauf s 
 couleur [s] = rosé ;
 enfiler (F,s) ;
 tant que F non vide faire   
     x = ExtraireTete(F) ; 
     afficher(x) ; 
     pour chaque y voisin de x faire 
     si couleur[y] == gris alors 
         couleur[y]=rosé ; 
         enfiler(F,y) ; 
     fin si ; 
     couleur[x]=bleu ; 
 fait ; 
 fin.  

L'algorithme

Trouver un des plus court chemin revient donc à trouver un chemin entre l'entrée et la sortie avec le minimum de cases parcourues possible.

Le parcours en largeur de la grille entre la case de départ et le MathSignal nous permet de trouver le plus court chemin, puisque on explore les cases par niveau et on s'arrête si on atteint le MathSignal.

Il suffit donc de récupérer le chemin utilisé pour trouver la distance minimale. Ainsi si on découvre le sommet s par le sommet u alors on se rappelle que u est le prédécesseur de s. On parle de forêt de parcours.

On récupère alors le prédécesseur du mathsignal est on recommence sur son prédécesseur jusqu'à arriver au sommet de départ.

Pseudo-Code

tableParcours : la forêt du parcours, à la découverte de chaque sommet on enregistre son prédécesseur.
Dist : la table des distances entre les sommets et la case de départ.
P : une pile pour sauvegarder le chemin (une structure LIFO "Last In First Out " )

ParcoursLargeur (G,s) 
 debut
 pour chaque sommet x != s faire 
     couleur [x] = gris ; 
     tableParcours[x] = nil ;
     Dist[x]=nil ;
 fait ;
 //initialement tous les sommets sont gris sauf s 
 couleur[s]=rosé ; 
 tableParcours[s]= nil ; 
 Dist[s] =0 ;
 enfiler (F,s) ; 
 tant que F non vide faire   
     x = ExtraireTete(F) ; 
     afficher(x) ; 
     pour chaque y voisin de x faire 
         si (couleur[y] == gris) alors 
             couleur[y] = rosé ; 
             Dist [y] = Dist [x] +1 ;
             tableParcours[y] = x ;
             enfiler(F,y) ; 
        fin si ; 
     fait ;
     couleur[x]=bleu ; 
 fait ;
 fin.   
MathGPS (G, s) 
 //s est le sommet de départ
 debut
 ParcoursLargeur (G,s);
 x = MathSignal ; 
 tant que tableParcours[x] est non vide faire 
     empiler(P, x);
     x = tableParcours[x];
 fait;
 tant que P non vide faire 
    dépiler(P,x);
    afficher(x);
 fait;
fin.

Exemple aléatoire

Fonctionnalités :

  • Cliquer sur l'image ci-dessus pour lancer le parcours ou faire pause
  • Cliquer pour relancer une génération à la fin de la précédente
  • Rester appuyé pour accélérer
  • touche r pour relancer avant la fin

Représentation du parcours en largeur :

  • Cases bleues -> Sommets traités
  • Cases rosées -> Sommets dans la file
  • Cases rouges -> Plus court chemin

Les numéros correspondent aux dates de découverte des sommets.

Faire Son propre Graphe

Mode édition (si pas de parcours en cours) :

  • s pour lancer le parcours
  • cliquer proche du bord des cases pour ajouter/enlever des murs (cliquer proche d'un coin permet d'ajouter deux murs à la fois) .
  • r pour réinitialiser le graphe

Mode parcours :

  • Cliquer pour faire pause
  • Cliquer pour revenir au mode édition à la fin du parcours
  • Rester appuyé pour accélérer
  • r pour repasser en mode édition

5. Au pire cas

Mathman veut être prêt à toutes éventualités.

Combien de temps mon MathGPS prend au maximum pour calculer le chemin le plus court ?

Nous allons pour cela séparer l'algorithme en deux parties :

  • L'initialisation
  • Le traitement des sommets

Complexité de l'initialisation ?

  pour chaque sommet x != s faire 
     couleur [x] = gris ; 
     tableParcours[x] = nil ;
     Dist[x]=nil ;
 fait ; 
 tableParcours[s]= nil ; 
 Dist[s] =0 ; 

Durant l'initialisation nous devons parcourir l'ensemble des sommets pour notamment leur donner la couleur grise, on a alors une complexité de :

O(|S|)

|S| étant le nombre de sommets

Combien de fois peut-on traiter un sommet ?

 enfiler (F,s) ; 
 tant que F non vide faire   
     x = ExtraireTete(F) ; 
     afficher(x) ; 
     pour chaque y voisin de x faire 
         si (couleur[y] == gris) alors 
             couleur[y] = rosé ; 
             Dist [y] = Dist [x] +1 ;
             tableParcours[y] = x ;
             enfiler(F,y) ; 
        fin si ; 
     fait ;
     couleur[x]=bleu ; 
 fait ; 

Au début de son traitement le sommet est colorié en rose puis en bleu lors de la fin de son traitement, or le sommet ne pourra jamais être remis en rose ou gris, ainsi les sommets ne peuvent être traité qu'une seule fois.

Ici nous prenons en compte le pire cas où tous les sommets sont accessibles depuis le point de départ et l'arrivé est découvert en dernier. Donc on aurait une complexité de :

O(|S|)

Mais pour chaque sommet on parcourt les arêtes reliées à celui-ci, il est donc plus précis de calculer la complexité du traitement en nombre de fois où l'on observe une arête.

Combien de fois observe-t'ont une arête ?

Chaque arête relie deux sommets, qui sont traités une fois chacun lors du parcours ainsi nous voyons une arête deux fois ce qui donne une complexité de 2*|A| (|A| étant le nombre d'arêtes), à une constante près (2) on obtient donc une complexité de :

O(|A|)

Conclusion

On additionne la complexité de l'initialisation des sommets et celle du parcours de graphe pour obtenir une complexité de :

O(|S|+|A|)

Dans Une GRILLE

Dans une grille de hauteur h et de longueur l, on a :

  • |S| vaut l*h
  • |A| est très proche de |S|, chaque sommet a au maximum 4 arêtes sortantes correspondant aux 4 directions. Or chaque arête est comptée deux fois car elle relie deux sommets entre eux. On a alors 4*|S| = 2*|A| et donc |A| = 2*|S| dans le pire des cas.

La complexité étant O(|S|+|A|) avec |S| = l*h et |A| = 2*|S| = 2*l*h, on obtient donc 3*l*h au total.

À une constante près (3), on obtient la complexité :

O(l*h)

Un temps linéaire ce qui est une très bonne complexité.

6. Algorithme naïf

Rhobin

Rhobin est en retard et a oublié son MathGPS!
Il veut toujours prendre le chemin le plus court mais utilise sa vielle MathCarte pour le trouver.

Rhobin sera-t-il là à temps ?

Pour trouver le chemin le plus court Rhobin va lister tous les chemins possibles (même bloqués) ne revenant jamais en arrière puis il enlève tous les chemins bloqués et calcule la taille des chemins restants pour trouver le chemin le plus court. Le but de Rhobin est de trouver le temps que prendra le calcul de son plus court chemin.

Ensemble des chemins

L'algorithme de Rhobin nécessite de lister tous les chemins.

La longueur d'un chemin est au maximum l*h (étant le nombre de cases dans la grille) si on ne repasse pas deux fois par la même case.

Or on sait que le nombre de chemins est borné par 3l*h, on doit donc construire au maximum 3l*h chemins de taille maximum l*h.

On peut considérer que la complexité d'ajout d'un sommet au chemin est un, on obtient alors la complexité :

O(l*h*3l*h )

Parcours de Chemin

Il reste alors à parcourir tous ces chemins pour trouver les chemins valides et la longueur de ces chemins.

Ici on parcourt l'ensemble des chemins possible :

Or comme dans la partie précédente on a au maximum 3l*h*l*h parcours de case avec une complexité de 2 pour les opérations suivantes :

  • On doit vérifier que l'arête suivante n'est pas un mur
  • On incrémente la taille du chemin

On obtient alors la complexité :

O(l*h*3l*h )

Complexité

Avant de parcourir l'ensemble des chemins, on doit appeler l'algorithme calculant l'ensemble des chemins, on obtient donc la complexité l*h*3l*h + l*h*3l*h , ce qui donne la complexité :

O(l*h*3l*h )

Rhobin n'arrivera jamais à temps, avec une telle complexité ! En effet la complexité O(l*h*3l*h ) est bien plus haute que la complexité de O(l*h) du parcours en largeur, ce qui montre bien l'intérêt de celui-ci.

7. Algorithme A*

Mathman observe que l'algorithme du parcours en largeur doit regarder la plus part des cases pour trouver le plus court chemin dans la grille. Mathman voudrait trouver un algorithme qui ne demande pas de parcourir autant de case pour trouver le plus court chemin.

Comment faire mieux que le parcours en largeur ?

Pour cela nous utiliserons un algorithme utilisant la distance euclidienne.

Definition

Distance euclidienne : il s'agit de la distance entre deux points dans un plan, ici les points sont les cases.

Principe

Et si l'algorithme savait la distance euclidienne de chaque case vers la case d'arrivé ? On pourrait donc prendre la case accessible dont la distance est la plus faible.

Il s'agit du principe de l'algorithme A* ! Nous n'en parlons pas d'avantage ici, mais nous vous laissons un lien dans la bibliographie pour approfondir le sujet.

Bibliographie

45 Cliquer pour recommander cet article