Problema del viajante de comercio TSP (III.3). Cálculo por fuerza bruta aprovechando las CPUs multi-núcleos.

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)

Permutaciones: Conversor sistema decimal a factorádico y a permutación.

El sistema de numeración factorádico proporciona un índice lexicográfico para permutaciones. En este ejemplo se pasa del sistema decimal a factorádico y este a su vez a permutación.


Código (permutar4.java):

package permutar4;

import java.util.Arrays;

public class Permutar4 {

    public static void main(String[] args) {
        int indice = 90;
        int nElementos = 5;
        Permutation p1 = new Permutation(nElementos, indice);
        System.out.println("Elementos:\n" + nElementos);
        System.out.println("Decimal:\n" + indice);
        System.out.println("Factorádico:");
        System.out.println(Arrays.toString(p1.getFactoradico()));
        System.out.println("La 90 permutación de orden 5 es:");
        System.out.println(Arrays.toString(p1.getPermutacion()));
    }

}



Código (Permutation.java):


package permutar4;

public class Permutation {

    private int[] perm = null;

    int[] factoradic;

    public Permutation(int n, int k) {

        this.perm = new int[n];

        // Calcular factorádico de k
        factoradic = new int[n];

        for (int j = 1; j <= n; ++j) {
            factoradic[n - j] = k % j;
            k /= j;
        }

        // Convertir factoradic a permutación
        int[] temp = new int[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] = 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:
Elementos:
5
Decimal:
90
Factorádico:
[4, 4, 1, 1, 1]
La 90 permutación de orden 5 es:
[3, 4, 0, 1, 2]
BUILD SUCCESSFUL (total time: 0 seconds)

Permutaciones: Sin repetición / Importa orden. (forma no recursiva)

Código:

//* Permutaciones (Forma no recursiva)
//- Importa posición
//- Sin repetición
package permutar3;

import java.util.Arrays;

public class Permutar3 {

    public static void main(String[] args) {
        int[] perm = {0, 1, 2, 3, 4, 5};
        do {
            System.out.println(Arrays.toString(perm));
        } while (nextPermutation(perm));
    }

    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 temp = array[i - 1];
        array[i - 1] = array[j];
        array[j] = temp;

        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
        return true;
    }
}

Resultado:

run:

[0, 1, 2, 3, 4, 5]

[0, 1, 2, 3, 5, 4]

[0, 1, 2, 4, 3, 5]

[0, 1, 2, 4, 5, 3]

[0, 1, 2, 5, 3, 4]

[0, 1, 2, 5, 4, 3]

[0, 1, 3, 2, 4, 5]

[0, 1, 3, 2, 5, 4]

...

...

...

[5, 4, 2, 3, 0, 1]

[5, 4, 2, 3, 1, 0]

[5, 4, 3, 0, 1, 2]

[5, 4, 3, 0, 2, 1]

[5, 4, 3, 1, 0, 2]

[5, 4, 3, 1, 2, 0]

[5, 4, 3, 2, 0, 1]

[5, 4, 3, 2, 1, 0]

BUILD SUCCESSFUL (total time: 0 seconds)