Travelling Salesman Problem - TSP

Código básico.
El código supone la existencia de una base de datos de nombre de localizaciones, coordenada X y coordenada Y. El formato del fichero debe ser ascii separado por espacios, un registro por linea. El algoritmo es el más simple posible, con la excepción de que sólo genera un random por intercambio de pares, lo que lo hace más eficaz que si obtuviese un par. Se recomienda drand48() como algoritmo de rand() en perl. Creo que así viene por defecto.

#!/usr/local/bin/perl

open IN, "<"."coordenadas" or die "Cannot open coordenadas";
while ( < IN > ){
      $n++;
      @linea = split /(\s+)/,$_;
      $nombre[$n]=$linea[0];
      $x[$n]=$linea[1];
      $y[$n]=$linea[2];
}
close IN;

for $i (1..$n){
    for $j (1..$i){
	$d[$i][$j]=sqrt( ($x[$i]-$x[$j])**2 + ($y[$i]-$y[$j])**2 ); 
	$d[$j][$i]=$d[$i][$j];
    }
}

for $i (1..$n){ $p[$i]=$i; }                # solución inicial
$p[0]=$p[$n];
# print @p,"\n";

$MIN = 999999999;
while (1){
    $k++;
    $sol=0;
    for $j (1..$n){
	$sol += $d[$p[$j]][$p[$j-1]];
    }
    if ($sol<$MIN){
	$MIN=$sol;
	print "$n lugares, $k solución: distancia $sol\n";
	print "Orden @p\n";
    }
    while (1){
	$i++;
	if ($i>$n){ $i=1; }
	$j =int(1+rand($n));
	$temp0=$d[$p[$i]][$p[$i-1]]+$d[$p[$i]][$p[$i+1]]+$d[$p[$j]][$p[$j-1]]+$d[$p[$j]][$p[$j+1]];
	$temp1=$d[$p[$j]][$p[$i-1]]+$d[$p[$j]][$p[$i+1]]+$d[$p[$i]][$p[$j-1]]+$d[$p[$i]][$p[$j+1]];
	if ($temp0>=$temp1){
	    $temp = $p[$i];
	    $p[$i] = $p[$j];
	    $p[$j] = $temp;
	    $p[0] = $p[$n];
	    last;
	}
    }
}

__END__