YOUR NAME(S) HERE

In [ ]:

```
# everything you need for the TSP!
from tsp_utils import *
%matplotlib inline
```

Traveling salesman problem (TSP): Given a list of cities and the distances between each pair of cities, find thetourwith the lowest possible total cost that visits each city exactly once and returns to the origin city.

- $n$ cities $x_1,\ldots,x_n$.
- Cost matrix $C[x_i, x_j]$ (possibly symmetric and/or triangle inequality).
- Search space is all permutations of cities: size of $(n-1)!$.
- Objective function: sum of costs of the paths.

For this problem, the 'cities' are represented as points on the 2D plane. The $x,y$-coordinates are stored in the Numpy array `coordinates`

and the distances between two cities are found in the Numpy array `distances`

.

In [ ]:

```
coordinates[:10]
```

In [ ]:

```
n = len(coordinates)
print('There are {} cities.'.format(n))
```

In [ ]:

```
distances[:10,:10]
```

Cities are referred by their respective index. A tour is implemented as a list of the permutation of the indices of $n$ cities, e.g. `[0, 1, 2, ..., n-1]`

. Note that the cost is invariant w.r.t. cyclic permutations, i.e. the cost is the same independent from which city the tour starts.

In [ ]:

```
tour = list(range(n))
tour
```

Some simple function are provided to compute the length of a given tour and to plot the cities and a tour.

In [ ]:

```
cost = compute_tour_cost(tour, distances)
print('Cost of tour is {:.3f}'.format(cost))
fig, ax = plt.subplots(figsize=(8, 8))
plot_cities(ax, coordinates, color=blue) # plot cities as a scatter plot
plot_tour(ax, tour, coordinates, distances, color=red, title=True) # add the tour
```

A tour can be saved and loaded in a JSON file. You have to hand in your best tour!

In [ ]:

```
save_tour('Data/my_tour.json', tour)
loaded_tour = load_tour('Data/my_tour.json')
```

In [ ]:

```
!rm Data/my_tour.json
```

Implement *two* heuristic algorithms for finding a low-cost tour:

- write a report in the notebook discussing your strategy and the final results;
- embed the code with sufficient documentation;
- plot your final best tour in your notebook with the total cost.

DESCRIBE YOUR STRATEGY

In [ ]:

```
# CELLS FOR CODE!
# TINY EXAMPLE FROM MICHIEL
import itertools as it
def yield_some_permutations(tour, mtry):
"""
Yields mtry permutations of a tour.
"""
count = 0
for perm in it.permutations(tour):
yield perm
count += 1
if count > mtry:
break
def lazy_brute_force(distances, mtry=10000):
n, _ = distances.shape
return min(yield_some_permutations(list(range(n)), mtry),
key=lambda t : compute_tour_cost(t, distances))
```

In [ ]:

```
%timeit
best_tour = lazy_brute_force(distances, mtry=10000)
```

In [ ]:

```
cost = compute_tour_cost(best_tour, distances)
print('Cost of tour is {:.3f}'.format(cost)) # improvement!
fig, ax = plt.subplots(figsize=(8, 8))
plot_cities(ax, coordinates, color=blue) # plot cities as a scatter plot
plot_tour(ax, best_tour, coordinates, distances, color=orange, title=True) # add the tour
```

DESCRIBE YOUR RESULTS