Problema del viajante de Comercio TSP (XIII). Método Aproximación de Christofides.

El Algoritmo de Aproximación de Christofides es un método para resolver el Problema del Viajante de Comercio (TSP).

Características:

Garantía de aproximación: Proporciona una solución que es, como máximo, 3/2 veces el óptimo para instancias que cumplen la desigualdad triangular.
Complejidad: Tiene una complejidad temporal de O(n^3), donde n es el número de ciudades.

Pasos principales:

  1.Construye un árbol de expansión mínima (MST)
  2.Encuentra vértices de grado impar en el MST
  3.Crea un emparejamiento perfecto de mínimo peso para estos vértices
  4.Combina el MST y el emparejamiento para formar un circuito euleriano
  5.Convierte el circuito euleriano en un tour hamiltoniano


Aplicabilidad: Es especialmente útil para instancias del TSP que cumplen la desigualdad triangular.
Eficiencia: Ofrece un buen equilibrio entre calidad de la solución y tiempo de ejecución.
Limitaciones: No garantiza el óptimo global y su rendimiento puede degradarse en instancias que no cumplen la desigualdad triangular.


Código Java (TSP_Christofides.java):

package tsp_christofides;

import java.util.ArrayList;

public class TSP_Christofides {

    public static void main(String[] args) {

        double[][] distanceMatrix = {
            {0, 8128, 823, 8767, 1253, 8827, 5106, 5501, 7097, 8026, 7162, 2260, 4441, 510, 7138, 6509},
            {8128, 0, 6653, 9241, 4344, 7231, 1503, 7145, 6571, 6217, 9412, 9051, 1931, 5817, 8633, 8513},
            {823, 6653, 0, 7900, 1178, 1820, 1262, 678, 9930, 6739, 9965, 908, 9481, 7708, 1874, 9303},
            {8767, 9241, 7900, 0, 589, 9827, 520, 6671, 9859, 4489, 1642, 1045, 1760, 5607, 5053, 7776},
            {1253, 4344, 1178, 589, 0, 5829, 5823, 3482, 9090, 9537, 8507, 3802, 3302, 2944, 8613, 7257},
            {8827, 7231, 1820, 9827, 5829, 0, 9288, 6497, 5442, 4381, 9297, 2086, 1372, 5616, 1981, 3412},
            {5106, 1503, 1262, 520, 5823, 9288, 0, 3242, 5625, 4715, 7754, 2366, 8314, 1360, 623, 3915},
            {5501, 7145, 678, 6671, 3482, 6497, 3242, 0, 1522, 6648, 324, 8704, 7602, 8091, 1608, 1286},
            {7097, 6571, 9930, 9859, 9090, 5442, 5625, 1522, 0, 7740, 7480, 2266, 9346, 967, 9585, 9113},
            {8026, 6217, 6739, 4489, 9537, 4381, 4715, 6648, 7740, 0, 9509, 7830, 5276, 7174, 8535, 2604},
            {7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 9509, 0, 1847, 8948, 9498, 9456, 4716},
            {2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 7830, 1847, 0, 1620, 6634, 7744, 9744},
            {4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 5276, 8948, 1620, 0, 2261, 3892, 7722},
            {510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 7174, 9498, 6634, 2261, 0, 6734, 6447},
            {7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 8535, 9456, 7744, 3892, 6734, 0, 2382},
            {6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 2604, 4716, 9744, 7722, 6447, 2382, 0}
        };

        TSPCh tsp = new TSPCh(distanceMatrix);
        ArrayList<Integer> bestRoute = tsp.solve();
        double bestDistance = tsp.calculateTotalDistance(bestRoute);

        // Verificar la desigualdad triangular
        if (!tsp.checkTriangleInequality()) {
            System.out.println("ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.");
            System.out.println("El resultado puede no ser óptimo o estar alejado del óptimo esperado.\n");
        }

        System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
        System.out.println("Distancia mínima aproximada: " + bestDistance);
    }
}


Código Java (TSPCh.java):

package tsp_christofides;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;

public class TSPCh {

    private final double[][] distanceMatrix;
    private final int numCities;

    public TSPCh(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
        this.numCities = distanceMatrix.length;
    }

    public ArrayList<Integer> solve() {
        ArrayList<int[]> mstEdges = generateMST();
        ArrayList<Integer> oddDegreeNodes = findOddDegreeNodes(mstEdges);
        ArrayList<int[]> perfectMatching = generatePerfectMatching(oddDegreeNodes);
        ArrayList<int[]> eulerianCircuit = combineMSTAndMatching(mstEdges, perfectMatching);
        return findHamiltonianCircuit(eulerianCircuit);
    }

    private ArrayList<int[]> generateMST() {
        boolean[] inMST = new boolean[numCities];
        double[] key = new double[numCities];
        int[] parent = new int[numCities];
        Arrays.fill(key, Double.MAX_VALUE);
        key[0] = 0;
        parent[0] = -1;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingDouble(o -> key[o[0]]));
        pq.add(new int[]{0, -1});

        ArrayList<int[]> mstEdges = new ArrayList<>();

        while (!pq.isEmpty()) {
            int u = pq.poll()[0];
            inMST[u] = true;

            for (int v = 0; v < numCities; v++) {
                if (!inMST[v] && distanceMatrix[u][v] < key[v]) {
                    key[v] = distanceMatrix[u][v];
                    pq.add(new int[]{v, u});
                    parent[v] = u;
                }
            }
        }

        for (int i = 1; i < numCities; i++) {
            mstEdges.add(new int[]{i, parent[i]});
        }

        return mstEdges;
    }

    private ArrayList<Integer> findOddDegreeNodes(ArrayList<int[]> mstEdges) {
        int[] degree = new int[numCities];
        for (int[] edge : mstEdges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        ArrayList<Integer> oddDegreeNodes = new ArrayList<>();
        for (int i = 0; i < numCities; i++) {
            if (degree[i] % 2 != 0) {
                oddDegreeNodes.add(i);
            }
        }

        return oddDegreeNodes;
    }

    private ArrayList<int[]> generatePerfectMatching(ArrayList<Integer> oddDegreeNodes) {
        ArrayList<int[]> perfectMatching = new ArrayList<>();
        boolean[] matched = new boolean[numCities];

        for (int i = 0; i < oddDegreeNodes.size(); i++) {
            if (matched[oddDegreeNodes.get(i)]) {
                continue;
            }

            int minJ = -1;
            double minDistance = Double.MAX_VALUE;

            for (int j = i + 1; j < oddDegreeNodes.size(); j++) {
                if (!matched[oddDegreeNodes.get(j)] && distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)] < minDistance) {
                    minDistance = distanceMatrix[oddDegreeNodes.get(i)][oddDegreeNodes.get(j)];
                    minJ = j;
                }
            }

            matched[oddDegreeNodes.get(i)] = true;
            matched[oddDegreeNodes.get(minJ)] = true;
            perfectMatching.add(new int[]{oddDegreeNodes.get(i), oddDegreeNodes.get(minJ)});
        }

        return perfectMatching;
    }

    private ArrayList<int[]> combineMSTAndMatching(ArrayList<int[]> mstEdges, ArrayList<int[]> perfectMatching) {
        ArrayList<int[]> combinedGraph = new ArrayList<>(mstEdges);
        combinedGraph.addAll(perfectMatching);
        return combinedGraph;
    }

    private ArrayList<Integer> findHamiltonianCircuit(ArrayList<int[]> eulerianCircuit) {
        LinkedHashSet<Integer> visited = new LinkedHashSet<>();
        Stack<Integer> stack = new Stack<>();
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int[] edge : eulerianCircuit) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }

        stack.push(0);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                if (graph.containsKey(node)) {
                    for (int neighbor : graph.get(node)) {
                        stack.push(neighbor);
                    }
                }
            }
        }

        return new ArrayList<>(visited);
    }

    public double calculateTotalDistance(ArrayList<Integer> route) {
        double totalDistance = 0.0;

        for (int i = 0; i < route.size() - 1; i++) {
            int city1 = route.get(i);
            int city2 = route.get(i + 1);
            totalDistance += distanceMatrix[city1][city2];
        }

        totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start city

        return totalDistance;
    }

    public boolean checkTriangleInequality() {
        for (int i = 0; i < numCities; i++) {
            for (int j = 0; j < numCities; j++) {
                for (int k = 0; k < numCities; k++) {
                    if (distanceMatrix[i][j] > distanceMatrix[i][k] + distanceMatrix[k][j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}


Resultado:

run:
ADVERTENCIA: La matriz de distancias no cumple con la desigualdad triangular.
El resultado puede no ser óptimo o estar alejado del óptimo esperado.

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