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

$|=1;

open (IN, "<","coordenadas") || die "Cannot open coordenadas:$!";
while (<IN>){
    next if (/^#/);
    next if (/^teco/);
    next if (/^costa/);
    chomp;
    $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];
    }
}

$NN = 8;            # NUMBER OF SALESMEN!
$PUNTOS = $n;
$size= 1+int($PUNTOS/$NN);
$holgura = $size*$NN-$PUNTOS;

$j=1;
$k=0;
for $i (1..$PUNTOS){
    $k++;
    if ($k < $size){
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
    }elsif ($j <= $holgura){
	$p[$j][$k]=-2;
	$k=1;
	$j++;
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
    }else{
	$p[$j][$k]=$i;
	$h[$i]=$j;
	$l[$i]=$k;
	$k=0;
	$j++;
    }
}

$MIN=9e99;
$sqmin=9e99;
$iteracion=0;
for (;;){
    @r=();
    $suma=0;
    for $j (1..$NN){
	for $i (1..$size-1){
	    if ($p[$j][$i+1]>0){
		$r[$j] += $d[ $p[$j][$i] ][ $p[$j][$i+1] ];
		if ($i+1==$size){
		    $r[$j] += $d[ $p[$j][$size] ][ $p[$j][1] ];
		    last;
		}
	    }else{
		$r[$j] += $d[ $p[$j][$i] ][ $p[$j][1] ];
		last;
	    }
	}
	$suma += $r[$j];
    }
    $media = $suma / $NN;
    $sqerr=0;
    for $j (1..$NN){
	$sqerr += ($r[$j]-$media)**2;
    }
    if ($suma<$MIN){
#    if ($sqerr<=$sqmin){
	$kk++;
	$MIN=$suma;
	$sqmin=$sqerr;
	print "\n$0: Problema de $PUNTOS puntos, con $NN vendedores\n";
	print "Iteracion $iteracion, solucion $kk, ";
	printf "distancia %.3f, ",$suma;
	printf "error %.3f\n", $sqerr;
	for $j (1..$NN){
	    print "Viajante $j distancia ";
	    printf "%.3f: ",$r[$j];
	    for $i (1..$size){
		if ($p[$j][$i]>0) { print "$p[$j][$i] "; }
	    }
	    print "\n";
	}
    }
##############################    
loop: 
    
    $iteracion++;
    $z = 1+ int rand($PUNTOS);
#    $z++;
#    if ($z>$PUNTOS) {
#	$z=1;
	$m++;
	if ($m>$PUNTOS){
	    $m =1;
	}
#    }
#    $m = 1+ int rand($PUNTOS);
    if ($z==$m) { goto loop; }
    
    $ii= $h[$z];
    $jj= $h[$m];
    $i = $l[$z];
    $j = $l[$m];
    
#    if ($ii == $jj){
#	$min=($i>$j) ? $j : $i;
#	$max= ($i>$j) ? $i : $j;
#	if ($min > 1 && $max<$size-1){
#	    if ($i == $j+1 || $i == $j-1){
#		$temp0 = $d[$p[$ii][$min-1]][$p[$ii][$min]]
#		  +$d[$p[$ii][$max]][$p[$ii][$max+1]];
#		$temp1 = $d[$p[$ii][$min-1]][$p[$ii][$max]]
#		  +$d[$p[$ii][$min]][$p[$ii][$max+1]];
#		goto vecinos;
#	    }
#	}
#    }
    
    if ($p[$ii][$size]>0){ $ultimo = $p[$ii][$size] ; }
    else { $ultimo = $p[$ii][$size-1]; }
    if ($i-1==0) { $antesz=$ultimo; }
    else { $antesz=$p[$ii][$i-1]; }
    if ($i+1==$size+1 || $p[$ii][$i+1]==-2){ $despuesz=$p[$ii][1]; }
    else { $despuesz=$p[$ii][$i+1]; }
             
    $d1 = $d[$z][ $antesz ] + $d[$z][ $despuesz ];

    if ($p[$jj][$size]>0){ $ultimo = $p[$jj][$size] ; }
    else { $ultimo = $p[$jj][$size-1]; }
    if ($j-1==0) { $antesm=$ultimo; }
    else { $antesm=$p[$jj][$j-1]; }
    if ($j+1==$size+1 || $p[$jj][$j+1]==-2){ $despuesm=$p[$jj][1]; }
    else { $despuesm=$p[$jj][$j+1]; }

    $d2 = $d[$m][ $antesm ] + $d[$m][ $despuesm ];
    $temp0 = $d1+$d2;
    
    $temp1 = $d[$m][ $antesz ] + $d[$m][ $despuesz ];
    $temp1 += $d[$z][ $antesm ] + $d[$z][ $despuesm ];

vecinos:	
    if ($temp0>$temp1){
	$p[$ii][$i]=$m;
	$h[$m]=$ii;
	$l[$m]=$i;
	$p[$jj][$j]=$z;
	$h[$z]=$jj;
	$l[$z]=$j;
    }else { 
	goto loop;
    }
}

__END__
mtsp2: Problema de 223 puntos, con 5 vendedores
  Iteracion 1207340, solucion 184, distancia 3290.094, error 2206596.666
  Viajante 1 distancia 1899.256: 184 90 74 144 128 122 57 95 136 203 186 134
  192 118 52 50 153 187 120 108 148 185 137 24 11 105 72 79 116 76 167 183
  179 25 123 22 143 87 219 159 142 8 222 175
  Viajante 2 distancia 138.600: 132 180 17 196 189 16 96 15 217 114 71 47 7
  198 119 221 160 106 211 147 195 191 150 117 157 216 112 27 204 3 202 169
  214 158 28 99 33 154 121 130 100 207 38 218 103
  Viajante 3 distancia 41.692: 113 135 138 42 173 146 51 162 210 80 85 97
  171 89 163 26 62 149 20 178 208 151 56 126 54 172 29 68 14 59 2 83 6 35
  220 141 170 94 5 140 84 205 45 104
  Viajante 4 distancia 678.449: 12 91 9 23 161 156 129 125 41 37 127 65 36
  64 21 107 63 111 182 197 166 194 66 69 78 40 61 199 201 82 39 181 223 31
  81 155 213 102 115 164 200 44 212 209 109
  Viajante 5 distancia 532.097: 34 46 165 152 32 1 4 93 18 30 49 92 133 13
  145 75 101 48 188 58 168 174 19 193 10 73 131 55 86 110 177 98 190 176 67
  77 43 70 53 88 206 124 60 139 215