Task — The travelling salesman

You are given a NxN 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.

Examples

Example 1
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)

Analysis

The Travelling Salesman Problem was first described in 1832 and has been the subject of many mathematical analyses and attempts to solve it in less than O(N^2!) time. Wikipedia has a lot of information on the subject.

I assumed that the intention of the matrix is that the distance from i to j was found at row i, column j. However, that means that the distance from, say, point 2 to point 3 in the example is 6 whereas the distance in the opposite direction is 4, which is a little strange, but never mind.

My solution simply enumerates all the possible permutations of points visited and finds the shortest. This works on my computer in negligible time for an 8x8 matrix, in around 4 seconds for 9x9 and 35 seconds for 10x10. Clearly it is not a sensible approach for, say, a 20x20 matrix.

Although travelling salesmen are a dying breed, we might rename it the Amazon Driver Problem, and in my career I have had to provide solutions to such a problem twice. Fortunately, in real life, the absolute optimum journey is not needed, and there are ways to get close in a reasonable time.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-07-12
use utf8;     # Week 121 - task 2 - Travelling salesman
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'permutations';

travelling_salesman(
   [[0, 5, 2, 7],
    [5, 0, 5, 3],
    [3, 1, 0, 6],
    [4, 5, 4, 0]]);
    
# make randomised matrix
my ($size, $i, $j, $m, $n); 
$size = 10;
for $i (0 .. $size - 1) {
    for $j ($i + 1 .. $size) {
        $n = int(rand(500));
        $m->[$i]->[$j] = $m->[$j]->[$i] = $n;
    }
    $m->[$i]->[$i] = 0;
}
$m->[$size]->[$size] = 0;
travelling_salesman($m);

sub travelling_salesman {
    
    my ($from_to, $best, @iterator, $case, $this, $path, 
        $j, $starts, $best_tour);
    
    # initialise
    $from_to = $_[0];
    $best = 1e6;
    
    # create iterator, eg 1234
    $iterator[$_ - 1] = $_ for 1 .. @$from_to - 1;
    $starts = $#iterator;
    
    # calculate journey lengths
    $case = permutations(\@iterator);
    
    # calculate length of possible journeys
    while ($this = $case->next) {
        $path = 0;
        
        # add up point to point distances
        for $j (0 .. $starts - 1) {
            $path += $from_to->[$this->[$j]]->[$this->[$j + 1]];
        }

        # add point 0 to first point on path
        $path += $from_to->[0]->[$this->[0]]; 
        
        # and last point on path to point 0
        $path += $from_to->[$this->[$starts]]->[0];
            
        # found a better one
        if ($path < $best) {
            $best = $path;
            $best_tour = '0 ' . join(' ', @$this) . ' 0';

        }
    }
    print qq[\n];
    print_matrix('Input: ', $from_to);
    say qq[Output: $best ($best_tour)];
}

sub print_matrix {
    
    my ($legend, $matrix, $j);

    # format matrix
    ($legend, $matrix) = @_;
    for $j (0 .. @$matrix - 1) {
        print qq{$legend [} . join(', ', @{$matrix->[$j]}) . qq(]);
        say $j == @$matrix - 1 ? '' : ', ';
        $legend = ' ' x length($legend);
    }
}

last updated 2026-03-12 — 27 lines of code

Output

Input:  [0, 5, 2, 7], 
        [5, 0, 5, 3], 
        [3, 1, 0, 6], 
        [4, 5, 4, 0]
Output: 10 (0 2 1 3 0)

Input:  
[0,   443, 422, 415, 168, 462, 369, 106, 469, 330, 339], 
[443,   0, 220, 152, 125,  77, 162, 249, 389, 354, 286], 
[422, 220,   0, 319,  78, 226, 310, 411, 244, 108,  22], 
[415, 152, 319,   0,  99, 117, 330, 424, 309, 319, 198], 
[168, 125,  78,  99,   0, 229, 294,  69, 272, 253, 450], 
[462,  77, 226, 117, 229,   0, 207, 217, 485, 176, 272], 
[369, 162, 310, 330, 294, 207,   0, 216, 484, 306, 100], 
[106, 249, 411, 424,  69, 217, 216,   0, 358, 402, 155], 
[469, 389, 244, 309, 272, 485, 484, 358,   0, 128, 405], 
[330, 354, 108, 319, 253, 176, 306, 402, 128,   0, 359], 
[339, 286,  22, 198, 450, 272, 100, 155, 405, 359,   0]
Output: 1445 (0 4 3 5 1 6 10 2 9 8 7 0)