Problema del viajante de comercio TSP (III.2). Optimizando cálculo del método Fuerza Bruta.

Recordamos que el principal problema en el uso del método de Fuerza Bruta es el tiempo necesario para calcular la ruta más óptima. Para lidiar un poco el problema he optimizado el algoritmo del post anterior. Con unas pocas lineas de código de más se consigue un espectacular repunte en la velocidad de cálculo, concretamente alrededor de 80 mil veces más rápido.

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) {

                    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.