-
Notifications
You must be signed in to change notification settings - Fork 0
/
TSPSolver.py
245 lines (220 loc) · 10.5 KB
/
TSPSolver.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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#!/usr/bin/python3
from which_pyqt import PYQT_VER
if PYQT_VER == 'PYQT5':
from PyQt5.QtCore import QLineF, QPointF
else:
raise Exception('Unsupported Version of PyQt: {}'.format(PYQT_VER))
import time
import numpy as np
from TSPClasses import *
import heapq
import itertools
class TSPSolver:
def __init__(self, gui_view):
self._scenario = None
def setupWithScenario(self, scenario):
self._scenario = scenario
''' <summary>
This is the entry point for the default solver
which just finds a valid random tour. Note this could be used to find your
initial BSSF.
</summary>
<returns>results dictionary for GUI that contains three ints: cost of solution,
time spent to find solution, number of permutations tried during search, the
solution found, and three null values for fields not used for this
algorithm</returns>
'''
def defaultRandomTour(self, time_allowance=60.0):
results = {}
cities = self._scenario.getCities()
ncities = len(cities)
foundTour = False
count = 0
best_solution = None
start_time = time.time()
while not foundTour and time.time() - start_time < time_allowance:
# create a random permutation
perm = np.random.permutation(ncities)
route = []
# Now build the route using the random permutation
for i in range(ncities):
route.append(cities[perm[i]])
best_solution = TSPSolution(route)
count += 1
if best_solution.cost < np.inf:
# Found a valid route
foundTour = True
end_time = time.time()
results['cost'] = best_solution.cost if foundTour else math.inf
results['time'] = end_time - start_time
results['count'] = count
results['soln'] = best_solution
results['max'] = None
results['total'] = None
results['pruned'] = None
return results
''' <summary>
This is the entry point for the greedy solver, which you must implement for
the group project (but it is probably a good idea to just do it for the branch-and
bound project as a way to get your feet wet). Note this could be used to find your
initial BSSF.
</summary>
<returns>results dictionary for GUI that contains three ints: cost of best solution,
time spent to find best solution, total number of solutions found, the best
solution found, and three null values for fields not used for this
algorithm</returns>
'''
# Time Complexity: O(n) * O(n) = O(n^2)
# Space Complexity: O(n) + O(n) + O(n) = O(3n) = O(n)
def greedy(self, time_allowance=60.0):
results = {}
routeFound = False
route = []
listOfPossibleStartCities = self._scenario.getCities().copy() # Space Complexity: O(n)
cities = self._scenario.getCities() # Space Complexity: O(n)
startCity = listOfPossibleStartCities.pop() # Space Complexity: O(n)
city = startCity
route.append(city)
start_time = time.time()
while routeFound is False and time.time() - start_time < time_allowance: # Time Complexity: O(n)
lowestCost = math.inf
lowestCity = None
for neighbor in cities: # Time Complexity: O(n)
if neighbor is city:
continue
if city.costTo(neighbor) < lowestCost and (neighbor not in route):
lowestCost = city.costTo(neighbor)
lowestCity = neighbor
if lowestCity is None: # check to see if can't continue
if city.costTo(startCity) < lowestCost: # check to see if we're done
routeFound = True
bssf = TSPSolution(route)
else:
route.clear()
startCity = listOfPossibleStartCities.pop()
city = startCity
# route.append(city)
else: # We did find a lowestCity
route.append(lowestCity)
city = lowestCity
end_time = time.time()
results['cost'] = bssf.cost if routeFound else math.inf
results['time'] = end_time - start_time
results['count'] = len(route)
results['soln'] = bssf
results['max'] = None
results['total'] = None
results['pruned'] = None
return results
''' <summary>
This is the entry point for the branch-and-bound algorithm that you will implement
</summary>
<returns>results dictionary for GUI that contains three ints: cost of best solution,
time spent to find best solution, total number solutions found during search (does
not include the initial BSSF), the best solution found, and three more ints:
max queue size, total number of states created, and number of pruned states.</returns>
'''
def branchAndBound(self, time_allowance=60.0):
pass
''' <summary>
This is the entry point for the algorithm you'll write for your group project.
</summary>
<returns>results dictionary for GUI that contains three ints: cost of best solution,
time spent to find best solution, total number of solutions found during search, the
best solution found. You may use the other three field however you like.
algorithm</returns>
'''
def fancy(self, time_allowance=60.0):
initial_greedy_sol = self.greedy()["soln"]
results = self.two_opt(initial_greedy_sol, time_allowance)
# results = self.three_opt(initial_greedy_sol, time_allowance)
print("cost: ", results["cost"])
print("time: ", results["time"])
return results
# Time Complexity: O(c) * O(n) * O(n) = O(c* n^2) = O(n^2)
# Space Complexity: O(n) + O(n) + O(n) = O(3n) = O(n)
def two_opt(self, soln, time_allowance):
sol_to_beat = soln # Space: O(n)
route_to_beat = sol_to_beat.route.copy() # Space Complexity: O(n)
start_time = time.time()
improved = True
count = 0
iter = 1
# Time Complexity: O(c) (which is bounded to a small const by the efficiency of greedy - should be less than 5)
while improved and time.time() - start_time < time_allowance:
print("Iteration num: %s" % iter)
iter += 1
improved = False
for i in range(1, len(route_to_beat) - 2): # Time Complexity: O(n)
for j in range(i + 1, len(route_to_beat)):
if j - i == 1:
continue
new_route = route_to_beat.copy() # Space Complexity: O(n)
new_route[i:j] = route_to_beat[j - 1:i - 1:-1]
new_sol = TSPSolution(new_route)
if new_sol.cost < sol_to_beat.cost:
sol_to_beat = new_sol
route_to_beat = new_route
count += 1
improved = True
end_time = time.time()
results = {'cost': sol_to_beat.cost, 'time': end_time - start_time, 'count': count, 'soln': sol_to_beat,
'max': None, 'total': None, 'pruned': None}
return results
# Time Complexity: O(c) * O(n) * O(n) * O(n) = O(c * n^3) = O(n^3)
# Space Complexity: O(n) + O(n) + O(n) = O(3n) = O(n)
def three_opt(self, soln, time_allowance):
sol_to_beat = soln # Space Complexity: O(n)
route_to_beat = sol_to_beat.route.copy() # Space Complexity: O(n)
start_time = time.time()
improved = True
count = 0
iter = 1
# Time Complexity: O(c) (which is bounded to a small const by the efficiency of greedy - should be less than 5)
while improved and time.time() - start_time < time_allowance:
print("Iteration num: %s" % iter)
iter += 1
improved = False
for i in range(1, len(route_to_beat) - 2): # Time Complexity: O(n)
for j in range(i + 1, len(route_to_beat)): # Time Complexity: O(n)
if j - i == 1:
continue
else:
for k in range(j + 1, len(route_to_beat)): # Time Complexity: O(n)
if k - j == 1:
continue
# 6 cases
# AB, CD, EF - original
# AB, CF, ED - swap D & F
new_route = route_to_beat.copy() # Space Complexity: O(n)
new_route[j:k] = route_to_beat[k - 1:j - 1:-1] # swaps D & F
new_solA = TSPSolution(new_route)
# AD, CB, EF - swap B & D
new_route = route_to_beat.copy()
new_route[i:j] = route_to_beat[j - 1:i - 1:-1] # swaps B & D
new_solB = TSPSolution(new_route)
# AD, CF, EB - swap B & F, then F & D
new_route = route_to_beat.copy()
new_route[i:k] = route_to_beat[k - 1:i - 1:-1] # swaps B & F
new_route[k:j] = route_to_beat[j - 1:k - 1:-1] # swaps D & F
new_solC = TSPSolution(new_route)
# AF, CD, EB - swap B & F
new_route = route_to_beat.copy()
new_route[i:k] = route_to_beat[k - 1:i - 1:-1] # swaps B & F
new_solD = TSPSolution(new_route)
# AF, CB, ED - swap B & F, then B & D
new_route = route_to_beat.copy()
new_route[i:k] = route_to_beat[k - 1:i - 1:-1] # swaps B & F
new_route[j:i] = route_to_beat[i - 1:j - 1:-1] # swaps B & D
new_solE = TSPSolution(new_route)
array = [new_solA, new_solB, new_solC, new_solD, new_solE]
array.sort(key=lambda a: a.cost)
if array[0].cost < sol_to_beat.cost:
sol_to_beat = array[0]
route_to_beat = array[0].route
improved = True
count += 1
end_time = time.time()
results = {'cost': sol_to_beat.cost, 'time': end_time - start_time, 'count': count, 'soln': sol_to_beat,
'max': None, 'total': None, 'pruned': None}
return results