forked from aimacode/aima-python
-
Notifications
You must be signed in to change notification settings - Fork 1
/
tsp_problem.py
115 lines (89 loc) · 4.24 KB
/
tsp_problem.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
from matplotlib import lines
from search import *
from utils import *
from numpy import random
import matplotlib.pyplot as plt
import numpy as np
import networkx as nx
class TSP_problem(Problem):
""" subclass of Problem to define various functions """
def __init__(self, initial, distances):
super(TSP_problem, self).__init__(initial)
self.distances = distances
def two_opt(self, state):
""" Neighbour generating function for Traveling Salesman Problem """
neighbour_state = state[:]
left = random.randint(0, len(neighbour_state) - 1)
right = random.randint(0, len(neighbour_state) - 1)
if left > right:
left, right = right, left
neighbour_state[left: right + 1] = reversed(neighbour_state[left: right + 1])
return neighbour_state
def actions(self, state):
""" action that can be excuted in given state """
return [self.two_opt]
def result(self, state, action):
""" result after applying the given action on the given state """
return action(state)
def path_cost(self, c, state1, action, state2):
""" total distance for the Traveling Salesman to be covered if in state2 """
cost = 0
for i in range(len(state2) - 1):
cost += self.distances[state2[i]][state2[i + 1]]
cost += self.distances[state2[0]][state2[-1]]
return cost
def value(self, state):
""" value of path cost given negative for the given state """
return -1 * self.path_cost(None, None, None, state)
def hill_climbing_tsp(problem, iterations=10000):
"""From the initial node, keep choosing the neighbor with highest value,
stopping when no neighbor is better. [Figure 4.2]"""
def find_neighbors(state, number_of_neighbors=100):
""" finds neighbors using two_opt method """
neighbors = []
for i in range(number_of_neighbors):
new_state = problem.two_opt(state)
neighbors.append(Node(new_state))
state = new_state
return neighbors
# as this is a stochastic algorithm, we will set a cap on the number of iterations
current = Node(problem.initial)
while iterations:
neighbors = find_neighbors(current.state)
if not neighbors:
break
neighbor = argmax_random_tie(neighbors,
key=lambda node: problem.value(node.state))
if problem.value(neighbor.state) >= problem.value(current.state):
current.state = neighbor.state
iterations -= 1
return current.state
def show_tsp_map(graph_data, words, node_colors = None, figsize=(18,13)):
G = nx.Graph(graph_data['graph_dict'])
node_colors = node_colors or graph_data['node_colors']
node_positions = graph_data['node_positions']
node_label_pos = graph_data['node_label_positions']
edge_weights= graph_data['edge_weights']
# set the size of the plot
plt.figure(figsize=figsize)
# draw the graph (both nodes and edges) with locations from romania_locations
nx.draw(G, pos={k: node_positions[k] for k in G.nodes()},
node_color=[node_colors[node] for node in G.nodes()], linewidths=0.3, edgecolors='k')
# draw labels for nodes
node_label_handles = nx.draw_networkx_labels(G, pos=node_label_pos, font_size=14)
# add a white bounding box behind the node labels
[label.set_bbox(dict(facecolor='white', edgecolor='none')) for label in node_label_handles.values()]
# add edge lables to the graph
nx.draw_networkx_edge_labels(G, pos=node_positions, edge_labels=edge_weights, font_size=14)
# add a legend
white_circle = lines.Line2D([], [], color="white", marker='o', markersize=15, markerfacecolor="white")
list_circles = []
local_words = words[:]
for i in range(len(local_words)):
list_circles.append(white_circle)
local_words[i] = str(i+1) + '-' + local_words[i]
plt.legend(list_circles,
local_words,
numpoints=1, prop={'size':16}, loc=(.95,.5))
# show the plot. No need to use in notebooks. nx.draw will show the graph itself.
plt.show()