Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Function solving the TSP problem
5"""
7import random
10def distance_point(p1, p2):
11 """
12 Returns the Euclidian distance between two points.
13 Retourne la distance euclidienne entre deux points.
15 @param p1 point 1
16 @param p2 point 2
17 @return distance
18 """
19 d = 0
20 for a, b in zip(p1, p2):
21 d += (a - b) ** 2
22 return d ** 0.5
25def distance_circuit(points):
26 """
27 Computes the distance of this circuit.
28 Calcule la longueur d'un circuit.
30 @param points list of points, the circuit assumes they are giving in that order
31 @return distance
32 """
33 d = 0
34 for i in range(1, len(points)):
35 d += distance_point(points[i - 1], points[i])
36 return d + distance_point(points[0], points[-1])
39def permutation(points, i, j):
40 """
41 Switches two points and returns a new path.
42 Echange deux points et retourne le nouveau circuit.
44 @param points circuit
45 @param i first index
46 @param j second index (< len(points))
47 @return new circuit
48 """
49 points = points.copy()
50 points[i], points[j] = points[j], points[i]
51 return points
54def reverse(points, i, j):
55 """
56 Reverses a sub part of circuit.
57 Retourne une partie du circuit.
59 @param points circuit
60 @param i first index
61 @param j second index (<= len(points))
62 @return new circuit
63 """
64 points = points.copy()
65 if i > j:
66 i, j = j, i
67 c = points[i:j]
68 c.reverse()
69 points[i:j] = c
70 return points
73def voyageur_commerce_simple(points):
74 """
75 Solves the TSP using basic permutations,
76 points are 2D coordinates.
77 Résoud le problème du voyageur de commerce.
79 @param points list of points
80 """
81 d0 = distance_circuit(points)
82 dnew = d0
83 n = len(points) - 1
84 first = True
85 while dnew < d0 or first:
86 first = False
87 d0 = dnew
89 # first pass : random
90 for i in range(len(points)):
91 h1 = random.randint(0, n)
92 h2 = random.randint(0, n)
93 p = permutation(points, h1, h2)
94 d = distance_circuit(p)
95 if d < dnew:
96 dnew = d
97 points = p
99 h1 = random.randint(0, n)
100 h2 = random.randint(h1 + 1, n + 1)
101 p = reverse(points, h1, h2)
102 d = distance_circuit(p)
103 if d < dnew:
104 dnew = d
105 points = p
107 # second pass : no reverse
108 for i in range(len(points)):
109 for j in range(i + 1, len(points) + 1):
110 p = reverse(points, i, j)
111 d = distance_circuit(p)
112 if d < dnew:
113 dnew = d
114 points = p
116 return points
119def plot_circuit(points, ax=None, **kwargs):
120 """
121 Plots the circuit on a graph.
122 Dessine la solution du voyageur de commerce.
124 @param points points
125 @param ax axe
126 @param kwargs sent to ``plt.subplots``
127 @return ax
128 """
129 if ax is None:
130 import matplotlib.pyplot as plt
131 _, ax = plt.subplots(**kwargs)
133 ax.plot([_[0] for _ in points], [_[1] for _ in points], "o")
135 p2 = points + [points[0]]
136 ax.plot([_[0] for _ in p2], [_[1] for _ in p2], "-")
137 return ax