Problema del viajante de Comercio TSP (VIII). Método Ramificación y Poda (Branch and Bound).

El código implementa el algoritmo Ramificación y Poda (TSPBB) para resolver el Problema del Viajante de Comercio (TSP). Explora sistemáticamente todas las rutas posibles, comenzando desde una ciudad inicial. Utiliza recursión y un array para rastrear ciudades visitadas. Mantiene actualizada la mejor ruta encontrada, podando ramas subóptimas para mejorar la eficiencia. El proceso continúa hasta explorar todas las combinaciones viables, garantizando la solución óptima.

Características:

1. Efectividad: Garantiza encontrar la solución óptima, aunque puede ser lento para un gran número de ciudades debido a su naturaleza exhaustiva.
2. Poda: Descarta ramas subóptimas, mejorando la eficiencia.
3. Exhaustividad: Explora todo el espacio de soluciones viable.
4. Memoria eficiente: Usa backtracking, requiriendo menos memoria que métodos que almacenan todas las soluciones.
5. Determinismo: Siempre produce el mismo resultado para los mismos datos de entrada.


Código Java (TSP_BranchAndBound.java):

package tsp_branchandbound;

import java.util.Arrays;

public class TSP_BranchAndBound {

    public static void main(String[] args) {

        double[][] distances = {
            {0, 4008, 9665, 4771, 1778, 7977, 6458, 4382, 6975, 5656, 1866, 5567, 9295, 6606, 5620, 660},
            {4008, 0, 6944, 5136, 7793, 2325, 1371, 9034, 457, 4749, 8772, 2501, 7517, 9010, 2227, 6696},
            {9665, 6944, 0, 1620, 4822, 5690, 2570, 4991, 5606, 5347, 789, 683, 5823, 3832, 5270, 2851},
            {4771, 5136, 1620, 0, 1537, 2606, 4129, 4096, 924, 7534, 114, 270, 4023, 7169, 5630, 8939},
            {1778, 7793, 4822, 1537, 0, 8463, 4904, 8184, 1695, 204, 4358, 1615, 5363, 2176, 9802, 5605},
            {7977, 2325, 5690, 2606, 8463, 0, 8239, 4344, 6284, 7034, 5428, 373, 8147, 6935, 6579, 1988},
            {6458, 1371, 2570, 4129, 4904, 8239, 0, 3809, 2582, 3048, 1609, 2428, 6958, 5622, 3067, 4746},
            {4382, 9034, 4991, 4096, 8184, 4344, 3809, 0, 9133, 7408, 1592, 9464, 782, 9170, 2441, 8855},
            {6975, 457, 5606, 924, 1695, 6284, 2582, 9133, 0, 971, 7738, 4865, 7364, 6892, 1542, 5583},
            {5656, 4749, 5347, 7534, 204, 7034, 3048, 7408, 971, 0, 9410, 4268, 3898, 8930, 7749, 6348},
            {1866, 8772, 789, 114, 4358, 5428, 1609, 1592, 7738, 9410, 0, 6926, 1324, 7214, 1873, 8162},
            {5567, 2501, 683, 270, 1615, 373, 2428, 9464, 4865, 4268, 6926, 0, 271, 3262, 8201, 4239},
            {9295, 7517, 5823, 4023, 5363, 8147, 6958, 782, 7364, 3898, 1324, 271, 0, 4325, 1593, 8763},
            {6606, 9010, 3832, 7169, 2176, 6935, 5622, 9170, 6892, 8930, 7214, 3262, 4325, 0, 5532, 7356},
            {5620, 2227, 5270, 5630, 9802, 6579, 3067, 2441, 1542, 7749, 1873, 8201, 1593, 5532, 0, 2441},
            {660, 6696, 2851, 8939, 5605, 1988, 4746, 8855, 5583, 6348, 8162, 4239, 8763, 7356, 2441, 0}
        };

        TSPBB tsp = new TSPBB(distances);

        System.out.println("Mejor Ruta: " + Arrays.toString(tsp.getBestRoute()));
        System.out.println("Distancia mínima: " + tsp.getBestDistance());
    }
}


Código Java (TSPBB.java):

package tsp_branchandbound;

public class TSPBB {
    private final double[][] distanceMatrix;
    private final int numCities;
    private final boolean[] visited;
    private final int[] bestRoute;
    private double bestDistance;

    public TSPBB(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
        this.visited = new boolean[numCities];
        this.bestRoute = new int[numCities]; // Sin el regreso al inicio
        this.bestDistance = Double.MAX_VALUE;

        // Iniciar el algoritmo de Ramificación y Poda
        int[] currentRoute = new int[numCities];
        currentRoute[0] = 0; // Comenzar desde la primera ciudad
        visited[0] = true;

        branchAndBound(0, 1, 0.0, currentRoute);
    }

    private void branchAndBound(int currentCity, int level, double currentDistance, int[] currentRoute) {
        // Si hemos visitado todas las ciudades
        if (level == numCities) {
            // Sumar la distancia de regreso a la ciudad inicial
            double totalDistance = currentDistance + distanceMatrix[currentCity][0];

            if (totalDistance < bestDistance) {
                bestDistance = totalDistance;
                System.arraycopy(currentRoute, 0, bestRoute, 0, numCities);
            }
            return;
        }

        for (int i = 0; i < numCities; i++) {
            if (!visited[i]) {
                visited[i] = true;
                currentRoute[level] = i;

                double nextDistance = currentDistance + distanceMatrix[currentCity][i];

                if (nextDistance < bestDistance) {
                    branchAndBound(i, level + 1, nextDistance, currentRoute);
                }

                visited[i] = false;
            }
        }
    }

    public int[] getBestRoute() {
        return bestRoute;
    }

    public double getBestDistance() {
        return bestDistance;
    }
}


Resultado:

run:
Mejor Ruta: [0, 10, 3, 2, 13, 4, 9, 8, 1, 6, 14, 7, 12, 11, 5, 15]
Distancia mínima: 22193.0
BUILD SUCCESSFUL (total time: 2 seconds)