Con este método se saca más partido a la CPUs multi-núcleo. Consiste en dividir el problema en varias partes y todas estas partes son ejecutadas simultáneamente mediante el uso de Threads (hilos), reduciendo significativamente el tiempo de cálculo.
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)
