#!/usr/bin/perl -w

use strict;

my $DEBUG = 0;

my $puntos = 200;
my $pp = $puntos + 1;

my (@x, @y, @d);

$x[0] = 0;
$y[0] = 0;
for my $i (1..$puntos){
    $x[$i] = 1000 * rand;
    $y[$i] = 1000 * rand;
}

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

my @p;
for (1..$puntos){ $p[$_]=$_; }                # solucin inicial
$p[0]=0;
$p[$pp] = 0;

my $MIN = 9e99;
my ($it, $sol, @popt, $k, $z, $temp0, $temp1);
while (1){
    $it++;
    $sol=0;
    $sol += $d[ $p[$_-1] ][ $p[$_] ]  for (1..$pp);

    if ($sol < $MIN){
        $MIN=$sol;
	my $hora = scalar localtime();
        print "$0 - $puntos lugares, iteración $it, $hora, solución: distancia $sol\n";
        print "Orden: @p\n" if $DEBUG;
	@popt = @p;
    }
        
    do {
        $k++;
        if ($k > $puntos){ $k=1; }
	
        $z = 1 + int(rand() * $puntos);
        
	$temp0 = $d[ $p[$k] ][ $p[$k-1] ] +
	  $d[ $p[$k] ][ $p[$k+1] ] +
	  $d[ $p[$z] ][ $p[$z-1] ] +
	  $d[ $p[$z] ][ $p[$z+1] ];
	
        $temp1 = $d[ $p[$z] ][ $p[$k-1] ] +
	  $d[ $p[$z] ][ $p[$k+1] ] +
	  $d[ $p[$k] ][ $p[$z-1] ] +
	  $d[ $p[$k] ][ $p[$z+1] ];

    }until ($temp0 > $temp1);
    
    ($p[$z], $p[$k]) = ($p[$k], $p[$z]);
#    $p[0] = $p[$pp] = 0;
        
    select (undef, undef, undef, 0.001);
}

__END__


TSP2 - 200 lugares, iteración 89892, solución: distancia 19111.0432466889
  TSP2 - 200 lugares, iteración 89894, solución: distancia 18991.7760340524
  TSP2 - 200 lugares, iteración 89895, solución: distancia 18965.7779594758
  TSP2 - 200 lugares, iteración 109942, solución: distancia 18897.7534974873
  TSP2 - 200 lugares, iteración 109955, solución: distancia 18847.3037635712
  TSP2 - 200 lugares, iteración 110007, solución: distancia 18827.0964903667
  TSP2 - 200 lugares, iteración 110013, solución: distancia 18818.1223774227
  TSP2 - 200 lugares, iteración 110014, solución: distancia 18808.7409046648
  TSP2 - 200 lugares, iteración 110015, solución: distancia 18752.58472048
  TSP2 - 200 lugares, iteración 110016, solución: distancia 18620.9628051282
  TSP2 - 200 lugares, iteración 198939, solución: distancia 18463.5213987781
  TSP2 - 200 lugares, iteración 808746, solución: distancia 18446.7948348543
  TSP2 - 200 lugares, iteración 808747, solución: distancia 18445.7714440229
  TSP2 - 200 lugares, iteración 808748, solución: distancia 18442.7617186617
  TSP2 - 200 lugares, iteración 808750, solución: distancia 18245.3229904192
  TSP2 - 200 lugares, iteración 808751, solución: distancia 18200.4315833743
  TSP2 - 200 lugares, iteración 4868762, solución: distancia 18143.7803984699
  TSP2 - 200 lugares, iteración 5734601, solución: distancia 18131.6370477894
  TSP2 - 200 lugares, iteración 5734602, solución: distancia 18015.4952583797
  TSP2 - 200 lugares, iteración 5734603, solución: distancia 17804.0856918363
  TSP2 - 200 lugares, iteración 5734613, solución: distancia 17579.1292655281
  TSP2 - 200 lugares, iteración 5734614, solución: distancia 17489.1625793777