En este ejemplo se trata de buscar la ruta más corta entre 13 nodos. Para hacerse una idea tiene que elegir una ruta entre 6.227.020.800 posibles.
Requisito: Disponer de una CPU multinúcleo.
Código (TSP_Optimitzar.java):
package tsp_optimitzar;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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"};
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));
int nNodos = nombre_nodos.length;
int nHilos = 4;
// mostrar tabla distancias
tDistancias(vDistancias, nNodos);
System.out.println("\nCalculando...");
TSP_FuerzaBruta tsp[] = new TSP_FuerzaBruta[nHilos];
for (int i = 0; i < nHilos; i++) {
tsp[i] = new TSP_FuerzaBruta(lista_nombre_nodos, vDistancias, nHilos, i + 1);
tsp[i].start();
}
// control de finalización hilos
int cont;
do {
try { // +15%
Thread.sleep(600);
} catch (Exception e) {
}
cont = 0;
for (int i = 0; i < nHilos; i++) {
if (!tsp[i].isAlive()) {
cont++;
}
}
} while (cont != nHilos);
// balance final
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();
}
}
System.out.println("\nResultado más óptimo: ");
System.out.println("Ruta: " + ruta + "\nDistancia: " + minimo);
}
private static void tDistancias(float[] vDistancias, int n) {
n = (int) Math.sqrt(vDistancias.length);
float[][] tabla = new float[n][n];
int cont = 0;
for (int x = 0;
x < n;
x++) {
for (int y = 0; y < n; y++) {
tabla[y][x] = vDistancias[cont];
cont++;
}
}
System.out.println("Tabla distancias:");
String str;
for (int i = 0; i < n; i++) {
str = "| ";
for (int j = 0; j < n; j++) {
str += tabla[j][i] + " | ";
}
System.out.println(str);
str = "";
}
}
}
Código (TSP_FuerzaBruta.java):
package tsp_optimitzar;
import java.util.List;
public class TSP_FuerzaBruta extends Thread {
private final int nNodos;
private final int nHilos;
private final int part;
private int[] v_ruta = null;
private float minimo = Float.MAX_VALUE;
private float sumatorio = 0;
private final List<String> lista_nombre_nodos;
private final float[] v_distancias;
public TSP_FuerzaBruta(List<String> lista_nombre_nodos, float[] v_distancias, int nHilos, int part) {
this.lista_nombre_nodos = lista_nombre_nodos;
this.v_distancias = v_distancias;
this.nNodos = lista_nombre_nodos.size();
this.nHilos = nHilos;
this.part = part;
}
@Override
public void run() {
double beta;
double alfa;
int[] pAlfa = new int[nNodos];
double nPermutacions = Math.abs(Factorial(nNodos) / nNodos);
double div = nPermutacions / nHilos;
alfa = (part - 1) * div;
beta = alfa + Math.abs(div);
TSP_Factoradic p1 = new TSP_Factoradic(nNodos, alfa);
pAlfa = p1.getPermutacion();
float[][] t_distancias = conversorVT(v_distancias);
int[] perm = new int[nNodos];
for (int i = 0; i < nNodos; i++) {
perm[i] = i;
}
System.out.println("Hilo: " + this.getName());
perm = pAlfa.clone();
do {
alfa++;
sumatorio = 0;
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;
v_ruta = perm.clone();
}
} while (nextPermutation(perm) && beta > alfa); // +25%
}
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;
}
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 = "";
for (int i = 0; i < nNodos; i++) {
ruta += lista_nombre_nodos.get(v_ruta[i]) + " - ";
}
return ruta;
}
private double Factorial(int nNodos) {
double factorial = 1;
while (nNodos != 0) {
factorial = factorial * nNodos;
nNodos--;
}
return factorial;
}
}
Código (TSP_Factoradic.java):
package tsp_optimitzar;
public class TSP_Factoradic {
private int[] perm = null;
int[] factoradic;
// n = Número elementos
// k = Indice
public TSP_Factoradic(int n, double k) {
this.perm = new int[n];
// Calcula factoradic de k
factoradic = new int[n];
for (int j = 1; j <= n; ++j) {
factoradic[n - j] = (int) (k % j);
k /= j;
}
// Convierte factorádico a permutación
double[] temp = new double[n];
for (int i = 0; i < n; ++i) {
temp[i] = ++factoradic[i];
}
this.perm[n - 1] = 1;
for (int i = n - 2; i >= 0; --i) {
this.perm[i] = (int) temp[i];
for (int j = i + 1; j < n; ++j) {
if (this.perm[j] >= this.perm[i]) {
++this.perm[j];
}
}
}
for (int i = 0; i < n; ++i) {
--this.perm[i];
}
}
public int[] getFactoradico() {
return factoradic;
}
public int[] getPermutacion() {
return perm;
}
}
Resultado:
run:
Tabla distancias:
| 0.0 | 820.8666 | 475.23 | 630.9444 | 175.44064 | 360.75314 | 755.7496 | 186.8207 | 591.06683 | 298.11227 | 681.6526 | 289.17914 | 995.64746 |
| 8.357133 | 0.0 | 366.78992 | 83.80908 | 217.9351 | 237.86781 | 581.63153 | 925.394 | 453.48624 | 636.67017 | 200.24031 | 695.21234 | 890.6944 |
| 70.59399 | 368.34445 | 0.0 | 764.7878 | 182.2146 | 93.2886 | 194.98314 | 180.56621 | 363.5746 | 443.70917 | 641.6165 | 549.982 | 931.1095 |
| 874.7707 | 874.603 | 605.9038 | 0.0 | 25.786762 | 147.78946 | 533.5506 | 47.42154 | 108.01653 | 471.1008 | 261.24738 | 656.25104 | 99.16098 |
| 4.8551674 | 361.6684 | 245.69385 | 652.172 | 0.0 | 100.449036 | 633.9419 | 670.09125 | 150.59242 | 907.34863 | 275.1372 | 938.0571 | 38.05818 |
| 652.2065 | 238.30981 | 927.4687 | 318.43414 | 429.15936 | 0.0 | 595.4067 | 431.22238 | 388.80447 | 283.0264 | 249.39452 | 8.14694 | 899.722 |
| 671.8014 | 811.3296 | 355.1809 | 8.395913 | 157.35182 | 596.0345 | 0.0 | 306.99182 | 192.86949 | 298.59897 | 432.59073 | 633.6216 | 817.70074 |
| 301.66046 | 462.99008 | 147.49551 | 730.2186 | 902.4855 | 160.01877 | 485.22964 | 0.0 | 495.07837 | 358.40677 | 555.7709 | 983.111 | 318.58316 |
| 160.77138 | 3.104256 | 998.9104 | 310.08047 | 295.39194 | 466.86356 | 673.8137 | 499.67224 | 0.0 | 423.98648 | 855.799 | 779.7313 | 947.50555 |
| 372.0423 | 715.80835 | 866.05927 | 57.02963 | 696.6522 | 65.42037 | 388.12494 | 826.8198 | 912.82697 | 0.0 | 304.32504 | 886.0547 | 788.8762 |
| 157.58907 | 235.23514 | 575.64496 | 682.70575 | 689.79407 | 57.43567 | 877.0111 | 659.9925 | 658.1151 | 196.0468 | 0.0 | 549.32043 | 440.2496 |
| 957.9573 | 699.2848 | 57.796417 | 461.52716 | 881.24054 | 752.86084 | 748.3989 | 42.0304 | 459.0128 | 424.106 | 206.15532 | 0.0 | 386.36868 |
| 69.71372 | 877.4519 | 881.0224 | 954.1217 | 924.6164 | 813.5333 | 743.41473 | 956.4676 | 509.52542 | 867.4073 | 202.12968 | 515.76715 | 0.0 |
Calculando...
Hilo: Thread-0
Hilo: Thread-1
Hilo: Thread-3
Hilo: Thread-2
Resultados Hilos:
Thread 0: 1197.6255
Thread 1: 1525.2883
Thread 2: 1566.8871
Thread 3: 1360.7714
Resultado más óptimo:
Ruta: A - B - I - D - G - C - H - L - F - J - K - M - E -
Distancia: 1197.6255
BUILD SUCCESSFUL (total time: 12 seconds)
