# Perl Weekly Challenge 121: The Travelling Salesman

by Abigail ## Challenge

You are given a N x N matrix containing the distances between N cities.

Write a script to find a round trip of minimum length visiting all N cities exactly once and returning to the start.

BONUS 1: For a given number N, create a random N x N distance matrix and find a solution for this matrix.
BONUS 2: Find a solution for a random matrix of size 15 x 15 or 20 x 20.

### Example

Matrix: [0, 5, 2, 7]
[5, 0, 5, 3]
[3, 1, 0, 6]
[4, 5, 4, 0]

Output:
length = 10
tour = (0 2 1 3 0)


## Discussion

I don't get the bonus challenges. How are they different from the main challenge? Is one N different from another N?

The travelling salesman problem is a famous example of an NP-complete problem. In fact, the problem is NP-hard.

This means, there are no (known) quick algorithms giving an exact solution. Using dynamic programming, the best known algorithms run in time $$\mathcal{O} (n^2 2^n)$$. No algorithm is known which runs in $$\mathcal{o} (2^n)$$.

There are faster heurisitic algorithms known, but they only produce a result which is, with high probability, close to the best solution.

To keep our solutions reasonbly simple, we will use brute force, trying all possible paths, and remembering the shortest. This gives us a running time which is, up to a polynomial factor, $$\mathcal{O} (n!)$$.

## Solution

Since we want a tour, that is, we have to return to the starting city, it doesn't matter where we start. We therefore decide to start and end our tour in the first city.

Hence, we want to find the shortest path from first city to the first city, with the following conditions: we never visit a city twice, and we visit all the cities.

Thus, we create a recursive subroutine (shortest_path) which takes four arguments:

• The matrix with the distances between the cities
• The city we're starting from (from)
• The destination city (to)
• A set of cities to exclude (exclude)

Initially, the set of excluded cities is empty.

We will return two values: the length of the shortest path, and the shortest path itself.

If we have already visited all the other cities, (that is, excluded contains all the cities, except to), there is only one possible path (from from to to), and we return its length, and the one-step path.

Otherwise, for all cities next which aren't from, to, or in exclude we call shortest_path with the matrix, next as the starting city, to as the destination city, and an exclude set consisting for exclude with from added to it. To the result of each call, we add the distance between from and next, and remember the minimum value.

This minimum value will be the result of shortest_path.

### Perl

sub shortest_path ($matrix,$from, $to,$exclude) {
say "shortest_path (matrix, $from,$to, exclude)";
if (1 + keys %$exclude == @$matrix) {
#
# We have excluded everything, except the destination.
# This makes it the only, and hence, shortest path.
#
return ($$matrix [from] [to], [to]); } # # Else, try each node other than from, to, and what's in exclude, # as the first step. Then recurse, and return the shortest. # my shortest = ~0; my @shortest_path; my %new_exclude = (%exclude, from => 1); foreach my next (0 .. @matrix - 1) { next if next == from || next == to ||$$exclude {$next}; my ($length, $path) = shortest_path ($matrix, $next,$to,
\%new_exclude);
say "$next ->$to ==> $length"; if ($shortest > $length + $$matrix [from] [next]) { shortest = length +$$matrix [$from] [$next]; @shortest_path = ($next, @$path); } } return$shortest, \@shortest_path;
}


Reading in the data, calling shortest_path, and printing the results:

my @matrix = map {[split]} <>;

my  ($length,$path) = shortest_path \@matrix, 0, 0, {};
say "$length\n0 @$path";


Find the full program on GitHub.