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`

.

`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)`

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!)\).

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`

.

```
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.