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 ?