Código (TSP_FuerzaBruta.java):
package tsp_optimizar;
import java.util.List;
public class TSP_FuerzaBruta {
private final List<String> lista_nombre_nodos;
private final float[] v_distancias;
private float minimo = Float.MAX_VALUE;
float sumatorio = 0;
private String ruta_corta = "";
//Contructor1
public TSP_FuerzaBruta(List<String> lista_nombre_nodos, float[] v_distancias) {
this.lista_nombre_nodos = lista_nombre_nodos;
this.v_distancias = v_distancias;
}
public String getRuta() {
int nNodos = this.lista_nombre_nodos.size();
int[] vDist = new int[nNodos];
for (int i = 0; i < nNodos; i++) {
vDist[i] = i;
}
int[] ruta = null;
if (nNodos == Math.sqrt(v_distancias.length)) {
float[][] tabla_distancias = conversorVT(v_distancias);
do {
sumatorio = 0;
sumatorio += tabla_distancias[vDist[nNodos - 1]][vDist[0]];
for (int i = 0; i < (nNodos - 1); i++) {
sumatorio += tabla_distancias[vDist[i]][vDist[i + 1]];
if (sumatorio > minimo) { // podador (x 2 en velocidad)
break;
}
if (sumatorio > minimo) { // podador (x 2 en velocidad)
break;
}
}
if (sumatorio < minimo) {
minimo = (float) sumatorio;
ruta = vDist.clone();
}
} while (nextPermutation(vDist) && vDist[0] == 0);
for (int i = 0; i < nNodos; i++) {
ruta_corta += lista_nombre_nodos.get(ruta[i]) + " - ";
}
return ruta_corta;
} else {
return null;
}
}
public double getDistanciaRecorrida() {
return minimo;
}
public float[][] conversorVT(float[] vDistancias) {
int nNodos = (int) Math.sqrt(vDistancias.length);
float[][] tDistancias = new float[nNodos][nNodos];
int cont = 0;
for (int i = 0; i < nNodos; i++) {
for (int j = 0; j < nNodos; j++) {
tDistancias[j][i] = vDistancias[cont];
cont++;
}
}
return tDistancias;
}
private static boolean nextPermutation(int[] array) {
int i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i <= 0) {
return false;
}
int j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
int aux = array[i - 1];
array[i - 1] = array[j];
array[j] = aux;
j = array.length - 1;
while (i < j) {
aux = array[i];
array[i] = array[j];
array[j] = aux;
i++;
j--;
}
return true;
}
}
Resultado:
Nodos:
[A, B, C, D, E, F, G, H, I]
Coordenadas:
X: [20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0]
Y: [3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0]
Tabla distancias:
0 2308679 2408318 2886173 3361547 3405877 3352610 4178516 4936598
2308679 0 412310 707106 1615549 1100000 1500000 2061552 2630589
2408318 412310 0 984885 1964688 1077032 1131370 2267156 2624880
2886173 707106 984885 0 1004987 781024 1746424 1360147 2102379
3361547 1615549 1964688 1004987 0 1581138 2716615 1019803 2282542
3405877 1100000 1077032 781024 1581138 0 1216552 1392838 1552417
3352610 1500000 1131370 1746424 2716615 1216552 0 2596150 2334523
4178516 2061552 2267156 1360147 1019803 1392838 2596150 0 1345362
4936598 2630589 2624880 2102379 2282542 1552417 2334523 1345362 0
Calculando ruta...
A - B - D - E - H - I - F - G - C -
Distancia recorrida:
126.94599
BUILD SUCCESSFUL (total time: 0 seconds)
Notas: Más adelante intentaré aprovechar los actuales CPUs Multinúcleos para lograr ganar aun más velocidad. Y en última instancia el uso de las GPUs de las tarjetas gráficas Nvidia mediante la librería jCuda.
