Discussion :

[maleaume]

un algo recursif va s appeler lui meme jusqua une condition d arret

L idée de l'algo recursif est la suivante.
1) trouver un point qui verifie la ou les conditions "Etre une impasse".
2)une fois une impasse trouver remonter le chemin jusqu a une intersection et m arreter et continuer avec les autre impasse
une intersection n'est pas une impasse. ca sera la condition d arret de la recursion.


maintenant on definit ce qu est etre une impasse:
cest avoir la valeur 0, et etre entourer de trois 1 ou de un seul 0.
j opte pour le seul zero. car il va aussi me donner dans quelle direction mon chemin va pour lancer la recursion suivante.

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
    if(lab[x+(y-1)*N] == 0 )
		        result = 1;
 
	        //regarde a droite:
	        if(lab[x+1 + y*N] == 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;
 
 
	        //regarde en bas:
            if (lab[x + (y + 1) * N] == 0)
                if (result != 0) return;
                else result = 3;
 
	        //regarde a hauche:
	        if(lab[x-1 + y*N]== 0)
	           if(result!= 0) return;
	           else result = 4;

ce code regarde mes voisins, et regarde si ca vaut 0, si oui; je met result a 1,2,3 ou 4 ce qui me permet comme dit avant de savoir la direction a prendre apres.
mais si mon result est different de 0, c est que j ai deja trouver un 0 autour de mon point, ce qui fait que ce n est pas une impasse et donc je te poursuit pas l algo.

si le return n existe pas enmatlab utilise un booleen que tu met a true au debut, et a false a la place de mes return.



si je passe tout ces tests alors je fait ma recurrence

et ici tu peux ajouter avant, si monbooleen est == true, alors

Code :

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

1
2
3
4
5
6
7
8
9
 lab[x+y*N] = 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;
			        }

[scienceapart]

Aaaah d'accord ! Merci pour ton explication claire, désolé si je n'arrive pas à comprendre maleaume mais bon il y a peu de temps que je découvre MATLAB et coder aussi. Je vais voir ça alors. Merci à vous 2. Je reviens si soucis.

EDIT : ah désolé Maleaume, j'ai pas vu que tu avais posté ton commentaire.

[maleaume]

mais tu peux aussi revenir si ca marche
Edit: 2 commentaires valent mieux qu un

[scienceapart]

J'ai fait ça et ça me donne rien, je sais que je me suis trompé quelque part mais comme je suis une grosse m**** en retranscription de langage :

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
function X=testvoisins(X)
[n p]=size(X);
result=0;
function X=deletedeadlock(i,j)
        if X(i-1,j)==0
            result=1;
        if X(i,j+1)==0
            if result~=0
                return
            else result=2;
        if X(i+1,j)==0
            if result~=0
                return
            else result=3;
        if X(i,j-1)==0
            if result~=0
                return
            else result=4;
            end
        end
            end
        end
            end
        end
        end
end
for i=2:(n-1)
    for j=2:(p-1)
        switch result
            case 1
                X=deletedeadlock(i-1,j);
            case 2
                X=deletedeadlock(i,j+1);
            case 3
                X=deletedeadlock(i+1,j);
            case 4 
                X=deletedeadlock(i,j-1);
        end
    end
end
end

[maleaume]

suis pas un pro matlab mais plus comme cela

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
 
function X=testvoisins(X)
[n p]=size(X);
result=0;
 
for i=2:(n-1)
    for j=2:(p-1)
      ifX(i,j) ==0
 
function X=deletedeadlock(i,j)
 
          if X(i-1,j)==0
              result=1;
          if X(i,j+1)==0
              if result~=0
                  return
              else result=2;
         if X(i+1,j)==0
            if result~=0
                return
            else result=3;
        if X(i,j-1)==0
            if result~=0
                return
            else result=4;
            end
        end
            end
        end
            end
        end
        end
 
 
        switch result
            case 1
                X=deletedeadlock(i-1,j);
            case 2
                X=deletedeadlock(i,j+1);
            case 3
                X=deletedeadlock(i+1,j);
            case 4 
                X=deletedeadlock(i,j-1);
        end
    end
   end
end
end

[Myrne]

Tes 'end' sont mal placés, il faut les mettre à la fin de chaque if.
Tu ne demandes pas X en argument d'entrée de ta fonction, du coup je ne suis pas sûr qu'il puisse y accéder :

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
function X=deletedeadlock(X,i,j)
        result=0;
        if X(i-1,j)==0
            result=1;
        end
        if X(i,j+1)==0
            if result~=0
                return
            else result=2;
            end
        end
        if X(i+1,j)==0
            if result~=0
                return
            else result=3;
            end
        end
        if X(i,j-1)==0
            if result~=0
                return
            else result=4;
            end
        end
%pas de end ici, ta fonction n'est pas terminée, il te manque le switch

X(i,j)=1;
switch (result)
            case 1
                X=deletedeadlock(X,i-1,j);
            case 2
                X=deletedeadlock(X,i,j+1);
            case 3
                X=deletedeadlock(X,i+1,j);
            case 4 
                X=deletedeadlock(X,i,j-1);
 end

Ensuite, sépare ta fonction deletedeadlock de ta fonction main :
dans ton fichier .m, tu mets en premier ton code d'execution, puis après seulement ta fonction deletedeadlock:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
X=%ton labyrinthe
[L C]=size(X);
for i=2:L-1
   for j=2:C-1
      if X(i,j)==0
         X=deletedeadlock(X,i,j);
      end
   end
end
 
function X=deletedeadlock(X,i,j)
%le code de ta fonction
end

EDIT: faut qu'on arrête de répondre en même temps là...

[maleaume]

merci myrne car moi et matlab on ne s'est jamais croisé

[scienceapart]

Les pauvres, je dois vous casser les pieds avec mes soucis de compréhension et de création d'algo.

Sinon ça marche !

Je vous remercie tous les deux ! J'ai rien fait et je dois avoir honte !

Je vais essayer me débrouiller pour déterminer le chemin le plus court maintenant.

Merci encore.

[Myrne]

Si tu as bien compris l'histoire de la récursivité, calculer le chemin le plus court devrait être assez simple. Au moins sur le concept, la mise en application risque de te demander pas mal de temps si tu n'es pas habitué à coder

[scienceapart]

Bonjour,
je suis de retour car finalement l'idée des impasses n'est pas une bonne idée.

On m'a dit de faire en sorte que les chemins, on les remplaces par une succession de nombres qui augmentent 1 par 1 jusqu'à la sortie.

Exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
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
 
 
1     8     1     1     1
1     7     8     9     1
1     6     1     1     1
1     5     4     3     1
1     1     1     2     1

On m'a dit de créer une liste pour mémoriser les coordonnées de départ et qu'ensuite, il faut faire des itérations pour mémoriser les coordonnées de chaque position qu'on aura incrémenté de 1 etc. Mais bon j'arrives pas à mettre ça en place. Pouvez-vous m'aider s'il vous plaît? Merci d'avance.

[scienceapart]

S'il vous plait une réponse.

[scienceapart]

S'il vous plaît, je suis un peu désespéré !

[maleaume]

les impasses marchent tres bien, apres si la personne qui te demande de faire se taff ne connais qu un algo, c est qu elle est pas ouverte d esprit et ne connais que cette methode la. tu as pu voir que cette methode marchais et te permetait d obtenir moins de chemin en eliminant le cul de sac.
vent ton algo

L algo qu on ta aider a concevoir permet de supprimer toutes les impasses reste donc uniquement les chemin possible. reste donc maintenant a chercher le plus court.

l idee d incrementer le numero de chaque case pour avoir la longueur risque de te poser kk soucis au point de croisement.

a mon sens il te faut reperer tous les points de jonctions et les relier entre eux par un graphes + un longueur associer entre deux noeuds, et d optimiser le trajet entre ton entree et ta sortie de facon a avoir un chemin le plus court possible