Problema del viajante de Comercio TSP (VII). Método Held-Karp.

El algoritmo de Held-Karp es una mejora significativa sobre la fuerza bruta en términos de eficiencia, especialmente cuando el número de ciudades es grande. Sin embargo, al igual que la fuerza bruta, Held-Karp es exacto y garantiza encontrar la solución óptima (ruta mas corta posible).

Características:

    1. Método: Utiliza programación dinámica para evitar recalcular subproblemas y, por lo tanto, reduce el número de cálculos necesarios.
    2. Complejidad Computacional: O(n^2 * 2^n). Aunque sigue siendo exponencial, es mucho más eficiente que la fuerza bruta. El algoritmo almacena resultados intermedios en una tabla (memorización), lo que reduce drásticamente el número de cálculos.
    3. Precisión: Siempre encuentra la solución óptima, igual que la fuerza bruta.



Código Java (TSP_HeldKarp.java):

package tsp_heldkarp;

import java.util.Arrays;

public class TSP_HeldKarp {

    public static void main(String[] args) {

        // Matriz de distancias de 16x16
        double[][] distances = {
            {0, 6780, 6332, 5183, 3541, 6777, 9735, 7, 7297, 9569, 9649, 6776, 2841, 6953, 538, 4117},
            {6780, 0, 9200, 7166, 6987, 7864, 8168, 6569, 5755, 5199, 508, 2574, 8282, 5348, 106, 511},
            {6332, 9200, 0, 9806, 3578, 8764, 6077, 9847, 4451, 9042, 3870, 2817, 2318, 7693, 4202, 7622},
            {5183, 7166, 9806, 0, 3518, 4282, 255, 9261, 1766, 9321, 5317, 5747, 6177, 4520, 3900, 7828},
            {3541, 6987, 3578, 3518, 0, 9134, 4385, 8033, 3046, 7208, 3214, 2128, 19, 7763, 1796, 9843},
            {6777, 7864, 8764, 4282, 9134, 0, 4017, 7218, 2483, 5176, 3423, 9862, 6872, 5376, 7486, 4337},
            {9735, 8168, 6077, 255, 4385, 4017, 0, 4140, 2692, 409, 6729, 4045, 4354, 8323, 888, 3671},
            {7, 6569, 9847, 9261, 8033, 7218, 4140, 0, 1894, 9932, 4223, 2703, 932, 2015, 5867, 5244},
            {7297, 5755, 4451, 1766, 3046, 2483, 2692, 1894, 0, 2481, 171, 4352, 9602, 4497, 9916, 8946},
            {9569, 5199, 9042, 9321, 7208, 5176, 409, 9932, 2481, 0, 8364, 6474, 8869, 7058, 2869, 2216},
            {9649, 508, 3870, 5317, 3214, 3423, 6729, 4223, 171, 8364, 0, 109, 7461, 436, 4842, 3091},
            {6776, 2574, 2817, 5747, 2128, 9862, 4045, 2703, 4352, 6474, 109, 0, 2945, 8514, 7882, 2895},
            {2841, 8282, 2318, 6177, 19, 6872, 4354, 932, 9602, 8869, 7461, 2945, 0, 7904, 232, 6090},
            {6953, 5348, 7693, 4520, 7763, 5376, 8323, 2015, 4497, 7058, 436, 8514, 7904, 0, 4406, 103},
            {538, 106, 4202, 3900, 1796, 7486, 888, 5867, 9916, 2869, 4842, 7882, 232, 4406, 0, 3609},
            {4117, 511, 7622, 7828, 9843, 4337, 3671, 5244, 8946, 2216, 3091, 2895, 6090, 103, 3609, 0}
        };

        TSPHK tsp = new TSPHK distances);

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


Código Java (TSPHK.java):

package tsp_heldkarp;

import java.util.HashMap;
import java.util.Map;

public class TSPHK {

    private final double[][] distanceMatrix;
    private final int numCities;
    private final Map<String, Double> memo; // Para almacenar los resultados de subproblemas
    private int[] bestRoute;
    private double bestDistance;

    public TSPHK(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
        this.memo = new HashMap<>();
        this.bestRoute = new int[numCities];
        this.bestDistance = Double.MAX_VALUE;

        // Calcula la mejor ruta y la distancia mínima
        calculateOptimalRoute();
    }

    private void calculateOptimalRoute() {
        int fullSet = (1 << numCities) - 1; // Representación binaria de todos los nodos visitados
        double optimalDistance = heldKarp(0, fullSet);

        reconstructRoute();
        this.bestDistance = optimalDistance;
    }

    private double heldKarp(int position, int set) {
        // Caso base: si solo queda el nodo inicial
        if (set == (1 << position)) {
            return distanceMatrix[0][position];
        }

        String key = position + "," + set;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        double minDistance = Double.MAX_VALUE;

        // Excluimos el nodo actual del conjunto
        int remainingSet = set & ~(1 << position);

        // Evaluamos las posibles rutas
        for (int i = 0; i < numCities; i++) {
            if (i != position && (set & (1 << i)) != 0) {
                double distance = heldKarp(i, remainingSet) + distanceMatrix[i][position];
                if (distance < minDistance) {
                    minDistance = distance;
                }
            }
        }

        memo.put(key, minDistance);
        return minDistance;
    }

    private void reconstructRoute() {
        int[] route = new int[numCities];
        int position = 0;
        int set = (1 << numCities) - 1;

        for (int i = 0; i < numCities; i++) {
            int bestNextCity = -1;
            double minDistance = Double.MAX_VALUE;

            int remainingSet = set & ~(1 << position);

            for (int j = 0; j < numCities; j++) {
                if ((set & (1 << j)) != 0 && j != position) {
                    double currentDistance = heldKarp(j, remainingSet) + distanceMatrix[j][position];
                    if (currentDistance < minDistance) {
                        minDistance = currentDistance;
                        bestNextCity = j;
                    }
                }
            }

            route[i] = position;
            set = set & ~(1 << position);
            position = bestNextCity;
        }

        this.bestRoute = route;
    }

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

    public double getBestDistance() {
        return bestDistance;
    }
}


Resultado:

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