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)