from Graphics import Point
Point(0, 0) - Point(10, 10)
14.142135623731
import random
import time
import itertools
def exact_TSP(cities):
"Generate all possible tours of the cities and choose the shortest one."
return shortest(alltours(cities))
def shortest(tours):
"Return the tour with the minimum total distance."
return min(tours, key=total_distance)
alltours = itertools.permutations # The permutation function is already defined in the itertools module
cities = {1, 2, 3}
list(alltours(cities))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
def total_distance(tour):
"The total distance between each pair of consecutive cities in the tour."
return sum(distance(tour[i], tour[i-1]) for i in range(len(tour)))
City = Point # Constructor for new cities, e.g. City(300, 400)
def distance(A, B):
"The distance between two points."
return abs(A - B)
A = City(300, 0)
B = City(0, 400)
print(distance(A, B))
500.0
def Cities(n):
"Make a set of n cities, each with random coordinates."
return set(City(random.randrange(10, 890), random.randrange(10, 590)) for c in range(n))
# Let's make some standard sets of cities of various sizes.
# We'll set the random seed so that these sets are the same every time we run this notebook.
random.seed('seed')
cities8, cities10, cities100, cities1000 = Cities(8), Cities(10), Cities(100), Cities(1000)
cities8
set([<Point (x=476,y=312)>, <Point (x=888,y=54)>, <Point (x=607,y=12)>, <Point (x=229,y=343)>, <Point (x=409,y=128)>, <Point (x=781,y=385)>, <Point (x=231,y=241)>, <Point (x=596,y=456)>])
%%time
tour = exact_TSP(cities8)
print(tour)
print(total_distance(tour))
(<Point (x=607,y=12)>, <Point (x=409,y=128)>, <Point (x=231,y=241)>, <Point (x=229,y=343)>, <Point (x=476,y=312)>, <Point (x=596,y=456)>, <Point (x=781,y=385)>, <Point (x=888,y=54)>) 1808.86268316 Time: 00 s, 987 ms
def alltours(cities):
"Return a list of tours, each a permutation of cities, but each one starting with the same city."
start = first(cities)
return [[start] + list(tour)
for tour in itertools.permutations(cities - {start})]
def first(collection):
"Start iterating over collection, and return the first element."
for x in collection: return x
alltours({1, 2, 3})
[[1, 2, 3], [1, 3, 2]]
alltours({1, 2, 3, 4})
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]
%%time
tour = exact_TSP(cities8)
print(tour)
print(total_distance(tour))
[<Point (x=476,y=312)>, <Point (x=229,y=343)>, <Point (x=231,y=241)>, <Point (x=409,y=128)>, <Point (x=607,y=12)>, <Point (x=888,y=54)>, <Point (x=781,y=385)>, <Point (x=596,y=456)>] 1808.86268316 Time: 00 s, 168 ms
def plot_tour(algorithm, cities):
"Apply a TSP algorithm to cities, and plot the resulting tour."
# Find the solution and time how long it takes
t0 = time.clock()
tour = algorithm(cities)
t1 = time.clock()
# Plot the tour as blue lines between blue circles, and the starting city as a red square.
calico.ScatterChart(['x', 'y'], XY(list(tour) + [tour[0]]), {'width': 600, "height": 300,
'legend': 'none', "lineWidth": 1,
"pointSize": 3}).display()
print("{} city tour; total distance = {:.1f}; time = {:.3f} secs for {}".format(
len(tour), total_distance(tour), t1-t0, algorithm.__name__))
def XY(points):
"Given a list of points, return a list of [(X, Y), ...]"
return [(p.x, p.y) for p in points]
plot_tour(exact_TSP, cities8)
8 city tour; total distance = 1808.9; time = 0.136 secs for exact_TSP
def greedy_TSP(cities):
"At each step, visit the nearest neighbor that is still unvisited."
start = first(cities)
tour = [start]
unvisited = cities - {start}
while unvisited:
C = nearest_neighbor(tour[-1], unvisited)
tour.append(C)
unvisited.remove(C)
return tour
def nearest_neighbor(A, cities):
"Find the city in cities that is nearest to city A."
return min(cities, key=lambda x: distance(x, A))
cities = Cities(9)
plot_tour(exact_TSP, cities)
plot_tour(greedy_TSP, cities)
9 city tour; total distance = 2030.1; time = 1.079 secs for exact_TSP
9 city tour; total distance = 2350.9; time = 0.003 secs for greedy_TSP
plot_tour(greedy_TSP, cities100)
plot_tour(greedy_TSP, cities1000)
100 city tour; total distance = 7000.7; time = 0.034 secs for greedy_TSP
1000 city tour; total distance = 20854.9; time = 1.206 secs for greedy_TSP
def all_greedy_TSP(cities):
"Try the greedy algorithm from each of the starting cities; return the shortest tour."
return shortest(greedy_TSP(cities, start=c) for c in cities)
# We will modify greedy_TSP to take an optional start city; otherwise it is unchanged.
def greedy_TSP(cities, start=None):
"At each step, visit the nearest neighbor that is still unvisited."
if start is None: start = first(cities)
tour = [start]
unvisited = cities - {start}
while unvisited:
C = nearest_neighbor(tour[-1], unvisited)
tour.append(C)
unvisited.remove(C)
return tour
# Compare greedy_TSP to all_greedy_TSP
plot_tour(greedy_TSP, cities100)
plot_tour(all_greedy_TSP, cities100)
100 city tour; total distance = 7000.7; time = 0.026 secs for greedy_TSP
100 city tour; total distance = 6742.8; time = 1.367 secs for all_greedy_TSP
def greedy_exact_end_TSP(cities, start=None, end_size=8):
"""At each step, visit the nearest neighbor that is still unvisited until
there are k_end cities left; then choose the best of all possible endings."""
if start is None: start = first(cities)
tour = [start]
unvisited = cities - {start}
# Use greedy algorithm for all but the last end_size cities
while len(unvisited) > end_size:
C = nearest_neighbor(tour[-1], unvisited)
tour.append(C)
unvisited.remove(C)
# Consider all permutations of possible ends to the tour, and choose the best one.
# (But to make things faster, omit the middle of the tour.)
ends = map(list, itertools.permutations(unvisited))
best = shortest([tour[0], tour[-1]] + end for end in ends)
return tour + best[2:]
plot_tour(greedy_exact_end_TSP, cities100)
plot_tour(greedy_exact_end_TSP, cities1000)
100 city tour; total distance = 6853.2; time = 1.390 secs for greedy_exact_end_TSP
1000 city tour; total distance = 20830.3; time = 2.862 secs for greedy_exact_end_TSP
def greedy_bi_TSP(cities, start_size=12, end_size=6):
"At each step, visit the nearest neighbor that is still unvisited."
starts = random.sample(cities, min(len(cities), start_size))
return shortest(greedy_exact_end_TSP(cities, start, end_size)
for start in starts)
random.seed('bi')
plot_tour(greedy_bi_TSP, cities100)
plot_tour(greedy_bi_TSP, cities1000)
100 city tour; total distance = 7096.5; time = 0.442 secs for greedy_bi_TSP
1000 city tour; total distance = 20824.9; time = 17.009 secs for greedy_bi_TSP
from Widgets import Lines
def compare_algorithms(algorithms, maps):
"Apply each algorithm to each map and plot results."
lines = Lines(len(maps))
for algorithm in algorithms:
t0 = time.clock()
results = [total_distance(algorithm(m)) for m in maps]
t1 = time.clock()
avg = sum(results) / len(results)
label = '{:.0f}; {:.1f}s: {}'.format(avg, t1-t0, algorithm.__name__)
lines = Lines(lines, sorted(results), label)
calico.LineChart(lines, {"width": 800, "height": 300, "chartArea": {"width": 300}}).display()
print('{} x {}-city maps'.format(len(maps), len(maps[0])))
def Maps(M, N):
"Return a list of M maps, each consisting of a set of N cities."
return [Cities(N) for m in range(M)]
compare_algorithms([greedy_TSP, greedy_exact_end_TSP, all_greedy_TSP], Maps(10, 50))
10 x 50-city maps