Problema del viajante de comercio TSP (I.1). Cálculo mediante método circundante.

El proyecto trata de resolver el problema de viajante de comercio (TSP) mediante método circundante, que consiste en unir todos los nodos externos. Para este ejemplo utilizaré un sistema de organización mediante el uso de "packages", donde se irán añadiendo clases que posteriormente se importarán al proyecto principal.

* Estructura del proyecto:

Para añadir un nuevo package al proyecto, botón derecho del mouse sobre "Source Packages" - New - Java Package - Package Name: Utilidades.

Código (Ruta.java):

package Tsp;

import Utilidades.Mostrar;
import Utilidades.BuscarRuta;

public class Ruta {

    public static void main(String[] args) {

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

        //Coordenadas cartesianas (x,y)
        double[][] coordenadas_XY = {
            {20, 18, 22, 13, 3, 18, 30, 5, 14, 26, 23},     // X
            {3, 26, 27, 31, 32, 37, 35, 42, 52, 45, 12}};   // Y

        int nodos = coordenadas_XY[0].length;
        double[] ruta = new double[nodos];

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

        //Muestreos
        m.mostrarCoordenadas(coordenadas_XY);
        m.mostrarRuta(ruta, "\nRuta:\n");
    }
}


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 String nodos = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public void mostrarCoordenadas(double[][] t1) {
        char nodo;
        int x, y;
        System.out.println("Coordenadas nodos (x,y):");
        for (int i = 0; i < t1[0].length; i++) {
            nodo = nodos.charAt(i);
            x = (int) t1[0][i];
            y = (int) t1[1][i];
            System.out.println(nodo + " [" + x + ", " + y + "]");
        }
    }

    public void mostrarRuta(double[] az, String msg) {
        String aux = "";
        String aux2;
        for (int i = 0; i < az.length; i++) {
            aux2 = "" + nodos.charAt((int) az[i]);
            //evitar nodos repetidos 
            if (!aux.contains(aux2)) {
                aux += " ? " + aux2;
            }
        }
        System.out.println(msg + aux + " ?");
    }
}


Código (Ordenar.java):

package Utilidades;

public class Ordenar {
    public double[][] getOrdenacio(double[][] xy) {
        double [][] t = xy;
        //ordenar 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:
Coordenadas nodos (x,y):
A [20, 3]
B [18, 26]
C [22, 27]
D [13, 31]
E [3, 32]
F [18, 37]
G [30, 35]
H [5, 42]
I [14, 52]
J [26, 45]
K [23, 12]

Ruta:
? A ? K ? G ? J ? I ? H ? E ?
BUILD SUCCESSFUL (total time: 0 seconds)