NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

D
É
C
O
N
N
E
C
T
É

Les graphes

1 - La théorie des graphes :

Les graphes sont employés par exemple par les GPS pour trouver le chemin le plus court entre deux villes

villes   

On a des sommets et des arrêtes ou arcs si la liaison n'est pas bidirectionnelle. Les sommets de notre graphe se sont les villes, les arrêtes représentent le poids : ici, la distance séparant deux villes entre elles.

Pour aller à Mulhouse à Nancy, quel sera le chemin le plus court :

Les successeurs de Mulhouse sont : Strasbourg, Nancy, Epinal et Vesoul

Les prédécesseurs de Vesoul sont : Nancy, Epinal et Mulhouse qui sont également ses successeurs.

Pour trouver le chemin le plus court dans ce graphe il existe l'algorithme de Dijkstra ou Prim traité à la fin du chapitre.

1.1 - Matrice d'adjacence :

Oublions un moment le poids des arrêtes. La matrice d'adjacence permet de répertorier les prédécesseurs et les successeurs de chaque sommet. De Strasbourg je peux aller directement vers Mulhouse, Epinal ou Nancy mais pas Vesoul. Donc Mulhouse, Epinal et Nancy sont les successeurs de Strasbourg. On place la valeur 1 si c'est le successeur, 0 si ce n'est pas le successeur. On obtient la matrice suivante :

matrice      ligne       pre
       Matrice d'adjacence               recherche des successeurs          recherche des prédécesseurs

Pour connaître :

  • Son successeur, on sélectionne la ligne puis les successeurs marqués par la valeur 1 se trouvent dans les colonnes : Vesoul a pour successeurs Mulhouse, Epinal et Nancy
  • Son prédécesseur, on sélectionne la colonne puis les prédécesseurs marqués par la valeur 1 se trouvent dans les lignes : Strasbourg a pour prédécesseurs Mulhouse, Epinal et Nancy

1.2 - PILES et FILES : LIFO / FIFO

pile

Dans les piles, on empile les données commne une pile de livres

La première donnée qui sortira de la pile sera la dernière empilée

LIFO : Last In First Out
file

Dans une file, on enfile les données les unes après les autres

La première donnée qui sortira de la file sera la première enfilée.

FIFO : First In First Out

A partir de notre graphe des villes on peut constituer la file des successeurs FS :

Commençons par Mulhouse comme sommet en se référant à la matrice d'adjacence, Mulhouse a pour successeurs Strasbourg, Vesoul, Epinal et Nancy et c'est tout (-).

On enfile les autres lignes de ma matrice d'adjacence et obtient la file FS suivante :

file

Il est conseillé de construire une liste APS contenant les Adresses des Premiers Successeurs.

Traitement des piles avec python



Traitement des files avec python





1.3 - Parcours des graphes en largeur

Cette fois, on construit la matrice qui permet de donner le nombre d'arrêtes minimales séparant deux sommets

matrice              graph

Partons de Strasbourg : On marque le sommet pour indiquer qu'il a été visité puis on cherche les voisins. On marque les voisins et progressivement on enlève les arrêtes des sommets déjà visités. Quand tous les sommets sont marqués on obtient un arbre. Si On recommence en partant d'un autre sommet (ville) on aura un arbre différent.

 
A partir d'un nœud source S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire.

Étapes de l'algorithme :

   1. Mettre le nœud source dans la file.
   2. Retirer le nœud du début de la file pour le traiter.
   3. Mettre tous les voisins non explorés dans la file (à la fin).
   4. Si la file n'est pas vide reprendre à l'étape 2.

Note : l'utilisation d'une pile au lieu d'une file transforme l'algorithme du parcours en largeur en l'algorithme de parcours en profondeur. 

Vidéo : introduction-aux-graphes

2 - MISE EN PRATIQUE

On désirer trouver le chemin le plus court pour sortir d'un labyrinthe la distance séparant chaque sommet de son voisin est 1.

laby    carte

Le joueur (j) se trouve sur le sommet n°9 et la sortie (s) est au n°32

Le graphe partiel du labyrinthe est le suivant :

grapheLaby

Matrice d'adjacence partielle du labyrinthe :


 9 
10 11 12 13 18 20 21 25 26 29 32 33 34 35 36 37
9 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
11 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
13 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
18 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
20 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
21 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
25 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
26 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0
29 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
32 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
33 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0
34 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0
35 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
37 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0

fs

2.1 - Codage de la fonction liste_sommets

Télécharger puis décompresser le fichier Labyrinthe.zip. Ouvrir le fichier Labyrinthe_EL.py et ajouter y les fonctions permettant de trouver le chemin le plus court vers la sortie, en appliquant la théorie les graphes.

Ajouter une fonction liste_sommets() qui retourne la liste des sommets à partir des coordonnées des cases espace, du joueur et de la sortie. La fonction recherche(objet) renvoie une liste contenant les coordonnées des objets recherchés : espace, j ou s. Le nombre de colonnes est stocké dans la variable larg_laby.

carte

L'exécution de la fonction recherche('j') renvoie [(2,1)]. Trouver un calcul simple ( * et + ) utilisant les coordonnées x et y de j et la largeur de labyrinthe stockée dans la variable larg_laby permettant de calculer le n° du sommet : donc 10 dans le labyrinthe ci-dessus.

Algorithme

Fonction liste_sommets   
paramètres :
aucun
Résultat :
Liste contenant les n° des sommets des cases espace, du joueur et de la sortie
DEBUT
sommets ← []
coordonnees ← liste retournée par la recherche de la case du joueur 'j'
ajouter à la coordonnees la liste retournée par la recherche des cases espaces ' '
ajouter à la coordonnees la liste retournée par la recherche de la case sortie 's'
pour chaque coordonnee se trouvant dans la liste des coordonnees
calculer le numéro du sommet de la coordonnee
ajouter ce numéro de sommet dans la liste des sommets
retourne la liste des sommets
FIN
Ajoutez temporairement print(sommets) avant return
il faut trouver [9, 11, 12, 13, 14, 18, 20, 21, 22, 25, 26, 29, 30, 33, 34, 35, 36, 37, 38, 41, 42, 46, 49, 50, 51, 52, 53, 54, 10, 32]

2.2 - Matrice d'adjacence :

Si on prend le sommet n° 26 : les sommets adjacents sont ceux qui sont :
  • au-dessus : 26 - larg_laby
  • en-dessous : 26 + larg_laby
  • à gauche : 26 -1
  • à droite : 26+1
Fonction matrice_adjacence   
paramètres :
la liste des sommets
Résultat :
Liste contenant la matrice d'adjacence
DEBUT
matrice ← []
ligne ← []
Pour chaque sommet dans la liste des sommets
    Pour chaque som dans la liste des sommets
        si le sommet = som-1 ou sommet = som+1 ou sommet = som+larg_laby ou sommet = som-larg_laby
empiler 1 dans la liste ligne
sinon
empiler 0 dans la liste ligne
    empiler la ligne à la matrice
    ligne ← []
affiche_matrice(sommets,matrice) # appel de la fonction qui affiche la matrice pour vérifier le résultat
retourne matrice
Fin

2.3 - File des successeurs :

fs

Il faut donc parcourir la matrice d'adjacence ligne par ligne et rechercher les 1 qui correspondent aux sommets adjacents.
On ajoute ce sommet dans la liste FS et on ajoute 0 pour terminer les successeurs. Au passage on construit la liste APS (l'Adresse des Premiers Successeurs).

Algorithme

Fonction File_successeurs   
paramètres :
matrice : liste matrice d'adjacence
sommets : liste des sommets
Résultats :
FS : la liste contenant la file des successeurs
APS : la liste des adresses des premiers successeurs
DEBUT
FS ← []
APS ← []
pour i variant de 0 à la hauteur de la matrice
empiler la longueur de FS dans la liste APS
pour j variant de 0 à la largeur de la matrice
si matrice[i][j]=1
empiler sommets[j] à la liste FS
empiler 0 à la liste FS
empiler la longueur de FS dans la liste APS
retourne la liste des successeurs et les adresses des 1er successeurs
Fin

2.4- Parcours en largeur

On désire stocker la liste des sommets selon leur distance par rapport au nœud :

tab           arbre

Ex : pour le nœud 10, on souhaite générer une liste de l'arbre suivant : [[10],[9,18,11],[12,26],[13,20,25,34],[14,...],...]

Algorithme

Fonction parcours_largeur   
paramètres :
noeud : représente la case du joueur
Résultat:
arbre : liste contenant les distances du noeud à chaque sommet
Debut:

arbre ← [[noeud]]
file ← [0,noeud]
visites ← [] # liste des sommets déjà visités
Tant que la longueur de la file contient plus d'un élément
rang ← [] # liste qui permet de stocker les successeurs du sommet courant
Tant que le premier élément de la file est >0: # la valeur 0 permet d'indiquer la fin de la file courante
sommet ← défiler la file # sommet = file.pop()
Empiler le sommet à la liste visites
indice ← sommets.index(sommet) # recherche de la position du sommet courant dans la liste des sommets
pour i variant de APS[indice] à APS[indice+1]-1: # recherche des voisins du sommet dans FS en excluant 0
si FS[i] n'est pas dans la liste visites
Enfiler FS[i] dans rang # rang.insert(0,FS[i])
Enfiler FS[i] dans file
Empiler FS[i] dans visite
Défiler la file (qui doit être 0) # condition d'arrêt du tant que
Empiler à l'arbre la liste rang
Enfiler la valeur 0 dans la file
retourne la liste arbre
Fin

2.5 - Recherche du chemin vers la sortie

Chercher la case de sortie dans l'arbre puis trouver le prédécesseur dans la matrice d'adjacence. On la lira en sélectionnant la colonne et pour trouver la case dans la ligne.

Exemple le prédécesseur de 32 est 33 :

matrice arbre

Il peut y avoir plusieurs possibilités comme les prédécesseurs de 33 du niveau 3 de l'arbre qui en a deux : 25 et 34, on ne retiendra que le premier de l'arbre donc 25.

Algorithme :

Fonction chemin   
paramètres :
arbre
Résultat:
Liste : contenant le chemin le plus court vers la sortie
Début:
sortie ← rechercher dans la carte les coordonnées de la sortie 's'
case ← calculer le numéro de la sortie en fonction de la largeur de la carte
i ← 0
pour chaque rang de l'arbre # recherche de la colonne dans FS de chaque rang dans l'arbre
si la case sortie se trouve dans la liste rang
pos ← index case sortie dans la liste rang # Ex : pos=2 si case=32 rang=[50,36,32,...]
Arrêt
sinon
incrémenter i # Compter les rangs passés
indice ← index de case dans la liste des sommets # recherche des prédécesseurs du sommet trouvé
predecesseurs ← []
tant que i>1
j ← 0
pour chaque ligne de la matrice # On parcourt les lignes de la matrice
if ligne[indice]==1 et sommets[j] dans arbre[i-1]
Empiler sommets[j] à la liste predecesseurs
Arrêt
incrémenter j
décrémenter i
indice ← index de sommets[j] dans la liste des sommets
retourne predecesseurs
fin

Colez votre code python ci-dessous

Algorithme de recherche de chemin

Les algorithmes de recherche de chemin, travaillent sur des graphes pondérés (par exemple pour rechercher la route entre un point de départ et un point d'arrivée dans un logiciel de cartographie). Ces algorithmes recherchent aussi souvent les chemins les plus courts. On peut citer l'algorithme de Dijkstra ou encore l'algorithme de Bellman-Ford qui recherchent le chemin le plus court entre un noeud de départ et un noeud d'arrivée dans un graphe pondéré.

La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Dijkstra.

La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Prim.

Fond :  Texte :  Tables :  Thème du langage: