Graphe
Un graphe est constitué par un ensemble d'objets (représenté par des sommets) reliés entre eux par des liens (les arrêtes du graphes).
Un graphe permet de représenter le réseau ferroviaire, le réseau internet, un labyrinthe ou certains problèmes de choix de chemins.
I)L'EXEMPLE DU BERGER
Le problème : Un berger près d1 rivière possède une chèvre, un chou et un loup. Le berger doit faire passer un a un ces 3 derniers de l'autre côté de la rivière par barque.
CONDITIONS:
-Sans berger :
*chèvre et loup seuls = le loup mange la chèvre
*chou et chèvre seuls = la chèvre mange le chou
-En présence du berger : personne ne mange
t=0 tfinal
RIVE ARRIVÉE rien B + L + C + Cx
___________________________________________________________
RIVIÈRE
___________________________________________________________
RIVE DÉPART Berger+Loup+Chèvre+Chou rien
B + L + C + Cx
IL y a 16 situations possibles. Chaque état sera simplement écrit grâce au personnages présents sur la rive de départ.
LISTE DES ÉTATS INTERDITS :
L/C
C/Cx
B/Cx
B/L
(4 situations interdites)
SOLUTION:
II)COMMENT SORTIR D'UN LABYRINTHE ?
Les intersections sont les sommets du graphe et sont repérées par des lettres. Les couloirs sont les arrêtes.
Parcours en largeur :
1- A
2- AB
3- ABC
ABM
4- ABCD
ABCK
ABM (On ne peut prolonger qu'1 seul point en même temps dans une étape)
5- ABCD
ABCK
ABMN Impasse
ABMZ // solution
Le parcours en largeur permet de trouver le chemin le plus court pour sortir du labyrinthe.
Parcours en profondeur :
1- A
2- AB
3- ABC
ABM
4- ABCD
ABCK
ABM (On ne peut prolonger qu'1 seul point en même temps dans une étape)
5- ABCDE
ABCDK éliminé car K est reutilisé
ABCK
ABM
6- ABCDEF éliminé car Impasse
ABCDEG
ABCK
ABM
7- ABCDEGH éliminé car Impasse
ABCDEGI
ABCK
ABM
8- ABCDEGIJ éliminé car Impasse
ABCK
ABM
9- ABCKD éliminé car comme on l'a vu avant il va y avoir que des impasses après
ADCKL éliminé car Impasse
ABM
10-ABMN éliminé car Impasse
ABMZ