#!/usr/local/bin/perl -w

$|=1; # autoflush

$ZONES=17;

open IN, "<", "coordenadas.dat" or die "Cannot open: $!";
while (<IN>){
    next if /^#/;
    chomp;
    s/^\s//;
    $i++;
    ($Provincia[$i], $Ciudad[$i], $y[$i], $x[$i]) = split /\s/;
    if (!defined $x[$i]){ die "$Ciudad[$i]"; }
    ($y1,$y2) = split /\./, $y[$i];
    $y2 = int ((10*$y2/6)*100000);   # due to error in data file input 
    $y[$i]= $y1.".".$y2;
    ($x1,$x2) = split /\./, $x[$i];
    $x2 = int ((10*$x2/6)*100000);
    $x[$i]= $x1.".".$x2;
    $t[$i]= 1;
}
$N=$i;
close IN;

# exit 1;

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

$min = 9e99;
while (1) {
    $lasti = 1 + int (rand($N));
    $t[0]=$t[$lasti];
    do {
	$t[$lasti] = 1+ int (rand($ZONES));
    }until ($t[$lasti] != $t[0]);
#    @sum=();
#    $mini = 9e99;
#    for $j (1..$ZONES){
#	for $i (1..$N){
#	    if ($t[$i]==$j || $i == $lasti){
#		for $k (1..$i-1){
#		    if ($t[$k]==$j || $k == $lasti){
#			$sum[$j] += $d[$i][$k];
#		    }
#		}
#	    }
#	}
#	if ($sum[$j]<$mini){
#	    $mini = $sum[$j];
#	    $sol = $j;
#	}
#    }
#    $t[$lasti] = $sol;
    
    $iter++;
#    @sum= ();
    $func = 0;
#    for $i (1..$ZONES){
    for $i ($t[0], $t[$lasti]){
	$lastsum[$i]=$sum[$i];
	$sum[$i]=0;
	for $j (1..$N){
	    next if ($t[$j]!=$i);
	    for $k (1..$j-1){
		if ($t[$k]==$i){
		    $sum[$i] += $d[$j][$k];
		}
	    }
	}
    }
    for $i (1..$ZONES){
	if (defined $sum[$i]){
	    $func += $sum[$i];     # sum of intracluster distance
	}                          # it is a measure of error, cost
    }
    if ($func < $min){
	print "\n$iter: $N puntos $func coste\n";
	for $i (1..$ZONES){
	    if (defined $sum[$i]){
		print "ZONA $i $sum[$i] ->";
	    }else{ print "ZONA $i ->"; }
	    $count=0;
	    for $j (1..$N){
		if ($t[$j]==$i) {
#		    print " $j";
		    print " $Ciudad[$j]($Provincia[$j])";
		    $count++;
		}
	    }
	    print ", $count ciudades\n";
	}
	$min = $func;
    }else{
	$sum[$t[0]]=$lastsum[$t[0]];
	$sum[$t[$lasti]]=$lastsum[$t[$lasti]];
	$t[$lasti]=$t[0];
    }
    last if $iter > 500_000;
}


__END__

BUGS
  
He vuelto con el tema de la zonificación y he mejorado el script
  (es más rápido) pero se vuelve muy lento para bases de datos grandes
  (más de 700 puntos).