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)

Problema del viajante de comercio TSP (II.1). Cálculo distancias entre nodos.

En este apartado se trata de calcular las distancias entre los nodos para luego mostrarlas en pantalla en formato tabla simétrica.
Para el cálculo de distancias entre coordenadas cartesianas en un plano(2D) se utiliza el teorema de Pitágoras:

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", "J", "K"};
    Double[] coordenadasX = {20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0, 26.0, 23.0};
    Double[] coordenadasY = {3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0, 45.0, 12.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();

        // Cálculos distancias entre nodos.  
        double n2 = Math.pow(coordenadas_XY.length, 2);
        double[] distancias = new double[(int) n2];
        distancias = getDistancia(coordenadas_XY);

        // Mostrar datos
        Mostrar_Listas();
        Mostrar_Tabla(distancias, "\nTabla distancias:");

    }

    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] * 10000)) + "\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;
    }

}


Resultado:

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
BUILD SUCCESSFUL (total time: 0 seconds)

Problema del viajante de comercio TSP (I.2). Reestructuración método circundante.

Esta vez se modifica el código del TSP (I.1) para dejarlo algo más reestructurado. También se realizan cambios menores como uso de listas y coordenadas con decimales...


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 Utilidades.BuscarRuta;
import Utilidades.Mostrar;
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", "J", "K"};
    Double[] coordenadasX = {20.0, 18.0, 22.0, 13.0, 3.0, 18.0, 30.0, 5.0, 14.0, 26.0, 23.0};
    Double[] coordenadasY = {3.0, 26.0, 27.0, 31.0, 32.0, 37.0, 35.0, 42.0, 52.0, 45.0, 12.0};

    Mostrar m = new Mostrar();
    BuscarRuta br = new BuscarRuta();

    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
        ruta = new double[coordenadas_XY[0].length];
        Cacular_Ruta();
        Mostrar_Listas();
        m.mostrarRuta(ruta, v_nodos);

    }

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

    }

    private void Cacular_Ruta() {

        for (int i = 0; i < br.getRuta(coordenadas_XY).size(); i++) {
            if (!br.getRuta(coordenadas_XY).contains(ruta[i])) {
                ruta[i] = br.getRuta(coordenadas_XY).get(i);
            }
        }
    }

}


Código (Angulo.java):

package Utilidades;

public class Angulo {

    public double getAngle(double x, double y, double x2, double y2, double px, double py, double px2, double py2) {

        double pendent1, pendent2, radians, graus;

        pendent1 = (y2 - y) / (x2 - x);
        pendent2 = (py2 - py) / (px2 - px);

        radians = Math.atan((pendent2 - pendent1) / (1 + (pendent2 * pendent1)));
        graus = (180 * radians) / Math.PI;   
     
        // cuadrante4
        if (px2 >= x && py2 <= y) {
            graus = 360 + graus;
            if (px2 == x) {
                graus = 270;
            }
            if (py2 == y) {
                graus = 360;
            }
        }

        // cuadrante3        
        if (px2 <= x && py2 <= y) {
            graus = 180 + graus;
            if (px2 == x) {
                graus = 270;
            }
            if (py2 == y) {
                graus = 180;
            }
        }

        // cuadrante2
        if (px2 <= x && py2 >= y) {
            graus = 180 + graus;
            if (px2 == x) {
                graus = 90;
            }
            if (py2 == y) {
                graus = 180;
            }
        }

        // cuadrante1
        if (px2 >= x && py2 >= y) {
            if (px2 == x) {
                graus = 90;
            }
            if (py2 == y) {
                graus = 0;
            }
        }

        return graus;
    }

}


Código (BuscarRuta.java):

package Utilidades;

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

public class BuscarRuta {

    public List<Integer> getRuta(double[][] xy) {

        Ordenar orden = new Ordenar();
        double[] base;
        double[][] tg = new double[xy.length][xy[0].length];
        double graus = 1;
        int id;
        base = BuscarMinY(xy);

        List<Integer> lista = new ArrayList<>();
        lista.add((int) base[2]);
        Angulo grau = new Angulo();

        while (true) {
            for (int i = 0; i < xy[0].length; i++) {
                tg[0][i] = i;
                tg[1][i] = grau.getAngle(
                        base[0], base[1], base[0] + 1, base[1], // base
                        base[0], base[1], xy[0][i], xy[1][i]);
            }

            // descarta angulos inferiores
            for (int i = 0; i < tg[0].length; i++) {
                if (tg[1][i] < graus) {
                    tg[1][i] = 999;
                }
            }

            tg = orden.getOrdenacio(tg);
            graus = tg[1][0];
            if (graus >= 999) {
                break;
            }
            id = (int) tg[0][0];
            lista.add(id);
            base[0] = xy[0][id];
            base[1] = xy[1][id];
        }
        return lista;

    }

    public double[] BuscarMinY(double[][] xy) {

        double[] pos_max = new double[3];
        double max = 9999;
        for (int i = 0; i < xy[0].length; i++) {
            if (xy[1][i] < max) {
                max = xy[1][i];
                pos_max[0] = xy[0][i];
                pos_max[1] = xy[1][i];
                pos_max[2] = i;
            }
        }
        return pos_max;

    }    

}


Código (Mostrar.java):

package Utilidades;

public class Mostrar {

    public void mostrarRuta(double[] az, String[] nodos) {

        String aux = "";
        String aux2;
        int contador = 0;

        for (int i = 0; i < nodos.length; i++) {
            aux2 = nodos[(int) az[i]];
            if (!aux.contains("" + aux2)) {
                aux += aux2 + " ? ";
                contador += 1;
            }
        }

        aux = aux.replaceFirst(" ? null", "");
        System.out.println("\nRuta encontrada:\n" + aux);
        System.out.println("\nTasa de resolución: " + contador * 100 / az.length + "%");
        System.out.println("\n");

    }

}

Código (Ordenar.java):

package Utilidades;

public class Ordenar {

    public double[][] getOrdenacio(double[][] xy) {

        double [][] t = xy;

        // Reordenar de menor a mayor
        int cont = 0;
        double aux;
        while (cont < t[0].length) {
            for (int i = 0; i < t[0].length - 1; i++) {
                if (t[1][i] > t[1][i + 1]) {
                    aux = t[1][i];
                    t[1][i] = t[1][i + 1];
                    t[1][i + 1] = aux;                    
                    aux = t[0][i];
                    t[0][i] = t[0][i + 1];
                    t[0][i + 1] = aux;                    
                    cont = 1;
                }
                cont++;
            }
        }
        return t;
    }

}

Resultado:

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]

Ruta encontrada:

A ? K ? G ? J ? I ? H ? E ? 

Tasa de resolución: 63%

BUILD SUCCESSFUL (total time: 0 seconds)