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)

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.

Problema del viajante de comercio TSP (III.1). Cálculo mediante método Fuerza Bruta.

En este nuevo ejemplo se usará el método de "Fuerza Bruta" para el cálculo del TSP, que consiste en calcular todas las combinaciones de rutas posibles quedándose con la ruta de menor coste o recorrido. 
Ventaja: Muestra el resultado más óptimo posible.
Desventaja: Tiempo de cálculo muy costoso.



Código (Ruta.java):

package Tsp;

public class Ruta {
    public static void main(String[] args) {
        Principal p = new Principal();
        p.principal();
    }
}



Código (Principal.java):

package Tsp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Principal {
    
    String[] nombre_nodos = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};
    Double[] coordenadasX = {20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0};
    Double[] coordenadasY = {3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0};

    List<String> lista_nombre_nodos = new ArrayList<>();
    List<Double> lista_coordenadasX = new ArrayList<>();
    List<Double> lista_coordenadasY = new ArrayList<>();

    String[] v_nodos = new String[lista_nombre_nodos.size()];
    double[][] coordenadas_XY;
    double[] ruta;

    public void principal() {

        Pasar_Arrays_a_Listas();
        Pasar_Listas_a_Arrays();

        // Calculos v_distancias entre nodos.  
        double n2 = Math.pow(coordenadas_XY.length, 2);
        double[] v_distancias = new double[(int) n2];
        v_distancias = getDistancia(coordenadas_XY);

        TSP_FuerzaBruta tspfb = new TSP_FuerzaBruta(lista_nombre_nodos, v_distancias);

        // Mostrar datos
        Mostrar_Listas();
        Mostrar_Tabla(v_distancias, "\nTabla distancias:");
        System.out.println("\nCalculando ruta...");
        System.out.println(tspfb.getRuta());
        System.out.println("\nDistancia recorrida:");
        System.out.println((double) tspfb.getDistanciaRecorrida() / 100000);

    }

    private void Pasar_Arrays_a_Listas() {
        lista_nombre_nodos.addAll(Arrays.asList(nombre_nodos));
        lista_coordenadasX.addAll(Arrays.asList(coordenadasX));
        lista_coordenadasY.addAll(Arrays.asList(coordenadasY));
    }

    private void Pasar_Listas_a_Arrays() {
        v_nodos = lista_nombre_nodos.toArray(v_nodos);
        coordenadas_XY = new double[lista_coordenadasX.size()][lista_coordenadasY.size()];
        for (int i = 0; i < coordenadas_XY.length; i++) {
            coordenadas_XY[0][i] = lista_coordenadasX.get(i);
            coordenadas_XY[1][i] = lista_coordenadasY.get(i);
        }
    }

    private void Mostrar_Listas() {
        System.out.println("\nNodos:\n" + lista_nombre_nodos);
        System.out.println("\nCoordenadas:");
        System.out.println("X: " + lista_coordenadasX);
        System.out.println("Y: " + lista_coordenadasY);
    }

    public void Mostrar_Tabla(double[] v1, String msg) {
        System.out.println(msg);
        int n = (int) Math.sqrt(v1.length);
        double t1[][] = new double[n][n];
        int cont = 0;
        String aux = "";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t1[j][i] = v1[cont];
                aux += ((int) (t1[j][i] * 100000)) + "\t";
                cont++;
            }
            System.out.println(aux);
            aux = "";
        }
    }

    public double[] getDistancia(double[][] xy) {
        int cont = 0;
        double[] v1 = new double[xy[0].length * xy[0].length];
        for (int i = 0; i < xy[0].length; i++) {
            for (int j = 0; j < xy[0].length; j++) {
                v1[cont] = Math.sqrt(Math.pow((xy[0][i] - xy[0][j]), 2) + Math.pow((xy[1][i] - xy[1][j]), 2));
                cont++;
            }
        }
        return v1;
    }

}



Código (TSP_FuerzaBruta.java):

package Tsp;

import java.util.List;

public class TSP_FuerzaBruta {

    private final List<String> lista_nombre_nodos;
    private final double[] v_distancias;
    private String ruta_corta = "";
    private long minim = Long.valueOf("9223372036854775807");
    String nodosRef = "0123456789abcdefghijklmnopqrstuwxyz";

    //Contructor
    public TSP_FuerzaBruta(List<String> lista_nombre_nodos, double[] v_distancias) {
        this.lista_nombre_nodos = lista_nombre_nodos;
        this.v_distancias = v_distancias;
    }

    //Método para obtener ruta corta
    public String getRuta() {
        //Control parametros correctos
        if (lista_nombre_nodos.size() == Math.sqrt(v_distancias.length)) {
            double[][] tabla_distancias = conversorVT(v_distancias);
            int nNodos = lista_nombre_nodos.size();
            int vMiniRuta[] = new int[nNodos];
            String nodos = nodosRef.substring(0, nNodos);
            String ruta = "";
            long index = 0;
            while (ruta.length() <= nNodos) {
                int vRuta[] = new int[v_distancias.length];
                double suma = 0;
                ruta = Long.toString(index, nNodos);
                // control del 0
                if (ruta.length() == nNodos - 1) {
                    ruta = "0" + ruta;
                }
                if (ruta.length() == nNodos) {                    
                    if (validar(ruta, nodos)) { // eliminar repetidos
                        for (int i = 0; i < ruta.length(); i++) {
                            vRuta[i] = Integer.parseInt("" + ruta.charAt(i), 36);
                        }
                        // calculo distancias
                        suma += tabla_distancias[vRuta[nNodos - 1]][vRuta[0]];
                        for (int i = 0; i < (nNodos - 1); i++) {
                            suma += tabla_distancias[vRuta[i]][vRuta[i + 1]];
                            if (suma > minim) { // podador
                                break;
                            }
                        }
                        if (minim > suma) {
                            minim = (long) suma;
                            vMiniRuta = vRuta;
                        }                        
                    }
                }
                index++;
            }            
            for (int i = 0; i < nNodos; i++) {
                ruta_corta += lista_nombre_nodos.get(vMiniRuta[i]) + " - ";
            }
            return ruta_corta;
        } else {
            return null;
        }
    }

    public long getDistanciaRecorrida() {
        return minim;
    }

    public double[][] conversorVT(double[] v_distancias) {
        int nNodos = (int) Math.sqrt(v_distancias.length);
        double[][] tabla_distancias = new double[nNodos][nNodos];
        int cont = 0;
        for (int i = 0; i < nNodos; i++) {
            for (int j = 0; j < nNodos; j++) {
                tabla_distancias[j][i] = v_distancias[cont] * 100000;
                cont++;
            }
        }
        return tabla_distancias;
    }

    private static boolean validar(String ruta, String nodos) {
        for (int i = 0; i < nodos.length(); i++) {
            if (!ruta.contains("" + nodos.charAt(i))) {
                return false;
            }
        }
        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: 7 minutes 25 seconds)