Discussion :

[scienceapart]

Bonjour à tous,

je suis étudiant en deuxième année de prépa, j'ai un projet qui consiste à créer un algorithme permettant de trouver le chemin le plus court pour n'importe quel labyrinthe et de tracer ce chemin. Je me dois me servir de MATLAB et j'ai un polycopié d'une centaine de pages pour les nombreuses fonctions du logiciel.

Le labyrinthe est associé à une matrice (L x C) composée de 0 et de 1 d'où les 0 représentent le passage et les 1 représentent un mur.

Exemple :

1 0 1 1 1
1 0 0 0 1
1 0 1 1 1
1 0 0 0 1
1 1 1 0 1

L'entrée est toujours en bas à droite et la sortie en haut à gauche et des murs sont toujours situés autour du labyrinthe.

Enfin j'ai peu ou pas d'expériences en création d'algorithme. J'ai commencé à faire ceci mais après je ne vois pas comment faire la suite. Il y a des algorithmes existants sur les résolutions des labyrinthe comme A* mais je ne vais pas "pomper" ces algorithmes. Je vous demande juste de me donner des pistes pour que je puisse me débrouiller par la suite.

Voici le début de mon algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function Y=cheminlepluscourt(X)
 
[n p]=size(X); %Ceci permet de connaitre la longueur et la largeur de la matrice (du labyrinthe).
 
if p<=3
    Y='impossible'; %Si le nombre de colonnes est inférieur ou égale à 3, la résolution est impossible.
elseif n<=3
    Y='impossible'; %Si le nombre de ligne est inférieur ou égale à 3, la résolution est impossible.
else
 
    X(1,2)=2; %On affecte la sortie du labyrinthe par 2.
    X(n,p-1)=3; %On affecte l'entrée du labyrinthe par 3.
    [x y]=find(X==3); %On affecte x et y comme coordonées de l'entrée du labyrinthe.
end

X est associé à la matrice du labyrinthe qu'on pourrait nous donner.

Je vous remercie d'avance.

[Myrne]

Il faut te poser plusieurs questions pour résoudre ce type de problème. Tout d'abord, sans parler de trouver la meilleure solution, comment trouverais-tu une solution ?

Ce qui me vient à l'idée comme ça:
- Parcourir ton tableau et trouver toutes les impasses: ce sont les cases remplies d'un 0 et où il n'y a qu'un seul zéro dans les cases alentours. Attention à ignorer l'entrée et la sortie dans cette recherche, elles pourraient être considérées comme des impasses.
Une fois les impasses trouvées, les remplacer par des murs et relancer la même recherche jusqu'à ne plus en trouver, les zéros restants mèneront donc forcément de l'entrée à la sortie.
C'est une méthode qu'on pourrait utiliser à la main sur les labyrinthes très grands, en raturant les impasses que l'on voit pour avoir une meilleure visibilité sur les chemins possibles

- "Tourner tout le temps à droite". C'est la méthode que l'on utiliserait si l'on était dans un labyrinthe nous même (et donc ne verrions pas l'intégralité des chemins possibles). à chaque intersection rencontrée, prendre à droite, regarder si ça mène quelque part. Si ce n'est pas le cas, retourner à l'intersection précédente et recommencer de là.
En informatique, ce serait (je crois) la notion de backtracking, tu peux chercher ça sur google, il y a quelques tutoriels pour bien comprendre ce que c'est (méthode de résolution des sudokus ou du problème des 8 reines).


Ensuite, tu peux simplifier ton problème: les bords de ton labyrinthe on l'air d'être forcément des murs (à part l'entrée et la sortie), tu pourrais donc les retirer de ton tableau et ne travailler que sur la matrice intérieure. Le but serait alors d'aller de la case (n,c) à la case (1,1).

Enfin, si tu arrives à trouver une solution, tu pourras étudier des moyens d'optimiser la solution. Il me semble que le backtracking serait plus adapté pour lister toutes les solutions possibles, au lieu d'arrêter la recherche quand tu sors du labyrinthe, tu enregistre la solution trouvée et tu reprends à l'intersection précédente, et ainsi de suite jusqu'à avoir tout trouvé. Il ne te reste alors qu'à comparer la taille de toutes les solutions.


EDIT: pour l'idée de tourner tout le temps à droite, il faudrait auparavant :
- trouver toutes les intersections et le nombre de routes y arrivant (3 ou 4 pour un truc en 2D)
- trouver les relations entre ces intersections: "l'intersection 2 est reliée à la 3 et la 4, l'intersection 8 est reliée à la 10, la 9 est reliée à la sortie" et les enregistrer, avec éventuellement la distance entre chacune de ces intersections
- En déduire comment tu pourras parcourir ton labyrinthe avec uniquement les informations des liaisons entre les intersections.

[scienceapart]

C'est pas une si bête idée la première que tu m'as donnée. Après le soucis c'est de pouvoir exprimer cette idée en algorithme. Je te remercie d'avoir consacré ton temps à me donner une réponse. Si jamais j'ai encore un soucis, je repasserai.

[scienceapart]

Bonjour,

au fait j'ai toujours du mal à commencer mon algorithme ! :s

[Myrne]

Alors je suppose que tu es parti sur la première idée. Dans ce cas il va te falloir parcourir tout ton tableau. Pour ça, deux boucles for imbriquées feront l'affaire (tu connais les tailles de ton tableau donc ça ne posera pas de problèmes).

Ensuite, pour tester la valeur de la case, un if fera l'affaire. (si tu devais avoir différentes action en fonction de la nature de la case, renseigne toi sur la fonction "switch")

Enfin, pour tester si la case est une impasse, un if devrait suffire. S'il y a plusieurs conditions (comme c'est le cas ici), le "ou" logique se traduit par ||, le "et" par &&.

ça donnerait donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
for i=1:n
   for j=1:p
 
      if X(i,j)==0 && testvoisins(X,i,j)
         %modification de la case
      end
   end
end

la fonction testvoisins renverrai OK si la case est une impasse. Tester un truc du genre la somme des cases voisines est égale à 3, en vérifiant qu'il n'y a pas l'entrée ou la sortie dans ces cases (étant donné que tu a mis une valeur différente pour ces deux cases).

Il serait probablement plus prudent de créer une copie du tableau et de modifier cette copie. Si tu modifie le tableau au fur et à mesure de son analyse, tu risques de faire des erreurs. Attention aussi aux conditions de bord qui se traiteront différement.

[scienceapart]

D'accord. Je vois ce que tu veux dire. Quand tu met testvoisin, ça veut dire que je dois faire différents cas si un 1 est à droite de la position, un 1 en haut etc... Dans ce cas, je dois utiliser switch, non ?

[Myrne]

non switch ne me parait pas le plus adapté.

Déjà dans ton programme, différencier la sortie (et l'entrée) d'une case empruntable (un zéro) ne me parait pas une bonne idée, ça ne ferait que compliquer la chose. Si l'entrée et la sortie sont forcément en bas à droite et en haut à gauche, tu n'as pas besoin de les différencier.

Ce que je ferai est simplement un truc du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 testvoisins=(X(i+1,j)+X(i-1,j)+X(i,j+1)+X(i,j-1)==3)

ça ce serait pour une case à l'intérieur du labyrinthe. Pour déterminer les conditions de bord, soit tu les ignores directement si tu n'as pas enlevé les bords de ta matrice, soit tu fais différents cas:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
if i==1 && j>1 && j<p
   testvoisins=%à compléter
else if i==n && j>1 && j<p
   testvoisins=%àcompléter
else if j==1
   testvoisins=%à compléter
else if j==p
   testvoisins=%à compléter
else testvoisins=(X(i+1,j)+X(i-1,j)+X(i,j+1)+X(i,j-1)==3);
end

Je n'ai pas vérifié que mes n et p correspondaient bien aux tiens, à toi de t'en assurer =)

EDIT: j'm'a trompé dans les conditions, ça ne couvre pas tous les cas, mais tu devrais savoir tous les trouver. N'hésite pas à faire des if imbriqués pour plus de lisibilité.

[scienceapart]

Ah d'accord, je vois ! Merci, je vais essayer de continuer. Je repasserai si soucis. Merci encore !

[Myrne]

Bon je dois bien avouer que ton programme de résolution de labyrinthe m'intéresse, par curiosité principalement. Je me suis penché un peu sur la question et une autre idée m'est venue, très bête et que je ne saurais pas trop comment mettre en place, mais l'idée me plaît alors je vais essayer ce soir, si ça t'intéresse je t'en reparle demain.

L'idée serait de faire couler de l'eau dans le labyrinthe. L'eau passerait par les chemins menant à la sortie, en remplissant éventuellement au passage les impasses. Passé un certain nombre d'itérations (au maximum le nombre de cases empruntables), l'eau sortirait de l'autre côté et il suffirait alors de regarder le chemin emprunté par l'eau courante : ce serait le chemin le plus court.

[scienceapart]

non switch ne me parait pas le plus adapté.

Déjà dans ton programme, différencier la sortie (et l'entrée) d'une case empruntable (un zéro) ne me parait pas une bonne idée, ça ne ferait que compliquer la chose. Si l'entrée et la sortie sont forcément en bas à droite et en haut à gauche, tu n'as pas besoin de les différencier.

Ce que je ferai est simplement un truc du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 testvoisins=(X(i+1,j)+X(i-1,j)+X(i,j+1)+X(i,j-1)==3)

ça ce serait pour une case à l'intérieur du labyrinthe. Pour déterminer les conditions de bord, soit tu les ignores directement si tu n'as pas enlevé les bords de ta matrice, soit tu fais différents cas:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
if i==1 && j>1 && j<p
   testvoisins=%à compléter
else if i==n && j>1 && j<p
   testvoisins=%àcompléter
else if j==1
   testvoisins=%à compléter
else if j==p
   testvoisins=%à compléter
else testvoisins=(X(i+1,j)+X(i-1,j)+X(i,j+1)+X(i,j-1)==3);
end

Je n'ai pas vérifié que mes n et p correspondaient bien aux tiens, à toi de t'en assurer =)

EDIT: j'm'a trompé dans les conditions, ça ne couvre pas tous les cas, mais tu devrais savoir tous les trouver. N'hésite pas à faire des if imbriqués pour plus de lisibilité.

Tu a déterminé les conditions en tenant compte des bords du labyrinthe ou non ?

[Myrne]

Non l'exemple que j'ai donné là c'est quand il n'y a pas les bords (les murs exterieurs) du labyrinthe. Dans ce cas, les bords ont des conditions particulières puisque tu n'as que 3 cases à vérifier (la dernière sort du tableau et fait planter le programme :p) voire deux si tu es dans un coin. C'est probablement mieux de garder les murs extérieurs de ce point de vue là.

[scienceapart]

J'ai essayé ceci et ça donne rien, enfin juste la matrice G que j'ai définie (la matrice du labyrinthe que j'ai fait comme exemple sans les murs extérieurs) pour tester et les testvoisins avec des valeurs différentes (0 ou 1) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
function Y=cheminlepluscourt(X)
 
[n p]=size(X); %Ceci permet de connaitre la longueur et la largeur de la matrice (du labyrinthe).
 
if p<=3
    Y='impossible'; %Si le nombre de colonnes est inférieur ou égale à 3, la résolution est impossible.
elseif n<=3
    Y='impossible'; %Si le nombre de ligne est inférieur ou égale à 3, la résolution est impossible.
else
    G=X(2:n-1,2:p-1);
    [l c]=size(G);
 
    for i=1:l
        for j=1:c
 
            if i==1 && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i+1,j)==3;
            elseif i==l && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i-1,j)==3;
            elseif j==1 && i>1 && i<l
                testvoisins=G(i,j+1)+G(i+1,j)+G(i-1,j)==3;
            elseif j==c && i>1 && i<l
                testvoisins=G(i,j-1)+G(i+1,j)+G(i-1,j)==3;
            elseif i>1 && i<l && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i+1,j)+G(i-1,j)==3
 
               if G(i,j)==0 && testvoisins
                G(i,j)=1;
               end
            end  
        end
    end
    G
end

Ca remplace pas les 0 par des 1 lorsqu'il y a une impasse.

Résultat :

testvoisins =

0


testvoisins =

0


[...]


testvoisins =

1


testvoisins =

1


G =

0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0

Sachant que le G donné reste le même qu'avant.

[Myrne]

Je n'ai pas vérifié les opérations dans tes if/else, mais il te manque les cas pour les quatres coins: i==1 && j==1, i==1 && j==L...

Ensuite, la tu parcours toutes tes cases en modifiant au fur et à mesure. Mais une fois que tu as fait une passe, il faut que tu en refasses une autre, puisque des cases qui étaient auparavant des chemins sont devenues des impasses. Il faut refaire des passes jusqu'à ce que le labyrinthe ne soit plus modifié. Je te laisse déterminer comment faire cette condition, elle est plutôt simple. Cela s'implémentera avec un while(...)

[scienceapart]

J'ai planté le while mais ça rend MATLAB occupé pendant des siècles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function Y=cheminlepluscourt(X)
 
[n p]=size(X); %Ceci permet de connaitre la longueur et la largeur de la matrice (du labyrinthe).
 
if p<=3
    Y='impossible'; %Si le nombre de colonnes est inférieur ou égale à 3, la résolution est impossible.
elseif n<=3
    Y='impossible'; %Si le nombre de ligne est inférieur ou égale à 3, la résolution est impossible.
else
    G=X(2:n-1,2:p-1);
    [l c]=size(G);
 
    for i=1:l
        for j=1:c
          while X(i,j)==0 
            if i==1 && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i+1,j)==3;
            elseif i==l && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i-1,j)==3;
            elseif j==1 && i>1 && i<l
                testvoisins=G(i,j+1)+G(i+1,j)+G(i-1,j)==3;
            elseif j==c && i>1 && i<l
                testvoisins=G(i,j-1)+G(i+1,j)+G(i-1,j)==3;
            elseif i>1 && i<l && j>1 && j<c
                testvoisins=G(i,j+1)+G(i,j-1)+G(i+1,j)+G(i-1,j)==3;
            elseif i==1 && j==1
                testvoisins=G(i,j+1)+G(i+1,j)==2;
            elseif i==1 && j==c
                testvoisins=G(i,j-1)+G(i+1,j)==2;
            elseif i==l && j==1
                testvoisins=G(i,j+1)+G(i-1,j)==2;
            elseif i==l && j==c
                testvoisins=G(i-1,j)+G(i,j-1)==2;
                if G(i,j)==0 && testvoisins
                G(i,j)=1;
                end 
            end  
          end
        end
    end
    G
end

[Myrne]

Normal. ce qu'il faut que tu vérifies, c'est si le labyrinthe initial (avant d'avoir parcouru toutes les cases) est identique au labyrinthe final (après les avoir toutes parcourues).
Là tu attends que ta case où il y a un zéro devienne un un. Si tu boucles sans cesse dessus sans modifier les autres cases, ça ne peut pas marcher.

[scienceapart]

Je ne comprends pas vraiment.

[maleaume]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
main()
{
	for (tout mes pixel x,y)
		if(Image(x,y) == 0)
			DeleteDeadLock(x,y);
}
 
//return 0 si c est pas uneimpasse
//sinon return 1,2,3,4 pour la position du zero pour la prochaine recursion
//1 en haut, 2 a droite,3 en bas , 4 a gauche.
void DeleteDeadLock(int x, int y)
{
	int result = 0;
	int sum = 0;
	//regarde le pixel du dessus:
	if(Image(x+(y-1)*sizeX) == 0 )
		result = 1;
	else
		sum++;
 
	//regarde a droite:
	if(Image(x+1 + y*sizeX) == 0)
	   if(result!= 0) return;  //on a deja trouver un 0, donc 2 zero ce n est //pas une impasse pas la peine de continuer
	   else result = 2;
	else 
		sum++;
 
	//regarde en bas:
	if(Image(x + (y+1)*sizeX) == 0)
	   if(result!= 0) return;
	   else result = 3
	else 
		sum++;
 
	//regarde a ghauche:
	if(Image(x-1 + y*sizeX) == 0)
	   if(result!= 0) return;
	   else result = 4
	else 
		sum++;
 
	//en toute logique si on arrive ici, 
	//c est que c est une impasse donc 3 pixel a 1 et 1 pxl a 0
	if(sum == 3 && result!=0)
		{
			Image(x,y) = 1;
			switch(result)
			{
			  case 1: DeleteDeadLock(x,   y-1); break;
			  case 2: DeleteDeadLock(x+1, y);break;
			  case 3: DeleteDeadLock(x,   y+1);break;
			  case 4: DeleteDeadLock(x-1, y);break;
			}
		}
	else return;
 
}

j ai tapper ca vite fait, en utilisant un algo recursif,ce code devrait en toute logique t effacer une a une les impasses de ton labyrinthe. des qu il va trouver un point correspondant a une impasse, il va remonter la "route" jusqu a une intersection et te mettre des 1 a la place des 0.

une fois qu il n y a plus de point "impasse", il ne doit rester que le seul et unique chemin menant du point A au point B

[scienceapart]

Je te remercie maleaume de ton aide. Mais que fait sum++ dans l'algo ?

[maleaume]

ca m assure de bien avoir 3 pixel a 1:

a la fin cest ma condition sum ==3

[maleaume]

en toute logique si on arrive jusqu au if(sum == 3) on est toujours assurer d avoir cette condition vrai, et effectivment incrementer sum n a plus d interet.
C est justeen cas de debug pour tes test.

apres tu pourra virer le

else
sum ++;