In [1]:
from Graphics import Point
In [2]:
Point(0, 0) - Point(10, 10)
Out[2]:
14.142135623731
In [3]:
import random
import time
import itertools
In [4]:
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)
In [5]:
alltours = itertools.permutations # The permutation function is already defined in the itertools module

cities = {1, 2, 3}
In [6]:
list(alltours(cities))
Out[6]:
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
In [7]:
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)))
In [8]:
City = Point # Constructor for new cities, e.g. City(300, 400)

def distance(A, B): 
    "The distance between two points."
    return abs(A - B)
In [9]:
A = City(300, 0)
B = City(0, 400)
print(distance(A, B))
500.0
In [10]:
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)
In [11]:
cities8
Out[11]:
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)>])
In [12]:
%%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
In [13]:
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
In [14]:
alltours({1, 2, 3})
Out[14]:
[[1, 2, 3], [1, 3, 2]]
In [15]:
alltours({1, 2, 3, 4})
Out[15]:
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]
In [16]:
%%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
In [17]:
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
In [18]:
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))
In [19]:
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
In [20]:
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
In [21]:
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
In [22]:
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
In [23]:
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
In [25]:
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
In [25]:
 
In [ ]: