* Entrada de parámetros de configuración:
>Parámetro 1 (Número de CPUs/Hilos):
Mi PC consta de una CPU Intel Core 2 Duo (2 núcleos), por lo que lo ideal en este caso seria indicarle 2 Hilos (Fig.1)
 |
| Fig 1. Test velocidad según número de hilos ejecutados simultáneamente [sobre una CPU Intel Core 2 Duo]
>Parámetro 2 (Precisión):
En el ejemplo consta de 13 nodos que permite hasta un total de 6.227.020.800 rutas distintas. Si le indicamos una precisión de 100.000.000 interacciones obtendremos una ruta bastante óptima con un 18.84% de probabilidades de dar con la ruta más corta posible.
|
 |
| Fig. 2 - Relación entre el Número Interacciones (método Montecarlo) con el % de probabilidades de dar con la ruta más óptima posible. |
Código 1 (TSP_Optimizar.java):
package tsp_optimitzar;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class TSP_Optimitzar {
@SuppressWarnings("empty-statement")
public static void main(String[] args) throws InterruptedException {
String[] nombre_nodos = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"};
int nNodos = nombre_nodos.length;
System.out.println("Configuración:\n");
System.out.println(">Número de CPUs/Hilos?");
Scanner reader = new Scanner(System.in);
int nHilos = Integer.parseInt(reader.next());
System.out.println(">Precisión?");
reader = new Scanner(System.in);
double precision = Double.parseDouble(reader.next());
float[] vDistancias = {
0.0F, 820.8666F, 475.23F, 630.9444F, 175.44064F, 360.75314F, 755.7496F, 186.8207F, 591.06683F, 298.11227F, 681.6526F, 289.17914F, 995.64746F,
8.357133F, 0.0F, 366.78992F, 83.80908F, 217.9351F, 237.86781F, 581.63153F, 925.394F, 453.48624F, 636.67017F, 200.24031F, 695.21234F, 890.6944F,
70.59399F, 368.34445F, 0.0F, 764.7878F, 182.2146F, 93.2886F, 194.98314F, 180.56621F, 363.5746F, 443.70917F, 641.6165F, 549.982F, 931.1095F,
874.7707F, 874.603F, 605.9038F, 0.0F, 25.786762F, 147.78946F, 533.5506F, 47.42154F, 108.01653F, 471.1008F, 261.24738F, 656.25104F, 99.16098F,
4.8551674F, 361.6684F, 245.69385F, 652.172F, 0.0F, 100.449036F, 633.9419F, 670.09125F, 150.59242F, 907.34863F, 275.1372F, 938.0571F, 38.05818F,
652.2065F, 238.30981F, 927.4687F, 318.43414F, 429.15936F, 0.0F, 595.4067F, 431.22238F, 388.80447F, 283.0264F, 249.39452F, 8.14694F, 899.722F,
671.8014F, 811.3296F, 355.1809F, 8.395913F, 157.35182F, 596.0345F, 0.0F, 306.99182F, 192.86949F, 298.59897F, 432.59073F, 633.6216F, 817.70074F,
301.66046F, 462.99008F, 147.49551F, 730.2186F, 902.4855F, 160.01877F, 485.22964F, 0.0F, 495.07837F, 358.40677F, 555.7709F, 983.111F, 318.58316F,
160.77138F, 3.104256F, 998.9104F, 310.08047F, 295.39194F, 466.86356F, 673.8137F, 499.67224F, 0.0F, 423.98648F, 855.799F, 779.7313F, 947.50555F,
372.0423F, 715.80835F, 866.05927F, 57.02963F, 696.6522F, 65.42037F, 388.12494F, 826.8198F, 912.82697F, 0.0F, 304.32504F, 886.0547F, 788.8762F,
157.58907F, 235.23514F, 575.64496F, 682.70575F, 689.79407F, 57.43567F, 877.0111F, 659.9925F, 658.1151F, 196.0468F, 0.0F, 549.32043F, 440.2496F,
957.9573F, 699.2848F, 57.796417F, 461.52716F, 881.24054F, 752.86084F, 748.3989F, 42.0304F, 459.0128F, 424.106F, 206.15532F, 0.0F, 386.36868F,
69.71372F, 877.4519F, 881.0224F, 954.1217F, 924.6164F, 813.5333F, 743.41473F, 956.4676F, 509.52542F, 867.4073F, 202.12968F, 515.76715F, 0.0F};
List<String> lista_nombre_nodos = new ArrayList<>();
lista_nombre_nodos.addAll(Arrays.asList(nombre_nodos));
// mostrar tabla distancias
tDistancias(vDistancias, nNodos);
System.out.println("\nCalculando...");
long tiempo1 = System.nanoTime();
TSP_Montecarlo tsp[] = new TSP_Montecarlo[nHilos];
for (int i = 0; i < nHilos; i++) {
tsp[i] = new TSP_Montecarlo(lista_nombre_nodos, vDistancias, precision, nHilos);
tsp[i].start();
}
// Control de finalización hilos
int cont;
do {
try { // +15%
Thread.sleep(500);
} catch (Exception e) {
}
cont = 0;
for (int i = 0; i < nHilos; i++) {
if (!tsp[i].isAlive()) {
cont++;
}
}
} while (cont != nHilos);
long tiempo2 = System.nanoTime();
// Balance final hilos
float minimo = Float.MAX_VALUE;
String ruta = "";
System.out.println("\nResultados Hilos:");
for (int i = 0; i < nHilos; i++) {
System.out.println("Thread " + i + ": " + tsp[i].getDistancia());
if (tsp[i].getDistancia() < minimo) {
minimo = tsp[i].getDistancia();
ruta = tsp[i].getRuta();
}
}
// Mostrar resultados
System.out.println("\nResultado más óptimo encontrado: ");
System.out.println("Ruta: " + ruta + "\nDistancia: " + minimo);
System.out.println("Tiempo empleado: " + (tiempo2 - tiempo1) / 1e6 + " ms");
}
private static void tDistancias(float[] vDistancias, int n) {
n = (int) Math.sqrt(vDistancias.length);
double[][] tabla = new double[n][n];
String str;
int cont = 0;
System.out.println("\nTabla distancias:");
for (int x = 0; x < n; x++) {
str = "| ";
for (int y = 0; y < n; y++) {
tabla[y][x] = vDistancias[cont];
str += tabla[y][x] + " | ";
cont++;
}
System.out.println(str);
}
}
}
Código 2 (TSP_Montecarlo.java):
package tsp_optimitzar;
import java.util.List;
import java.util.Random;
public class TSP_Montecarlo extends Thread {
// Entradas
private final List<String> lista_nombre_nodos;
private final float[] v_distancias;
private final double precision;
// Resto variables
private float minimo = Float.MAX_VALUE;
private float sumatorio = 0;
private int[] vRuta = null;
private final int nNodos;
// Contructor
public TSP_Montecarlo(List<String> lista_nombre_nodos, float[] v_distancias, double precision, int nHilos) {
this.lista_nombre_nodos = lista_nombre_nodos;
this.nNodos = lista_nombre_nodos.size();
this.v_distancias = v_distancias;
this.precision = Math.abs(precision / nHilos);
}
@Override
public void run() {
// Control parametros correctos
if (lista_nombre_nodos.size() == Math.sqrt(v_distancias.length)) {
float[][] t_distancias = conversorVT(v_distancias);
int[] aux_perm = new int[nNodos];
int[] perm = new int[nNodos];
Random rnd = new Random();
int aux_nNodos = nNodos;
int cont = 0;
int res;
do {
sumatorio = 0;
// Busqueda de rutas aleatorias evitando repeticiones de nodos.
// +1338%
aux_nNodos = nNodos;
for (int i = 0; i < nNodos; i++) {
aux_perm[i] = i + 1;
}
for (int i = 0; i < nNodos; i++) {
res = rnd.nextInt(aux_nNodos);
perm[i] = aux_perm[res] - 1;
aux_perm[res] = aux_perm[aux_nNodos - 1];
aux_nNodos--;
}
sumatorio += t_distancias[perm[nNodos - 1]][perm[0]];
for (int i = 0; i < (nNodos - 1); i++) {
sumatorio += t_distancias[perm[i]][perm[i + 1]];
if (sumatorio > minimo) { // +200%
break;
}
}
if (sumatorio < minimo) {
minimo = sumatorio;
vRuta = perm.clone();
}
} while (cont++ < precision);
}
}
public float[][] conversorVT(float[] v_distancias) {
float[][] t_distancias = new float[nNodos][nNodos];
int cont = 0;
for (int i = 0; i < nNodos; i++) {
for (int j = 0; j < nNodos; j++) {
t_distancias[j][i] = v_distancias[cont];
cont++;
}
}
return t_distancias;
}
public float getDistancia() {
return minimo;
}
public String getRuta() {
String ruta = lista_nombre_nodos.get(vRuta[0]) + " - ";
for (int i = 1; i < nNodos - 1; i++) {
ruta += lista_nombre_nodos.get(vRuta[i]) + " - ";
}
ruta += lista_nombre_nodos.get(vRuta[nNodos - 1]);
return ruta;
}
}
run:
Configuración:
>Número de CPUs/Hilos?
2
>Precisión?
100000000
Tabla distancias:
| 0.0 | 820.8665771484375 | 475.2300109863281 | 630.9443969726562 | 175.44064331054688 | 360.7531433105469 | 755.7495727539062 | 186.82069396972656 | 591.0668334960938 | 298.1122741699219 | 681.652587890625 | 289.17913818359375 | 995.6474609375 |
| 8.357132911682129 | 0.0 | 366.7899169921875 | 83.80908203125 | 217.9351043701172 | 237.86781311035156 | 581.6315307617188 | 925.3939819335938 | 453.4862365722656 | 636.670166015625 | 200.2403106689453 | 695.2123413085938 | 890.6943969726562 |
| 70.59398651123047 | 368.3444519042969 | 0.0 | 764.7877807617188 | 182.214599609375 | 93.2885971069336 | 194.98313903808594 | 180.5662078857422 | 363.5745849609375 | 443.70916748046875 | 641.6165161132812 | 549.9819946289062 | 931.1094970703125 |
| 874.7706909179688 | 874.60302734375 | 605.90380859375 | 0.0 | 25.786762237548828 | 147.78945922851562 | 533.5505981445312 | 47.421539306640625 | 108.01653289794922 | 471.1007995605469 | 261.24737548828125 | 656.2510375976562 | 99.16098022460938 |
| 4.855167388916016 | 361.66839599609375 | 245.69384765625 | 652.1719970703125 | 0.0 | 100.44903564453125 | 633.94189453125 | 670.0912475585938 | 150.59242248535156 | 907.3486328125 | 275.13720703125 | 938.05712890625 | 38.05818176269531 |
| 652.2064819335938 | 238.309814453125 | 927.4686889648438 | 318.43414306640625 | 429.15936279296875 | 0.0 | 595.4066772460938 | 431.2223815917969 | 388.8044738769531 | 283.0263977050781 | 249.39451599121094 | 8.146940231323242 | 899.7219848632812 |
| 671.8013916015625 | 811.32958984375 | 355.180908203125 | 8.395913124084473 | 157.35182189941406 | 596.0344848632812 | 0.0 | 306.9918212890625 | 192.86949157714844 | 298.5989685058594 | 432.5907287597656 | 633.62158203125 | 817.7007446289062 |
| 301.66046142578125 | 462.9900817871094 | 147.49551391601562 | 730.2186279296875 | 902.4854736328125 | 160.01876831054688 | 485.2296447753906 | 0.0 | 495.078369140625 | 358.4067687988281 | 555.7708740234375 | 983.1110229492188 | 318.5831604003906 |
| 160.77137756347656 | 3.1042559146881104 | 998.910400390625 | 310.0804748535156 | 295.3919372558594 | 466.8635559082031 | 673.813720703125 | 499.6722412109375 | 0.0 | 423.9864807128906 | 855.7990112304688 | 779.7313232421875 | 947.5055541992188 |
| 372.04229736328125 | 715.808349609375 | 866.0592651367188 | 57.02962875366211 | 696.6522216796875 | 65.42037200927734 | 388.12493896484375 | 826.81982421875 | 912.8269653320312 | 0.0 | 304.3250427246094 | 886.0546875 | 788.876220703125 |
| 157.5890655517578 | 235.23513793945312 | 575.6449584960938 | 682.7057495117188 | 689.7940673828125 | 57.4356689453125 | 877.0111083984375 | 659.9924926757812 | 658.1151123046875 | 196.0467987060547 | 0.0 | 549.3204345703125 | 440.2496032714844 |
| 957.957275390625 | 699.2847900390625 | 57.796417236328125 | 461.52716064453125 | 881.2405395507812 | 752.86083984375 | 748.39892578125 | 42.030399322509766 | 459.0127868652344 | 424.1059875488281 | 206.1553192138672 | 0.0 | 386.3686828613281 |
| 69.7137222290039 | 877.451904296875 | 881.0223999023438 | 954.1217041015625 | 924.6163940429688 | 813.5333251953125 | 743.4147338867188 | 956.4675903320312 | 509.5254211425781 | 867.4072875976562 | 202.1296844482422 | 515.7671508789062 | 0.0 |
Calculando...
Resultados Hilos:
Thread 0: 1497.1041
Thread 1: 1340.8267
Resultado más óptimo encontrado:
Ruta: M - E - A - B - I - D - J - G - C - H - L - F - K -
Distancia: 1340.8267
Tiempo empleado: 44039.191597 ms
BUILD SUCCESSFUL (total time: 56 seconds)
Nota: Lo marcado como [// +XXX%] significa el grado de mejora en la eficiencia del algoritmo con respecto a códigos anteriores.
