Bonjour à tous,
Je poste ici car je développe en c++, mais mon problème est plutot lié à de la logique.
Je suis en train d'implémenter l'algorithme 2opt pour le problème du TSP.
Avant de rentrer dans le vif du sujet je vais vous expliquer ce qu'est 2opt et le TSP afin que tout le monde puisse voir de quoi je parle.
TSP :
C'est le problème plus connu en france comme étant le problème du voyageur de commerce.
L'énoncé est simple : étant donné un ensemble de n villes nous devons trouvé la tournée de moindre coût permettant de passer par l'ensemble des villes une et une seulle fois tout en revenant à la ville de départ.
D'un point de vue théorie des graphes nous pourrions dire que nous souhaitons trouver le cycle de moindre coût.
2opt :
Le principe de cet algorithme est simple.
Nous devons tout d'abord trouvée une solution initiale, Sinit, calculée aléatoirement ou par un quelconque autre moyen.
Pour ma part j'ai initialisé Sinit de façon aléatoire.
Puis Tant que le nombre d'itération maximal n'est pas atteind :
-nous cassons 2 arrétes aléatoirement de notre cycle initial et nous reconstruisons un nouveau cycle différent du précédent.
En modifiant si possible le sens de certaines arrétes c'est a dire si nous avons 0 1 2 3 4 et que nous supprimons 01 et 34 nous obtenons alors 0 3 2 1 4.
-si le nouveau cycle a un cout inférieur au précédent alors nous le concervons
-sinon nous concervons le cycle avant transformation.
Cela permet donc d'optenir un cycle de coût minimal.
Plusieurs méthodes d'implémentation existent :
La méthode naïve :
Elle consiste à créer un cycle, c, et sa copie, cp, avec leurs coûts associé cout, et coutc.
De cette façon les modifications ne sont apportées qu’à la copie.
Si le cout de la copie coutp est inférieur à cout alors c est modifié sinon on réinitialise cp à c et nous réitérons.
Cette méthode à pour principal défaut d'être très gourmande en ressource à cause de la réinitialisation de cp.
Pour parer cela une autre méthode à été trouvée :
Elle consiste à ne pas faire de copie nous effectuons la modification directement sur notre cycle de base.
Et si les modifications engendrent un meilleur cycle alors nous le conservons, sinon nous refaisons un 2 opt pour revenir à l'état initial.
Mon problème arrive a ce moment la. Mais pour être plus clair je vais vous parler de mes structures de données.
Mon cycle est enregistré dans un tableau de taille n (n=nombre de villes).
Par exemple après initialisation mon cycle est : 0 1 2 3 4, pour n=5.
Ce qui veut dire que les arrêtes 01 ; 12 ; 23 ; 34 et 40 composent mon cycle.
Les coûts de ces arrêtes sont dans un matrice de taille n*n dont la diagonale est de valeur "infinie" (pour éviter les boucles).
Et donc pour calculer le coût de ma solution initiale je fais :
Après quoi je commence les modifications sur mon cycle et je calcule le cout des arrête enlevées est supérieur au coût des arrêtes ajoutées.Code:
2
Et le problème est bien la je n'arrive pas à calculer ses coûts.
Après plusieurs essais je me suis arrêté à :
etCode:
2
3
4
5
6
7
8
9
10
11
Je me doute bien que le problème vient de mes indices de tableau mais je ne vois pas ce qui ne va pas.Code:
2
3
4
5
6
7
8
9
10
11
La mise à jour de cbest ce fait :
Je vous mets bien sur mon code source :Code:
2
3
Je code avec Code::Blocks 10.05 sous windows 7.Code:
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
En vous remerciant d'avance pour vos réponses.
