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

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

# -*- coding: utf-8 -*- 

""" 

@file 

@brief Function solving the TSP problem 

""" 

 

import random 

 

 

def distance_point(p1, p2): 

""" 

Returns the Euclidian distance between two points. 

Retourne la distance euclidienne entre deux points. 

 

@param p1 point 1 

@param p2 point 2 

@return distance 

""" 

d = 0 

for a, b in zip(p1, p2): 

d += (a - b) ** 2 

return d ** 0.5 

 

 

def distance_circuit(points): 

""" 

Computes the distance of this circuit. 

Calcule la longueur d'un circuit. 

 

@param points list of points, the circuit assumes they are giving in that order 

@return distance 

""" 

d = 0 

for i in range(1, len(points)): 

d += distance_point(points[i - 1], points[i]) 

return d + distance_point(points[0], points[-1]) 

 

 

def permutation(points, i, j): 

""" 

Switches two points and returns a new path. 

Echange deux points et retourne le nouveau circuit. 

 

@param points circuit 

@param i first index 

@param j second index (< len(points)) 

@return new circuit 

""" 

points = points.copy() 

points[i], points[j] = points[j], points[i] 

return points 

 

 

def reverse(points, i, j): 

""" 

Reverses a sub part of circuit. 

Retourne une partie du circuit. 

 

@param points circuit 

@param i first index 

@param j second index (<= len(points)) 

@return new circuit 

""" 

points = points.copy() 

if i > j: 

i, j = j, i 

c = points[i:j] 

c.reverse() 

points[i:j] = c 

return points 

 

 

def voyageur_commerce_simple(points): 

""" 

Solves the TSP using basic permutations, 

points are 2D coordinates. 

Résoud le problème du voyageur de commerce. 

 

@param points list of points 

""" 

d0 = distance_circuit(points) 

dnew = d0 

n = len(points) - 1 

first = True 

while dnew < d0 or first: 

first = False 

d0 = dnew 

 

# first pass : random 

for i in range(len(points)): 

h1 = random.randint(0, n) 

h2 = random.randint(0, n) 

p = permutation(points, h1, h2) 

d = distance_circuit(p) 

if d < dnew: 

dnew = d 

points = p 

 

h1 = random.randint(0, n) 

h2 = random.randint(h1 + 1, n + 1) 

p = reverse(points, h1, h2) 

d = distance_circuit(p) 

if d < dnew: 

dnew = d 

points = p 

 

# second pass : no reverse 

for i in range(len(points)): 

for j in range(i + 1, len(points) + 1): 

p = reverse(points, i, j) 

d = distance_circuit(p) 

if d < dnew: 

dnew = d 

points = p 

 

return points 

 

 

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

""" 

Plots the circuit on a graph. 

Dessine la solution du voyageur de commerce. 

 

@param points points 

@param ax axe 

@param kwargs sent to ``plt.subplots`` 

@return ax 

""" 

if ax is None: 

import matplotlib.pyplot as plt 

f, ax = plt.subplots(**kwargs) 

 

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

 

p2 = points + [points[0]] 

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

return ax