The first solution that comes to mind to solve the TSP is using brute force to come up with the shortest path in which the salesperson visits every city exactly once and returns to the initial city. So, the brute-force strategy works as follows:

1. Evaluate all possible tours.
2. Choose the one for which we get the shortest distance.

The problem is that for n number of cities there are (n-1)! possible tours. It means that five cities will produce 4! = 24 tours and we will select the one that corresponds to the lowest distance. It is obvious that this method will only work since we do not have too many cities. As the number of cities increases, the brute-force strategy becomes unstable due to a large number of permutations generated by using this approach.

Let's see how we can implement the brute-force strategy in Python.

First, note that a tour, {1,2,3}, represents a tour of the city from city 1 to city 2 and city 3. The total distance in a tour is the total distance covered in a tour. We will assume that the distance between the cities is the shortest distance between them (which is the Euclidean distance).

Let's first define three utility functions:

• distance_points: Calculates the absolute distance between two points
• distance_tour: Calculates the total distance the salesperson has to cover in a given tour
• generate_cities: Randomly generates a set of n cities located in a rectangle of width 500 and height 300

Let's look at the following code:

import random
from itertools import permutations
alltours = permutations 

def distance_tour(aTour):
    return sum(distance_points(aTour[i - 1], aTour[i]) 
               for i in range(len(aTour)))

aCity = complex

def distance_points(first, second): return abs(first - second)

def generate_cities (number_of_cities):
    seed=111;width=500;height=300
    random.seed((number_of_cities, seed))
    return frozenset(aCity(random.randint(1, width), random.randint(1, height))
                     for c in range(number_of_cities))

In the preceding code, we implemented alltours from the permutations function of the itertools package. We have also represented the distance with a complex number. This means the following:

• Calculating the distance between two cities, a and b, is as simple as distance (a,b),
• We can create n number of cities just by calling generate_cities(n).

Now let's define a function, brute_force, that generates all the possible tours of the cities. Once it has generated all possible tours, it will choose the one with the shortest distance:

def brute_force(cities):
    "Generate all possible tours of the cities and choose the shortest 
     tour."
    return shortest_tour(alltours(cities))

def shortest_tour(tours): return min(tours, key=distance_tour)

Now let's define the utility functions that can help us plot the cites. We will define the following functions:

• visualize_tour: Plots all the cities and links in a particular tour. It also highlights the city from where the tour started.
• visualize_segment: Used by visualize_tour to plot cites and links in a segment.

Look at the following code:

%matplotlib inline
import matplotlib.pyplot as plt
def visualize_tour(tour, style='bo-'): 
    if len(tour) > 1000: plt.figure(figsize=(15, 10))
    start = tour[0:1]
    visualize_segment(tour + start, style)
    visualize_segment(start, 'rD') 
    
def visualize_segment (segment, style='bo-'):
    plt.plot([X(c) for c in segment], [Y(c) for c in segment], style, clip_on=False)
    plt.axis('scaled')
    plt.axis('off')
    
def X(city): "X axis"; return city.real
def Y(city): "Y axis"; return city.imag

Let's implement a function, tsp(), that does the following:

1. Generates the tour based on the algorithm and number of cities requested
2. Calculates the time it took for the algorithm to run
3. Generates a plot

Once tsp() is defined, we can use it to create a tour:

Note that we have used it to generate the tour for 10 cities. As n = 10, it will generate (10-1)! = 362,880 possible permutations. If n increases, the number of permutations sharply increases and the brute-force method cannot be used.