-
Notifications
You must be signed in to change notification settings - Fork 7
/
2opt.py
69 lines (61 loc) · 2.13 KB
/
2opt.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
import tsplib95
import matplotlib.pyplot as plt
import networkx as nx
import random
problem = tsplib95.load_problem('bays29.tsp')
G = problem.get_graph()
n = len(G.nodes)
s = 1
v = s
nodes = [v]
path = []
cost = 0
for i in range(n - 1):
candidates = []
for to in range(1, n + 1):
if to not in nodes:
candidates.append((G.edges[v, to]['weight'], to))
candidates.sort()
next_node = candidates[0][1]
cost += candidates[0][0]
nodes.append(next_node)
path.append((v, next_node))
v = next_node
path.append((v, s))
cost += G.edges[v, s]['weight']
plt.figure()
_, ax = plt.subplots()
pos = problem.display_data or problem.node_coords
nx.draw_networkx_nodes(G, pos=pos, ax=ax)
nx.draw_networkx_labels(G, pos=pos, labels={i: str(i) for i in range(1, len(G.nodes) + 1)}, font_size=8, font_color='white')
nx.draw_networkx_edges(G, pos=pos, edgelist=path, arrows=True)
ax.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
plt.show()
# 2-swap
for _ in range(10000):
while True:
i = random.randint(0, n - 1)
j = random.randint(0, n - 1)
if i != j:
break
if i > j:
i, j = j, i
distA = G.edges[nodes[i], nodes[i + 1]]['weight']
distB = G.edges[nodes[j], nodes[(j + 1) % n]]['weight']
distC = G.edges[nodes[i], nodes[j]]['weight']
distD = G.edges[nodes[i + 1], nodes[(j + 1) % n]]['weight']
if distA + distB > distC + distD:
print(cost, i, j, nodes[i], nodes[j])
nodes[i + 1:j + 1] = reversed(nodes[i + 1: j + 1])
cost += (distC + distD - distA - distB)
path = []
for i in range(n):
path.append((nodes[i], nodes[(i + 1) % n]))
plt.figure()
_, ax = plt.subplots()
pos = problem.display_data or problem.node_coords
nx.draw_networkx_nodes(G, pos=pos, ax=ax)
nx.draw_networkx_labels(G, pos=pos, labels={i: str(i) for i in range(1, len(G.nodes) + 1)}, font_size=8, font_color='white')
nx.draw_networkx_edges(G, pos=pos, edgelist=path, arrows=True)
ax.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)
plt.show()