-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtd_note_2010_rattrape.py
236 lines (193 loc) · 5.4 KB
/
td_note_2010_rattrape.py
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
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
# coding: utf-8
import random
import pylab
import copy
###
# r�ponse � la question 1
###
def get_tour():
tour = """Auxerre 3,537309885 47,76720047
Bastia 9,434300423 42,66175842
Bordeaux -0,643329978 44,80820084
Boulogne 1,579570055 50,70875168
Caen -0,418989986 49,14748001
Le Havre 0,037500001 49,45898819
Lens 2,786649942 50,40549088
Lille 2,957109928 50,57350159
Lyon 4,768929958 45,70447922
Paris 2,086790085 48,65829086
Lyon 4,768929958 45,70447922
Marseille 5,290060043 43,1927681
Lille 2,957109928 50,57350159
Nantes -1,650889993 47,16867065
Rennes -1,759150028 48,05683136
Toulouse 1,356109977 43,5388298
Strasbourg 7,687339783 48,49562836
Nancy 6,134119987 48,66695023
Nice 7,19904995 43,6578598
Saint-Etienne 4,355700016 45,39992905
Brest -4,552110195 48,36014938
Metz 6,11729002 49,0734787
Sedan 4,896070004 49,68407059
Grenoble 5,684440136 45,13940048
Annecy 6,082499981 45,8782196""".replace(
",", "."
).split(
"\n"
)
# ligne d'avant : on d�coupe l'unique cha�ne de caract�res
# ligne suivant : on d�coupe chaque ligne en colonne
tour = [t.strip("\r\n ").split("\t") for t in tour]
# puis on convertit les deux derni�res colonnes
tour = [t[:1] + [float(x) for x in t[1:]] for t in tour]
return tour
###
# r�ponse � la question 2
###
def distance(tour, i, j):
dx = tour[i][1] - tour[j][1]
dy = tour[i][2] - tour[j][2]
return (dx**2 + dy**2) ** 0.5
###
# r�ponse � la question 3
###
def longueur_tour(tour):
# n villes = n segments
d = 0
for i in range(len(tour) - 1):
d += distance(tour, i, i + 1)
# il ne faut pas oublier de boucler pour le dernier segment
d += distance(tour, 0, -1)
return d
###
# r�ponse � la question 4
###
def graph(tour):
x = [t[1] for t in tour]
y = [t[2] for t in tour]
x += [x[0]] # on ajoute la derni�re ville pour boucler
y += [y[0]] #
pylab.plot(x, y)
for ville, x, y in tour:
pylab.text(x, y, ville)
pylab.show()
###
# r�ponse � la question 5
###
def permutation(tour):
# on calcule la longueur du tour actuelle
best = longueur_tour(tour)
# variable fix : dit combien d'�changes ont eu lieu depuis la
# derni�re am�lioration
fix = 0
while True:
# on tire deux villes au hasard
i = random.randint(0, len(tour) - 1)
j = random.randint(0, len(tour) - 1)
if i == j:
continue
# on les �changes si i != j
e = tour[i]
tour[i] = tour[j]
tour[j] = e
# on calcule la nouvelle longueur
d = longueur_tour(tour)
if d >= best:
# si le r�sultat est plus long --> retour en arri�re
# ce qui consiste � �changer � nouveau les deux villes
fix += 1
e = tour[i]
tour[i] = tour[j]
tour[j] = e
else:
# sinon, on garde le tableau tel quel
best = d
# et on met fix � 0 pour signifier qu'une modification a eu lieu
fix = 0
# si aucune modification n'a eu lieu durant les derni�res 10000 it�rations,
# on s'arr�te
if fix > 10000:
break
###
# r�ponse � la question 6
###
def retourne(tour, i, j):
"""
on �change les �l�ments i et j
puis i+1 et j-1
puis i+2 et j-2
tant que i+k < j-k
"""
while i <= j:
e = tour[i]
tour[i] = tour[j]
tour[j] = e
i += 1
j -= 1
###
# r�ponse � la question 7
###
def croisement(tour):
"""
cette fonction reprend le m�me sch�ma que la fonction permutation
on annule une modification en appelant � nouveau la fonction retourne
"""
best = longueur_tour(tour)
fix = 0
while True:
i = random.randint(0, len(tour) - 2)
j = random.randint(i + 1, len(tour) - 1)
retourne(tour, i, j)
d = longueur_tour(tour)
if d >= best:
# retour en arri�re
fix += 1
retourne(tour, i, j)
else:
fix = 0
best = d
if fix > 10000:
break
###
# r�ponse � la question 8
###
def enchaine(tour):
"""
cette fonction est plus complexe que le r�sultat demand� pour cette question
on encha�ne les deux fonctions (croisement, permutation) tant que
la longueur du circuit diminue
et si jamais cette longueur ne diminue plus, on perturbe le circuit
au plus deux fois
en �changeant trois couples de villes choisies au hasard,
cette derni�re partie n'�tait pas pr�vue dans l'�nonc�
"""
best = longueur_tour(tour)
tttt = copy.deepcopy(tour)
print("debut", best)
nom = 0
while True:
croisement(tour)
d = longueur_tour(tour)
print("croisement", d, best)
permutation(tour)
d = longueur_tour(tour)
print("permutation", d, best)
if d < best:
best = d
tttt = copy.deepcopy(tour)
nom = 0
elif nom > 2:
break
else:
nom += 1
for _k in range(3):
i = random.randint(0, len(tour) - 2)
j = random.randint(i + 1, len(tour) - 1)
e = tour[i]
tour[i] = tour[j]
tour[j] = e
return tttt
if __name__ == "__main__":
tour = get_tour()
tour = enchaine(tour)
graph(tour)