Discussion :

[siviuze]

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 )