Discussion :

[Onkyo]

Bonjour à tous,

j'ai un problème théorique. Je possède un tableau d'entiers à deux dimensions dans lequel je me place aléatoirement (indice i,j). Puis je compare cette case du tableau avec les 4 cases adjacentes.

Si la case courante est le minimum, alors je m'arrête sinon je me place sur le nouveau minimum puis je compare à nouveau avec les 4 cases adjacentes et ainsi de suite, jusqu'à trouver le minimum du tableau.

Jusque là, tout va bien. Sauf que j'aimerai ne plus effectuer la comparaison avec les cases du tableau déjà visitées et je ne sais pas comment écrire cette condition.

Merci de votre aide.

[soft001]

Peux tu nous montrer ce que tu as déjà fait ?
Comment tu définis les 4 cases adjacentes ?
J'ai deux pistes :
Choix aléatoire de i et j est sans répétition avec une condition (définition des 4 cases adjacentes).
Soit tu supprimes les éléments testés de ta matrice initiale. (matrice ==> vecteur!!!)

[Onkyo]

Pour l'instant, j'arrive à trouver le minimum d'une matrice donnée, en partant de n'importe quel point initial (i,j).
Les cases adjacentes sont définies comme cela :

Code :

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

M((i(1)+k),j(1))

Code :

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

M((i(1)-k),j(1));

Code :

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

M(i(1),(j(1)+k))

Code :

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

M(i(1),(j(1)-k))

Pour k=1

Supprimer les éléments au fur et à mesure est une bonne idée mais je ne vois pas comment écrire la condition "s'il n'existe rien à côté".

Merci.

[soft001]

Pour les sommets, ils ont alors seulement deux cases adjacentes ??

Si la case courante est le minimum, alors je m'arrête sinon je me place sur le nouveau minimum puis je compare à nouveau avec les 4 cases adjacentes et ainsi de suite, jusqu'à trouver le minimum du tableau.

Comment peux tu garantir que tu as trouvé le minimum du tableau ??

[Onkyo]

C'est exactement ça pour les sommets.

En fait, la matrice représente un critère convexe (je fais un peu comme une descente de gradient pour trouver le minimum) donc cela m'assure de trouver le minimum de la matrice.

[soft001]

Je pense que tu vas avoir un problème si tu supprimes les éléments testés :
On suppose que ton min représente une des cases adjacentes de la case courante, forcement cette case n'est pas ton min, si tu vas la supprimer ainsi que ses cases adjacentes, tu tomberas sur un "faux min" !!

[Onkyo]

Oui, en fait plutôt que de supprimer les valeurs, je les ai remplacées par NaN (ce qui facilite aussi pour la condition). Mais j'ai un problème :
je dois remplacer par NaN toutes les valeurs visitées sauf le nouveau minimum (sinon problème pour les comparaisons suivantes) or sur le coup je ne sais pas laquelle des valeurs adjacentes va être mon nouveau minimum.

Je vous mets un petit bout de code pour être plus clair :

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
while condition
				tmp=[];
 
                %on met la valeur initiale dans le tableau
				 if (i(1) <= L && j(1) <= C) 
					 tmp(end+1)=M(i(1),j(1));
                 end
 
                 for k=1:pas
			    %puis viennent les 4 valeurs adjacentes
				  if (i(1)+k <= L) 
					 tmp(end+1)=M((i(1)+k),j(1));
				  end
 
				 if (i(1)-k > 0)
					 nb=M((i(1)-k),j(1));
					 tmp(end+1)=nb;
				 end
 
				 if (j(1)+k <= C)
					 tmp(end+1)=M(i(1),(j(1)+k));
				 end
 
				 if (j(1)-k > 0)
					 tmp(end+1)=M(i(1),(j(1)-k));
 
                 end
                 end
				 val_min=min(tmp);
 
				%Chercher u_min et v_min à partir de la matrice
				 [u_min,v_min]=find(abs(M-val_min)<.001);
				 sol=val_min;
				 u_sol=u_min(1);
				 v_sol=v_min(1);
				 if (M(i(1),j(1)) <= val_min) 
					 condition=false;
				 else
					 i(1)=u_sol;
					 j(1)=v_sol;
				 end

tmp est le tableau dans lequel j'effectue mes comparaisons. Je le vide à chaque nouveau tour de boucle.

[soft001]

Voici ce bout de code, à optimiser :

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
close all
clc
[x,y]=meshgrid(linspace(-2,2,101));
A=(x.^2)+(y.^2);
SizeA=size(A);
surf(x,y,A)
shading interp
view(0,-90)
 
 
iRand=randperm(prod(SizeA));
 
K=1;
j=1;
while numel(iRand)>1
    [I,J] = ind2sub(SizeA,iRand(1));
    Res= CasesAdjacentes(I,J,K,SizeA);
    index=[sub2ind(SizeA,Res(:,1),Res(:,2));iRand(1)];
[Min,Imin] = min(A(index(1:end-1)));
    if A(iRand(1))<Min
        break
    end
    index(Imin)=[];
    for m=1:numel(index)
        iRand(iRand==index(m))=[];
    end
    j=j+1;
end
%%
j
hold on
plot3(x(iRand(1)),y(iRand(1)),A(iRand(1)),'MarkerFaceColor',[1 0 0],'MarkerSize',15,...
    'Marker','hexagram',...
    'LineStyle','none',...
    'Color',[1 0 0]);

la fonction CasesAdjacentes :

Code :

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

1
2
3
4
5
6
7
8
9
10
function Res= CasesAdjacentes(I,J,K,SizeA)
Top=[I-K J];
Bottom=[I+K J];
Left=[I J-K];
Right=[I J+K];
Res=[Top;Bottom;Left;Right];
[row,~] = find(Res<=0);
Res(row,:)=[];
[row,~] = find(Res>SizeA(1)|Res>SizeA(2));
Res(row,:)=[];

[soft001]

Si tu augmentes k, ça converge plus rapidement,

[Onkyo]

Serait-ce possible de commenter un peu le code, car je comprends pas tout...

[Onkyo]

Ok, j'ai finalement compris.
Juste une chose, pour chaque tour de boucle, dans le tableau iRand, j'ai l'impression qu'il repart de iRand(1) (dans lequel on a enlevé les indices des valeurs que l'on a déjà visitées).

J'aimerais mieux qu'il reparte de l'indice du minimum précédent (celui que l'on a trouvé dans le tour de boucle précédente).

[soft001]

Je suis b.., forcément on doit repartir de l'indice du minimum précédent.
Dans ce cas tu n'auras qu'une seule case qui se répète à chaque itération...
Tu peux remplacer Lignes 23==>26 par (tu ne supprimes pas la case qui se répète):

Code :

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

iRand=index(Imin);

et tu mets while true ou while nombre d'itération max.
Tu peux optimiser encore ton algo ainsi que le code !!

[Onkyo]

Merci de votre aide. Grâce à votre astuce des indices dans un tableau, j'ai réussi à modifier mon code pour qu'il ne prenne plus en compte les cases déjà visitées.

Toutefois, j'ai essayé de reprendre le code que vous m'avez fournit et je me suis rendu compte qu'il reprend les cases déjà visitées. Seule le tableau iRand est modifié (donc la case de départ à chaque tour de boucle).

Une autre petite question : dans la fonction CasesAdjacentes, comment modifier l'algo pour que pour k=2 par exemple, il remplisse le tableau Top avec les 2 cases adjacentes (idemn pour Bottom, Left, Right).Autrement dit pour k=2, je prends les cases de k=1 + k=2, pour k=3, ce sera k=3 + k=2 + k=1.

Par exemple pour k=2 :

[soft001]

De rien

Toutefois, j'ai essayé de reprendre le code que vous m'avez fournit et je me suis rendu compte qu'il reprend les cases déjà visitées. Seule le tableau iRand est modifié (donc la case de départ à chaque tour de boucle).

Non, pour chaque nouvelle itération on ne reprend qu'une seule case déjà visitée et pas toutes les cases.

Une autre petite question : dans la fonction CasesAdjacentes, comment modifier l'algo pour que pour k=2 par exemple, il remplisse le tableau Top avec les 2 cases adjacentes (idemn pour Bottom, Left, Right).Autrement dit pour k=2, je prends les cases de k=1 + k=2, pour k=3, ce sera k=3 + k=2 + k=1.

Par exemple pour k=2 :

Tu modifies la fonction CasesAdjacentes, comme par exemple pour le Top de ta case active, tu peux ne pas prendre les inter-cases. Tu choisis un grand K puis tu le modifies de façon automatique pour trouver ton min, je pense que c'est plus rapide :

Code :

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

Top=[(I-K:I-1)' J*ones(K,1)];

[Onkyo]

Bonsoir,

j'aimerai maintenant effectuer la même chose mais pour un critère 3d. C'est à dire qu'au lieu d'avoir une matrice, on a maintenant un tenseur (comme un cube).
Je voudrai savoir si les fonctions utilisées (sub2ind, size) sont toujours valables... Et comment modéliser ce tenseur sous matlab ?

Merci