Perl Weekly Challenge 121: The Travelling Salesman

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;
}

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

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