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)