Aprovechando el código del anterior post TSP(II.1) se modifica ligeramente el fichero "Principal.java" y se crea un nuevo objeto "TSP_Montecarlo.java".
Código (Principal.java):
...
...
...
public void principal() {
Pasar_Arrays_a_Listas();
Pasar_Listas_a_Arrays();
// Calculos v_distancias entre nodos.
double n2 = Math.pow(coordenadas_XY.length, 2);
double[] v_distancias = new double[(int) n2];
v_distancias = getDistancia(coordenadas_XY);
long precision = 1000000;
TSP_Montecarlo tspm = new TSP_Montecarlo(lista_nombre_nodos, v_distancias, precision);
// Mostrar datos
Mostrar_Listas();
Mostrar_Tabla(v_distancias, "\nTabla distancias:");
System.out.println("\nCalculando ruta...");
System.out.println(tspm.getRuta());
System.out.println("\nDistancia recorrida:");
System.out.println((double) tspm.getDistanciaRecorrida() / 100000);
}
...
...
...
Código (TSP_Montecarlo.java):
package Tsp;
import java.util.List;
import java.util.Stack;
public class TSP_Montecarlo {
private final List<String> lista_nombre_nodos;
private final double[] v_distancias;
private final long precision;
private String ruta_corta = "";
private long minim = Long.valueOf("9223372036854775807");
//Contructor
public TSP_Montecarlo(List<String> lista_nombre_nodos, double[] v_distancias, long precision) {
this.lista_nombre_nodos = lista_nombre_nodos;
this.v_distancias = v_distancias;
this.precision = precision;
}
//Método para obtener ruta corta
public String getRuta() {
//Control parametros correctos
if (lista_nombre_nodos.size() == Math.sqrt(v_distancias.length)) {
double[][] tabla_distancias = conversorVT(v_distancias);
int nNodos = lista_nombre_nodos.size();
int vMiniRuta[] = new int[nNodos];
for (int t = 0; t < precision; t++) {
int vRuta[] = new int[v_distancias.length];
double suma = 0;
int pos;
Stack<Integer> pRuta = new Stack<Integer>();
for (int i = 0; i < nNodos; i++) {
pos = (int) Math.floor(Math.random() * nNodos);
while (pRuta.contains(pos)) {
pos = (int) Math.floor(Math.random() * nNodos);
}
pRuta.push(pos);
vRuta[i] = pos;
}
suma += tabla_distancias[vRuta[nNodos - 1]][vRuta[0]];
for (int i = 0; i < (nNodos - 1); i++) {
suma += tabla_distancias[vRuta[i]][vRuta[i + 1]];
if (suma > minim) {//podador
break;
}
}
if (minim > suma) {
minim = (long) suma;
vMiniRuta = vRuta;
}
}
for (int i = 0; i < nNodos; i++) {
ruta_corta += lista_nombre_nodos.get(vMiniRuta[i]) + " - ";
}
return ruta_corta;
} else {
return null;
}
}
public long getDistanciaRecorrida() {
return minim;
}
public double[][] conversorVT(double[] v_distancias) {
int nNodos = (int) Math.sqrt(v_distancias.length);
double[][] tabla_distancias = new double[nNodos][nNodos];
int cont = 0;
for (int i = 0; i < nNodos; i++) {
for (int j = 0; j < nNodos; j++) {
tabla_distancias[j][i] = v_distancias[cont] * 100000;
cont++;
}
}
return tabla_distancias;
}
}
Resultados:
run:
Nodos:
[A, B, C, D, E, F, G, H, I, J, K]
Coordenadas:
X: [20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0, 26.0, 23.0]
Y: [3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0, 45.0, 12.0]
Tabla distancias:
0 2308679 2408318 2886173 3361547 3405877 3352610 4178516 4936598 4242640 948683
2308679 0 412310 707106 1615549 1100000 1500000 2061552 2630589 2061552 1486606
2408318 412310 0 984885 1964688 1077032 1131370 2267156 2624880 1843908 1503329
2886173 707106 984885 0 1004987 781024 1746424 1360147 2102379 1910497 2147091
3361547 1615549 1964688 1004987 0 1581138 2716615 1019803 2282542 2641968 2828427
3405877 1100000 1077032 781024 1581138 0 1216552 1392838 1552417 1131370 2549509
3352610 1500000 1131370 1746424 2716615 1216552 0 2596150 2334523 1077032 2404163
4178516 2061552 2267156 1360147 1019803 1392838 2596150 0 1345362 2121320 3498571
4936598 2630589 2624880 2102379 2282542 1552417 2334523 1345362 0 1389244 4100000
4242640 2061552 1843908 1910497 2641968 1131370 1077032 2121320 1389244 0 3313608
948683 1486606 1503329 2147091 2828427 2549509 2404163 3498571 4100000 3313608 0
Calculando ruta...
K - A - E - H - I - J - G - F - D - B - C -
Distancia recorrida:
137.61998
BUILD SUCCESSFUL (total time: 8 seconds)
