Hide keyboard shortcuts

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""" 

6 

7import random 

8 

9 

10def distance_point(p1, p2): 

11 """ 

12 Returns the Euclidian distance between two points. 

13 Retourne la distance euclidienne entre deux points. 

14 

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 

23 

24 

25def distance_circuit(points): 

26 """ 

27 Computes the distance of this circuit. 

28 Calcule la longueur d'un circuit. 

29 

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]) 

37 

38 

39def permutation(points, i, j): 

40 """ 

41 Switches two points and returns a new path. 

42 Echange deux points et retourne le nouveau circuit. 

43 

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 

52 

53 

54def reverse(points, i, j): 

55 """ 

56 Reverses a sub part of circuit. 

57 Retourne une partie du circuit. 

58 

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 

71 

72 

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. 

78 

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 

88 

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 

98 

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 

106 

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 

115 

116 return points 

117 

118 

119def plot_circuit(points, ax=None, **kwargs): 

120 """ 

121 Plots the circuit on a graph. 

122 Dessine la solution du voyageur de commerce. 

123 

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) 

132 

133 ax.plot([_[0] for _ in points], [_[1] for _ in points], "o") 

134 

135 p2 = points + [points[0]] 

136 ax.plot([_[0] for _ in p2], [_[1] for _ in p2], "-") 

137 return ax