Problema del viajante de comercio TSP (III.4). Cálculo mediante método Vecino Cercano.

El algoritmo de vecino más cercano funciona de la siguiente manera:

    .Se elige una ciudad de inicio.
    .Se selecciona la ciudad más cercana a la ciudad actual, y se añade al camino.
    .Se repite el proceso anterior hasta que se haya visitado todas las ciudades.
    .Se regresa al lugar de origen para completar el ciclo.

El algoritmo de vecino más cercano es una forma rápida y sencilla de encontrar una solución para el TSP, pero no garantiza que sea la solución óptima. En general, el algoritmo tiende a dar buenos resultados para problemas pequeños, pero puede no ser tan efectivo para problemas más grandes.


Código (TSP_MainVecinoCercano.java):

package tsp_mainvecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSP_MainVecinoCercano {

    public static void main(String[] args) {

        int n = 12;
        int[][] distances = new int[n][n];

        // Generar distancias aleatorias
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    distances[i][j] = 0;
                } else {
                    distances[i][j] = (int) (Math.random() * 999 + 1);
                    distances[j][i] = distances[i][j];
                }
            }
        }

        // Imprimir matriz de distancias
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%5d ", distances[i][j]);
            }
            System.out.println();
        }

        TSP_VecinoCercano tsp = new TSP_VecinoCercano(distances);
        List<Integer> path = tsp.findOptimalPath();

        // Pone nombre a los nodos siguiendo la secuencia del abcedario
        List<String> nodeNames = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char letter = (char) ('A' + i);
            nodeNames.add(String.valueOf(letter));
        }

        // Imprimir ruta y distancia recorrida
        System.out.println("\n> Ruta:");
        path.forEach(node -> {
            System.out.print(nodeNames.get(node) + " ");
        });
        System.out.println("\n> La distancia total recorrida es:");
        int totalDistance = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            int node1 = path.get(i);
            int node2 = path.get(i + 1);
            totalDistance += distances[node1][node2];
        }
        System.out.println(totalDistance);
    }

}


Código 2 (TSP_VecinoCercano.java):

package tsp_mainvecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSP_VecinoCercano {

    private final int[][] distances;

    public TSP_VecinoCercano(int[][] distances) {
        this.distances = distances;
    }

    public List<Integer> findOptimalPath() {
        List<Integer> path = new ArrayList<>();
        path.add(0); // Empezamos en el nodo 0

        int currentNode = 0;
        for (int i = 0; i < distances.length - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int nextNode = -1;
            for (int j = 0; j < distances.length; j++) {
                if (distances[currentNode][j] < minDistance && !path.contains(j)) {
                    minDistance = distances[currentNode][j];
                    nextNode = j;
                }
            }
            path.add(nextNode);
            currentNode = nextNode;
        }

        // Volvemos al nodo de origen
        path.add(0);

        return path;
    }

}


Resultado:

run:
    0   138   758   967   823   983   914   935   369   522   282   990
  138     0   997   828   997   770   963   398   590   668   312   716
  758   997     0   849   945   774   952    47   859    52   438   582
  967   828   849     0   556   800   501   589   928   149   409   912
  823   997   945   556     0   856   172   696   375   240   335   887
  983   770   774   800   856     0   213    39   549   694   102    65
  914   963   952   501   172   213     0   164    79   243   646   907
  935   398    47   589   696    39   164     0   205   571   392   504
  369   590   859   928   375   549    79   205     0   167   253   203
  522   668    52   149   240   694   243   571   167     0   475   578
  282   312   438   409   335   102   646   392   253   475     0   314
  990   716   582   912   887    65   907   504   203   578   314     0

> Ruta:
A B K F H C J D G I L E A
> La distancia total recorrida es:
3332
BUILD SUCCESSFUL (total time: 0 seconds)