voyageur de commerce par recuit simulé

**siviuze** · 10/01/2007, 23h50

Bon apres avoir passer qq heures dessus je viens demander de l'aide

Je tente de résoudre le voyageur de comemrce par la méthode du recuit simulé.
Pour ce faire je cré d'abord un premier chemin en choisissant systematiquement la ville voisine la plus proche puis je tente, en faisant des permutations de 2 segments a la fois de maniere aléatoire d'optimiser mon trajet. Cependant, outre le fait que ca ne marche pas

, que le code est tres mal optimisé (au dessus de 50 villes ca devient lent) et bien j'ai l'impression que l'algorithme tourne en rond. Si quelqun pouvais m'eclaircir^^

Seule la fonction rech_locale semble ne pas donner les résultats attendu.
Ah et le tableau ville_dep est global.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
double distance(double ville1[][2], double ville2[][2], short i, short j)
{
double calcX,calcY,calc;
 
calcX = ville1[i][0]-ville2[j][0]; 			//distance entre les abscisses/ordonnées des points
calcY = ville1[i][1]-ville2[j][1];
calc = sqrt((pow(calcX,2) + pow(calcY,2))); //distance total entre 2 points
return calc;
}
 
 
 
void rech_loc(double ville[][2])
{
double II1, JJ1, IJ, I1J1, val, taille=0, best, essai, essai_faire, temp=8000, temp_min=5, dE;
short i, I=0, I1, J=0, J1, flag=0;			 //vecteur I et J
 
essai = pow((VILLE/2),2);
 
for(i=0;i<VILLE;i++)					 //save de lancien parcour
       {
        ville_dep[i][0]=ville[i][0];
        ville_dep[i][1]=ville[i][1];
        }
 
while(temp > temp_min)
        {
        for(essai_faire=0;essai_faire < essai;essai_faire++)
                {
                best=energie(ville);
 
                while(!flag)
                        {
                        I=rand() %VILLE-1;
                        J=rand() %VILLE-1;
 
                        if (I!=J)
                                flag=1;
                        }
 
                        I1=I+1;
                        J1=J+1;
 
                val = ville[I1][0];							//maj du tableau des points
                ville[I1][0] = ville[J][0];
                ville[J][0] = val;
 
                val = ville[I1][1];
                ville[I1][1] = ville[J][1];
                ville[J][1] = val;
 
                taille=energie(ville);
 
                dE=taille-best;							   //delta de l'"energie" finale apres modification
 
                if(dE<0 || recuit(dE, temp))
                        {
                        CanvasClear (VCOM, VCOM_CANVAS, VAL_ENTIRE_OBJECT);
                        for(i=0;i<VILLE-1;i++)		  //retrace le nouveau chemin
                                {
 
				//Sleep(500);
 
                                CanvasDrawLine (VCOM, VCOM_CANVAS,
                                        MakePoint(ville[i][0], ville[i][1]),
                                        MakePoint(ville[i+1][0], ville[i+1][1]));
 
                                CanvasDrawRect (VCOM, VCOM_CANVAS,
                                        MakeRect (ville[i][1],ville[i][0],3,3),
                                        VAL_DRAW_INTERIOR);
 
                                }
                        for(i=0;i<VILLE;i++)					 //save du nouveau parcour
                                {
                                ville_dep[i][0]=ville[i][0];
                                ville_dep[i][1]=ville[i][1];
                                }
 
                        }
                    else
			{
                        for(i=0;i<VILLE;i++)
                                {
                                ville[i][0]=ville_dep[i][0];		  //chargement de l'ancien parcour
                                ville[i][1]=ville_dep[i][1];
                                }
                         }
 
 
                SetCtrlVal (VCOM, VCOM_DISTANCE, best);
                }
        temp = temp * 0.999;
        SetCtrlVal (VCOM, VCOM_TEMP, temp);	
        }
 
}
 
 
double energie(double ville[][2])
{
int i;
double energie=0;
for(i=0;i<VILLE-1;i++)
        energie=energie + distance(ville,ville,i,i+1);
energie = energie + distance(ville, ville, VILLE-1, 0);
return energie;
}
 
 
double recuit(double dE, double temp)
{
double aleat;
 
aleat = (rand()%1000)*0.001;
if(aleat <= exp(-dE/temp))
        return 1;
else
        return 0;
}

voila voila^^ (je ne sais aps si c'est tres lisible

)

**PRomu@ld** · 11/01/2007, 00h19

Cependant, outre le fait que ca ne marche pas , que le code est tres mal optimisé (au dessus de 50 villes ca devient lent)

Déjà, pour le fait que ça ne marche pas, il faut étudier si c'est ton algorithme ou le code qui ne fonctionne pas. Si c'est le code, tu es peut être sur le bon forum, dans ce cas indique nous plus précisement les erreurs.

Si ça n'est pas le cas, il s'agit sans doute d'un problème d'algorithme et tu n'es pas sur le bon forum.

Pour ce qui est de la rapidité, le problème du voyageur de commerce est un problème NP-Complet et c'est donc normal.

**lechewal** · 11/01/2007, 00h46

Envoyé par PRomu@ld

Pour ce qui est de la rapidité, le problème du voyageur de commerce est un problème NP-Complet et c'est donc normal.

Non ce n'est pas normal. Le recuit est un(e?) heuristique. Sa complexité doit etre en n carré..

il doit pouvoir fonctionner "rapidement" sur au moins 2000 villes..

**koala01** · 11/01/2007, 02h45

Envoyé par lechewal

Non ce n'est pas normal. Le recuit est un(e?) heuristique. Sa complexité doit etre en n carré..

il doit pouvoir fonctionner "rapidement" sur au moins 2000 villes..

Heu... Je tiens quand meme à signaler que, si tu as une complexité de n carré, tu obtiens, quand meme, pour 50 villes, 2500 itération à effectuer... Ce qui fait quand meme pas mal

En plus, es tu sur que le recuit simulé soit, réellement, l'algorithme le plus adapté à ce que tu veux

Que penserais-tu, par exemple, de t'orienter vers l'algorithme de Dijkstra qui *pourrait* s'avérer plus adéquat

**siviuze** · 11/01/2007, 08h10

En théorie il me semble avoir réalisé les étapes nécessaire de l'algorthme mais je ne suis pas sur de la maniere dont j'ai encodé la modification du trajet : comme je l'ai dit j'ai l'impression qu'il ne me test aps toute les possibilitées meme pour une température plus élevé. Ensuite pour ce qui est du choix de l'algorithme j'avais compris que l'algorithme de Dijkstra "repassait" par ses anciennes positions ? Et puis le recuit simulé me semblait plus intéressant car plus général et suffisament robuste (c'est mon premier probleme d'optimisation combinatoire donc si je pouvais tester un algo qui marche pour presque tout ^^)

**PRomu@ld** · 11/01/2007, 08h34

Code :

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

1
2
3
while(temp > temp_min)
...
temp = temp * 0.999;

Ici, avant de passer de 8000 à 5, ça risque être long.

Code :

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

calc = sqrt((pow(calcX,2) + pow(calcY,2)));

Si tu veux gagner un peu en rapidité, au lieu de calculer un carré avec pow, fait le à la main. (ie : calcX * calcX ).

Code :

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

1
2
3
4
5
 I=rand() %VILLE-1;
J=rand() %VILLE-1;
 
if (I!=J)
   flag=1;

Ici tu fais une comparaison de flotant, ceci est interdit ! En effet, la comparaison des flotants est incorrecte. Il y a de forte chances que ça boucle.

Heu... Je tiens quand meme à signaler que, si tu as une complexité de n carré, tu obtiens, quand meme, pour 50 villes, 2500 itération à effectuer... Ce qui fait quand meme pas mal

2500 pour un ordi, c'est dérisoire ... . J'avais mal lu et ne connaissant pas le recuit simulé j'était parti du principe que ça restait dans une forte complexité.

voyageur de commerce par recuit simulé

C

Vue hybride

Discussions similaires

Partager

Partager