Problema del viajante de comercio TSP (II.2). Cálculo mediante método Montecarlo.

En este ejemplo se usará el método Montecarlo para el cálculo del TSP. Básicamente consiste en calcular muchas rutas aleatorias quedándose finalmente con la ruta que obtenga menor coste o recorrido.
Aprovechando el código del anterior post TSP(II.1) se modifica ligeramente el fichero "Principal.java" y se crea un nuevo objeto "TSP_Montecarlo.java".


Código (Principal.java):

...
...
...
    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);

        long precision = 1000000;
        TSP_Montecarlo tspm = new TSP_Montecarlo(lista_nombre_nodos, v_distancias, precision);

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

    }
...
...
...


Código (TSP_Montecarlo.java):

package Tsp;

import java.util.List;
import java.util.Stack;

public class TSP_Montecarlo {

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

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

    //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];
            for (int t = 0; t < precision; t++) {
                int vRuta[] = new int[v_distancias.length];
                double suma = 0;
                int pos;
                Stack<Integer> pRuta = new Stack<Integer>();
                for (int i = 0; i < nNodos; i++) {
                    pos = (int) Math.floor(Math.random() * nNodos);
                    while (pRuta.contains(pos)) {
                        pos = (int) Math.floor(Math.random() * nNodos);
                    }
                    pRuta.push(pos);
                    vRuta[i] = pos;
                }
                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;
                }
            }
            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;
    }

}

Resultados:

run:

Nodos:
[A, B, C, D, E, F, G, H, I, J, K]

Coordenadas:
X: [20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0, 26.0, 23.0]
Y: [3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0, 45.0, 12.0]

Tabla distancias:
0 2308679 2408318 2886173 3361547 3405877 3352610 4178516 4936598 4242640 948683
2308679 0 412310 707106 1615549 1100000 1500000 2061552 2630589 2061552 1486606
2408318 412310 0 984885 1964688 1077032 1131370 2267156 2624880 1843908 1503329
2886173 707106 984885 0 1004987 781024 1746424 1360147 2102379 1910497 2147091
3361547 1615549 1964688 1004987 0 1581138 2716615 1019803 2282542 2641968 2828427
3405877 1100000 1077032 781024 1581138 0 1216552 1392838 1552417 1131370 2549509
3352610 1500000 1131370 1746424 2716615 1216552 0 2596150 2334523 1077032 2404163
4178516 2061552 2267156 1360147 1019803 1392838 2596150 0 1345362 2121320 3498571
4936598 2630589 2624880 2102379 2282542 1552417 2334523 1345362 0 1389244 4100000
4242640 2061552 1843908 1910497 2641968 1131370 1077032 2121320 1389244 0 3313608
948683 1486606 1503329 2147091 2828427 2549509 2404163 3498571 4100000 3313608 0

Calculando ruta...
K - A - E - H - I - J - G - F - D - B - C - 

Distancia recorrida:
137.61998
BUILD SUCCESSFUL (total time: 8 seconds)