Visitando os Departamentos do Uruguai

Um projeto que eu gostaria de colocar em marcha um dia é o de visitar todos os departamentos do Uruguai. Então, o primeiro passo é ter uma ideia da distância a ser percorrida. Assim, posso avaliar a viabilidade e quanto tempo seria necessário.

Eu comecei com uma tabela de todas as distâncias entre as capitais departamentais. Depois, uma função que percorre recursivamente todas as possibilidades partindo de uma cidade específica. Este não é o problema do caixeiro viajante: não é preciso terminar no mesmo lugar.

Para acelerar a busca, o código corta os ramos da árvore de busca que forem maiores que a menor distância já encontrada. Então, o programa vai acelerando com o tempo. Mesmo assim, ele levou um dia inteiro para encontrar o melhor caminho a partir de Artigas.

A solução encontrada tem 1927km. Ou seja, o projeto é viável, mesmo para ser executado em uma semana.

A tabela abaixo tem todos os passos e as distâncias percorridas em cada um.

Artigas
Rivera	183
Tacuarembó	111
Melo	204
Treinta y Tres	113
Rocha	172
Maldonado	85
Minas	75
Montevideo	122
Canelones	46
Florida	52
Durazno	85
Trindad	41
San José	95
Colonia	108
Mercedes	176
Fray Bentos	31
Paysandú	110
Salto	118

#!/usr/bin/perl
use strict;
use experimental 'smartmatch';

$|=1;

my $capitals={
0=>'Artigas',
1=>'Canelones',
2=>'Colonia',
3=>'Durazno',
4=>'Florida',
5=>'Fray Bentos',
6=>'Maldonado',
7=>'Melo',
8=>'Mercedes',
9=>'Minas',
10=>'Montevideo',
11=>'Paysandú',
12=>'Rivera',
13=>'Rocha',
14=>'Salto',
15=>'San José',
16=>'Tacuarembó',
17=>'Treinta y Tres',
18=>'Trinidad'
};

my $distances=[
  [0,555,611,418,503,435,748,392,435,711,601,325,183,671,207,580,211,503,459],
  [555,0,145,137,52,268,155,378,237,131,46,332,455,220,450,47,344,282,151],
  [611,145,0,218,178,207,301,507,176,276,177,286,549,360,404,108,429,427,176],
  [418,137,218,0,85,201,298,418,170,273,183,229,318,363,348,136,207,424,41],
  [503,52,178,85,0,286,209,329,255,184,98,318,403,274,437,88,292,355,126],
  [435,268,207,201,286,0,422,622,31,395,309,110,452,483,228,220,341,546,160],
  [748,155,301,298,209,422,0,325,391,75,134,487,572,85,605,202,509,212,301],
  [392,378,507,418,329,622,325,0,590,276,387,435,262,285,428,407,204,113,460],
  [435,237,176,170,255,31,391,590,0,363,278,110,452,452,228,189,341,415,129],
  [711,131,276,273,184,395,75,276,363,0,122,463,604,132,582,182,484,164,276],
  [601,46,177,183,98,309,134,387,278,122,0,378,501,210,496,93,390,286,188],
  [325,332,286,229,318,110,487,435,110,463,378,0,342,553,118,285,231,614,190],
  [183,455,549,318,403,452,572,262,452,604,501,342,0,541,335,473,111,373,359],
  [671,220,360,363,274,483,85,285,452,132,210,553,541,0,672,272,490,172,366],
  [207,450,404,348,437,228,605,428,228,582,496,118,335,672,0,403,224,534,309],
  [580,47,108,136,88,220,202,407,189,182,93,285,473,272,403,0,353,327,95],
  [211,344,429,207,292,341,509,204,341,484,390,231,111,490,224,353,0,320,248],
  [503,282,427,424,335,546,212,113,514,164,286,614,373,172,534,327,320,0,427],
  [459,151,176,41,126,160,301,460,129,276,188,190,359,366,309,95,248,427,0]
];

sub print_path {
  my $distance=shift;
  my $marker=shift;
  my @path=@_;
  my @names=map { $capitals->{$_} } @path;
  print "$distance km $marker "; 
  print join '->', @names;
  print "\n";
}

my $limit=3_000;

sub run {
  my $capital=shift;
  my $distance=shift||0;
  my @path=@_;

  if(scalar(@path)==18) { 
    $limit=$distance if $distance<$limit;
    print_path($distance, '*', @path, $capital);
  } else {
    for my $c (0..18) {
      if (!($c~~@path) && $c!=$capital) {
        my $d=$distances->[$capital]->[$c];
        run($c, $distance+$d, @path, $capital) if ($d+$distance)<$limit;
      }  
    }
  }   
}

run(0);

A função run() recebe o índice de uma cidade e recursivamento adiciona todas as outras, uma a uma, até ter um caminho completo. Mas ela aborta qualquer caminho que ultrapasse o valor de $limit, além de atualizar $limit quando encontra um caminho menor.