3 jours sans trouver le résultat... heeeeeeelp plz
blanccc
Messages postés23Date d'inscriptionmercredi 7 décembre 2005StatutMembreDernière intervention 9 juin 2006
-
21 avril 2006 à 15:08
cs_louis14
Messages postés793Date d'inscriptionmardi 8 juillet 2003StatutMembreDernière intervention10 février 2021
-
21 avril 2006 à 22:39
Bonjour à tous. Voila je m'adresse surtout aux matheux et à ceux qui ont fait un peu de théorie des graphes mais je suis preneur de toute réponse que vous pourriez m'apporter ^^
Je suis actuellement en stage de fin d'étude et mon problème est le suivant :
J'ai une série de sommets ainsi qu'une série d'arêtes reliant ces sommets, qui sont à l'origine placés aléatoirement sur une feuille. Mon algorithme est censé travailler sur les coordonnées des sommets ainsi que sur les distances entre 2 sommets pour "redessiner" le graphe de manière à le rendre lisible. J'ai donc fouiné un peu partout sur internet ainsi que sur ce site et j'en ai trouvé un qui est censé fonctionner à merveille, mais voilà chez moi il ne fonctionne pas... lol... Je programme pour le moment sous Matlab (parce que c'est le seul logiciel auquel j'ai accès pour le moment) mais le but est de programmer en C au final.
voici le code que j'utilise, j'espère que vous aurez le temps d'y jeter un coup d'oeil... les fonctions dxm(..), dxm2(..) etc.. sont les dérivées partielles de l'énergie totale de mon graphe (respectivement au 1er et 2ème ordre). La fonction PlusCourtChemin (basée sur l'algorithme de Dijkstra)renvoie le nombre d'arête minimal qu'il faut empreinter pour aller du sommet Debut au sommet Fin. Toutes ces fonctions fonctionnent parfaitement (je les ai testées à part), mais si vous voulez les voir reply et je les mettrai (je ne les met pas pour ne pas surcharger le post).
Voici le code (je vous conseille d'en faire un copier-coller sous notepad il sera beaucoup plus lisible je pense):
%------------------------------%
% PRINCIPE DE L'ALGORITHME %
%------------------------------%
%
% On appellera Pi les points de coordonnées (xi,yi) images des sommets
% Soient les variables suivantes :
% * dij : chemin le plus court de Pi à Pj
% * lij = L x dij avec L la longueur idéale souhaitée entre deux sommets voisins
% * kij = K / (dij²) avec K une constante au choix
% Remarque : plusieurs valeurs de K sont à essayer pour voir son influence sur la vitesse de convergence
% et la valeur de L devrait influer sur la distance entre les sommets les plus proches
%
% On notera Ei l'énergie du sommet N°i et E l'énergie totale du système avec :
%
% n-1
% Ei = Somme ( 1/2 * kij * ( |Pi-Pj| - lij )² )
% j=1
% j<>i
%
% de la même façon on a :
%
% n-1 n-1
% E = Somme [ Somme { 1/2 * kij * ( |Pi-Pj| - lij )² } ]
% i=1 j=i+1
%
% Le problème est qu'il est impossible de minimiser l'énergie du système d'un seul coup. On calcule donc
% l'énergie de chaque particule et on déplace celle qui a l'énergie la plus élevée au point où son énergie est la
% plus faible pour elle. On note Pm le sommet qui a l'énergie la plus élevée et (xm,ym) ses coordonnées:
% Delta_m SQRT( (dE/dxm)² + (dE/dym)² ) cette grandeur est minimale quand dE/dxm dE/dym = 0 et représente l'énergie du sommet m
%
% On se retrouve donc avec un système de 2 équations à 2 inconnues : ( Delta_x , Delta_y ) :
%
% / d²E d²E dE
% | -----(xm(t),ym(t))*Delta_x + -------(xm(t),ym(t))*Delta_y = - ----(xm(t),ym(t))
% | dxm² dxm.dym dxm
% <
% | d²E d²E dE
% | -------(xm(t),ym(t))*Delta_x + -----(xm(t),ym(t))*Delta_y = - ----(xm(t),ym(t))
% \ dxm.dym dym² dym
%
% avec (xm(t),ym(t)) valeur de (xm,ym) à l'itération n°t
%
% Sachant cela, voici donc le principe du fonctionnement en quelques lignes :
% 1. calcul des dij ( 1 <= i <> j <= n )
% 2. calcul des lij ( 1 <= i <> j <= n )
% 2. calcul des kij ( 1 <= i <> j <= n )
% 4. initialisation des Pi
% 5. WHILE maximum(Delta_i) > Epsilon DO
% 6. Soit Pm une particule telle que Delta_m = maximum(Delta_i)
% 7. WHILE Delta_m > Epsilon DO
% 8. Calcul de Delta_x et de Delta_y
% 9. xm := xm + Delta_x
% 10. ym := ym + Delta_y
% 11. END DO;
% 12. END DO;
%
% à la fin de cet algorithme, on échange 2 à 2 les sommets de place. Si un de ces changements amène à une
% énergie globale ou locale plus faible on recommence avec cette nouvelle position comme position de départ.
%--------------------------------------------------------------%
% DEFINITION DES CONSTANTES ET INITIALISATION DES VARIABLES %
%--------------------------------------------------------------%
L = 1; % Cette valeur représente la longueur idéale que l'on souhaite avoir entre chaque paire de noeuds voisins
K = 100; % Cette valeur 'doit' servir de potentiomètre entre vitesse de convergence et précision de résultat (???)
d = zeros([Nb_Sommets,Nb_Sommets]); % \
l = zeros([Nb_Sommets,Nb_Sommets]); % | initialisation des matrices à 0
k = zeros([Nb_Sommets,Nb_Sommets]); % /
% pour chaque couple (i,j), calcul des dij, kij et lij initiaux :
for ii = 1 : Nb_Sommets
for jj = 1 : Nb_Sommets
if ii ~= jj
d(ii,jj) = CheminPlusCourt(ii,jj,Nb_Sommets,Nb_Aretes,Aretes); % distance la plus courte de i à j
l(ii,jj) = d(ii,jj) * L;
k(ii,jj) = K / (d(ii,jj)*d(ii,jj));
end;
end;
end;
Em_Max = -Inf;
Indice_Em_Max = 1;
for ii = 1 : Nb_Sommets
Em1(ii) = Em(ii,Nb_Sommets,Sommets,k,l);
if Em1(ii) > Em_Max
Em_Max = Em1(ii);
Indice_Em_Max = ii;
end;
end;
% on réécrit les système défini précédemment comme suit :
% /
% | A.Delta_x + B.Delta_y = -C
% |
% | B.Delta_x + D.Delta_y = -E
% \
% On va faire la boucle un certain nombre de fois. Evolution à apporter : trouver un epsilon (différence d'NRJ totale
% d'une boucle à l'autre) en dessous duquel on sortirait d'une boucle while (remplaçante de la boucle for)
Nb_Boucles = 10;
for i2 = 1 : Nb_Boucles
Epsilon2 = 0.0001;
Energie_Totale_1 = Etot(Nb_Sommets,Sommets,k,l)
A = dxm2(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
B = dxmym(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
C = dxm(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
D = dym2(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
E = dym(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
Delta_x = (B*E - C*D) / (A*D - B*B);
Delta_y = (B*C - A*E) / (A*D - B*B);
Sommets(Indice_Em_Max,1) = Sommets(Indice_Em_Max,1) + Delta_x;
Sommets(Indice_Em_Max,2) = Sommets(Indice_Em_Max,2) + Delta_y;
Energie_Totale_2 = Etot(Nb_Sommets,Sommets,k,l)
% on continue de déplacer le meme sommet tant que l'énergie totale continue de descendre significativement
% si la différence d'énergie totale entre 2 boucles consécutives n'est pas significative on ne rentre pas(plus)
% dans la boucle while
while Energie_Totale_1 - Energie_Totale_2 >= Epsilon2
Energie_Totale_1 = Energie_Totale_2
A = dxm2(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
B = dxmym(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
C = dxm(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
D = dym2(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
E = dym(Indice_Em_Max , Nb_Sommets , Sommets , k , l);
% Calcul du déplacement élémentaire en x et en y
Delta_x = (B*E - C*D) / (A*D - B*B);
Delta_y = (B*C - A*E) / (A*D - B*B);
% Mise à jour des nouvelles coordonnées du sommet N° Indice_Em_Max
Sommets(Indice_Em_Max,1) = Sommets(Indice_Em_Max,1) + Delta_x;
Sommets(Indice_Em_Max,2) = Sommets(Indice_Em_Max,2) + Delta_y;
%on recalcule à présent la valeur de l'énergie du sommet N° Indice_Em_Max
Energie_Totale_2 = Etot(Nb_Sommets,Sommets,k,l)
end;
%-------------------------------------------%
% AFFICHAGE DU NOUVEAU GRAPHE A L'ECRAN %
%-------------------------------------------%
% Sommets :
figure(1);
plot( Sommets(1:Nb_Sommets,1) , Sommets(1:Nb_Sommets,2) , 'o' );
% Aretes :
for ii = 1 : Nb_Aretes
line( [Sommets(Aretes(ii,1),1) , Sommets(Aretes(ii,2),1)] , [Sommets(Aretes(ii,1),2) , Sommets(Aretes(ii,2),2)] );
end;
% et maintenant on recherche le Sommet dont l'énergie est la plus importante
Indice_Em_Max2 = 1;
for ii = 1 : Nb_Sommets
Em1(ii) = Em(ii,Nb_Sommets,Sommets,k,l);
if Em1(ii) > Em_Max
Em_Max = Em1(ii);
Indice_Em_Max2 = ii;
end;
end;
Voilà ! les variables Sommets() et Aretes() sont construites de la façon suivante :
Sommets(i,1) = abscisse du sommet i
Sommets(i,2) = ordonnée du sommet i
Aretes(i,1) = Numéro du sommet d'origine de l'arête n°i
Aretes(i,2)= Numéro du sommet de destination de l'arête n°i
Si vous avez d'autres questions n'hésitez surtout pas. J'espère que vous ne trouverez pas trop rébarbatif de relire ce code, j'ai vraiment besoin de votre aide je suis perdu là ! vous aurez peut-être remarqué que j'utilise une boucle "for" à un moment où l'algorithme de principe propose une boucle "while". Je l'avais fait au début et, étant donné que l'algorithme n'arrivait pas à converger vers une position stable, il tournait en boucle sans fin. J'ai donc mis une boucle "for" en faisant varier "à la main" le nombre d'itérations
Merci d'avance pour votre aide...
Cédric
A voir également:
3 jours sans trouver le résultat... heeeeeeelp plz
