Se intenta mejorar el algoritmo del TSP Vecino Cercano (TSP VC). Básicamente la mejora consiste en elegir todos los nodos como punto de origen y a partir de ahi calcular las rutas (una ruta para cada nodo de origen) y de todas las rutas realizadas se elige la de menor costo. Se puede resumir de la siguiente manera:
1. El algoritmo comienza seleccionando el primer nodo como punto de origen.
2. A partir de este origen, construye una ruta completa utilizando la heurística del vecino más cercano, es decir, siempre elige el nodo no visitado más cercano como siguiente destino.
3. Una vez completada la ruta, calcula y registra su longitud total.
4. Luego, pasa al siguiente nodo de la lista y lo convierte en el nuevo punto de origen.
5. Repite los pasos 2 y 3 con este nuevo origen, construyendo una nueva ruta completa y registrando su longitud.
6. Este proceso se repite para todos los nodos del grafo, de modo que cada nodo sirve como punto de partida una vez.
7. Finalmente, compara todas las rutas generadas y selecciona la más corta como la solución óptima.
Esta técnica mejora la calidad de la solución al no depender de un único punto de partida arbitrario. Al probar con todos los nodos como puntos de inicio, aumenta la probabilidad de encontrar una solución de mejor calidad para el problema del TSP.
Código (TSP_VecinoCercano.java):
package tsp_vecinocercano;
import java.util.ArrayList;
import java.util.List;
public class TSP_VecinoCercano {
public static void main(String[] args) {
double[][] distances = {
{0, 8718, 6530, 4970, 9334, 8982, 3156, 1176, 2851, 6647, 3224, 7585, 1188, 674, 2976, 6462, 9859, 4383, 413, 8051, 2599, 4309, 6907, 6617, 5877, 40, 9527, 599, 5186, 2204, 958, 6352},
{8718, 0, 5578, 6583, 3220, 373, 8710, 9125, 7310, 5435, 6190, 5, 172, 8327, 9867, 7121, 8150, 7334, 5975, 6283, 3346, 4778, 4260, 2658, 1343, 2078, 5685, 7380, 4178, 4378, 9261, 2925},
{6530, 5578, 0, 3962, 9826, 7362, 2942, 9474, 8696, 702, 4025, 2482, 2835, 2242, 4553, 3010, 8983, 3542, 9294, 2125, 9571, 9825, 2661, 1486, 8266, 1282, 1351, 8665, 4985, 8601, 2280, 9848},
{4970, 6583, 3962, 0, 8376, 7925, 367, 5408, 5804, 1419, 8230, 1472, 6616, 5679, 8119, 3974, 3555, 6723, 8150, 3918, 8549, 697, 6750, 1783, 4507, 5238, 6531, 1172, 3210, 5349, 3911, 4668},
{9334, 3220, 9826, 8376, 0, 9280, 3764, 4344, 9310, 5045, 7951, 6054, 7108, 9809, 2248, 5730, 947, 4696, 1152, 1922, 1549, 3312, 117, 162, 4051, 3235, 4711, 6196, 7258, 9712, 3544, 5608},
{8982, 373, 7362, 7925, 9280, 0, 1416, 9483, 2944, 9414, 7099, 9253, 3002, 6088, 6071, 6438, 6671, 9525, 938, 8854, 7549, 696, 1710, 6428, 4259, 6255, 634, 5646, 8444, 9392, 4613, 1831},
{3156, 8710, 2942, 367, 3764, 1416, 0, 3941, 2741, 760, 134, 1421, 8024, 8239, 4515, 5480, 2234, 5244, 2988, 2736, 4316, 7303, 9550, 9208, 9937, 1990, 4288, 3886, 1627, 8133, 7496, 8701},
{1176, 9125, 9474, 5408, 4344, 9483, 3941, 0, 6482, 2291, 209, 1564, 6115, 7033, 388, 7159, 949, 1206, 819, 7063, 8407, 7276, 8549, 2065, 692, 6609, 3787, 4200, 7321, 4083, 273, 1167},
{2851, 7310, 8696, 5804, 9310, 2944, 2741, 6482, 0, 5805, 1260, 2545, 4431, 7551, 109, 9793, 3329, 7518, 6346, 7244, 970, 9089, 4194, 4286, 9696, 4135, 6841, 8441, 9612, 1688, 2835, 981},
{6647, 5435, 702, 1419, 5045, 9414, 760, 2291, 5805, 0, 1198, 7659, 4863, 3156, 9607, 8913, 766, 9156, 104, 3774, 9823, 3869, 8037, 7464, 4425, 3770, 1525, 5335, 3428, 4548, 1464, 173},
{3224, 6190, 4025, 8230, 7951, 7099, 134, 209, 1260, 1198, 0, 4420, 5162, 8597, 9135, 3779, 781, 7727, 1873, 3465, 9720, 7812, 8289, 2987, 4365, 2162, 6521, 45, 3882, 8806, 2951, 3621},
{7585, 5, 2482, 1472, 6054, 9253, 1421, 1564, 2545, 7659, 4420, 0, 7994, 2146, 6586, 8030, 3783, 8586, 2883, 981, 2254, 1388, 7707, 2868, 7915, 4826, 3, 2297, 5955, 9653, 3941, 194},
{1188, 172, 2835, 6616, 7108, 3002, 8024, 6115, 4431, 4863, 5162, 7994, 0, 6081, 1943, 6874, 5095, 6744, 8236, 581, 659, 39, 7486, 8141, 5008, 5082, 3388, 313, 5951, 8125, 8967, 483},
{674, 8327, 2242, 5679, 9809, 6088, 8239, 7033, 7551, 3156, 8597, 2146, 6081, 0, 7233, 5627, 377, 8318, 6613, 7989, 8130, 2708, 8351, 8639, 3376, 5304, 464, 6356, 5450, 5435, 6056, 2441},
{2976, 9867, 4553, 8119, 2248, 6071, 4515, 388, 109, 9607, 9135, 6586, 1943, 7233, 0, 8937, 7994, 9845, 9423, 5764, 404, 9510, 2690, 8358, 1337, 8400, 7455, 702, 7261, 6572, 8530, 1075},
{6462, 7121, 3010, 3974, 5730, 6438, 5480, 7159, 9793, 8913, 3779, 8030, 6874, 5627, 8937, 0, 2076, 3500, 8861, 4498, 7016, 4600, 6052, 853, 7694, 9338, 6213, 9554, 6007, 7202, 150, 189},
{9859, 8150, 8983, 3555, 947, 6671, 2234, 949, 3329, 766, 781, 3783, 5095, 377, 7994, 2076, 0, 650, 3974, 2983, 4635, 4879, 8521, 9878, 324, 7166, 1590, 6161, 2388, 565, 8154, 1109},
{4383, 7334, 3542, 6723, 4696, 9525, 5244, 1206, 7518, 9156, 7727, 8586, 6744, 8318, 9845, 3500, 650, 0, 8510, 6072, 9148, 8725, 4253, 179, 7482, 1879, 4345, 2123, 2609, 7177, 9474, 5491},
{413, 5975, 9294, 8150, 1152, 938, 2988, 819, 6346, 104, 1873, 2883, 8236, 6613, 9423, 8861, 3974, 8510, 0, 2408, 9521, 1261, 3307, 2986, 4130, 6344, 8514, 7086, 9097, 2474, 812, 5845},
{8051, 6283, 2125, 3918, 1922, 8854, 2736, 7063, 7244, 3774, 3465, 981, 581, 7989, 5764, 4498, 2983, 6072, 2408, 0, 5767, 7228, 8174, 4159, 5450, 5999, 9462, 7850, 7524, 4761, 3336, 3912},
{2599, 3346, 9571, 8549, 1549, 7549, 4316, 8407, 970, 9823, 9720, 2254, 659, 8130, 404, 7016, 4635, 9148, 9521, 5767, 0, 8060, 2095, 755, 7323, 7827, 9760, 3379, 5808, 4447, 3691, 2063},
{4309, 4778, 9825, 697, 3312, 696, 7303, 7276, 9089, 3869, 7812, 1388, 39, 2708, 9510, 4600, 4879, 8725, 1261, 7228, 8060, 0, 310, 1156, 6942, 2354, 9513, 7937, 7901, 2823, 8495, 9382},
{6907, 4260, 2661, 6750, 117, 1710, 9550, 8549, 4194, 8037, 8289, 7707, 7486, 8351, 2690, 6052, 8521, 4253, 3307, 8174, 2095, 310, 0, 699, 2285, 463, 7347, 7896, 3418, 7033, 8571, 1879},
{6617, 2658, 1486, 1783, 162, 6428, 9208, 2065, 4286, 7464, 2987, 2868, 8141, 8639, 8358, 853, 9878, 179, 2986, 4159, 755, 1156, 699, 0, 1500, 5797, 3703, 9899, 8202, 5020, 2487, 1438},
{5877, 1343, 8266, 4507, 4051, 4259, 9937, 692, 9696, 4425, 4365, 7915, 5008, 3376, 1337, 7694, 324, 7482, 4130, 5450, 7323, 6942, 2285, 1500, 0, 7450, 813, 3252, 4077, 5836, 5629, 6369},
{40, 2078, 1282, 5238, 3235, 6255, 1990, 6609, 4135, 3770, 2162, 4826, 5082, 5304, 8400, 9338, 7166, 1879, 6344, 5999, 7827, 2354, 463, 5797, 7450, 0, 5938, 9266, 5470, 7824, 6255, 5539},
{9527, 5685, 1351, 6531, 4711, 634, 4288, 3787, 6841, 1525, 6521, 3, 3388, 464, 7455, 6213, 1590, 4345, 8514, 9462, 9760, 9513, 7347, 3703, 813, 5938, 0, 4890, 8193, 7989, 4389, 477},
{599, 7380, 8665, 1172, 6196, 5646, 3886, 4200, 8441, 5335, 45, 2297, 313, 6356, 702, 9554, 6161, 2123, 7086, 7850, 3379, 7937, 7896, 9899, 3252, 9266, 4890, 0, 6852, 6175, 3352, 2781},
{5186, 4178, 4985, 3210, 7258, 8444, 1627, 7321, 9612, 3428, 3882, 5955, 5951, 5450, 7261, 6007, 2388, 2609, 9097, 7524, 5808, 7901, 3418, 8202, 4077, 5470, 8193, 6852, 0, 3231, 7790, 2594},
{2204, 4378, 8601, 5349, 9712, 9392, 8133, 4083, 1688, 4548, 8806, 9653, 8125, 5435, 6572, 7202, 565, 7177, 2474, 4761, 4447, 2823, 7033, 5020, 5836, 7824, 7989, 6175, 3231, 0, 7831, 6332},
{958, 9261, 2280, 3911, 3544, 4613, 7496, 273, 2835, 1464, 2951, 3941, 8967, 6056, 8530, 150, 8154, 9474, 812, 3336, 3691, 8495, 8571, 2487, 5629, 6255, 4389, 3352, 7790, 7831, 0, 3777},
{6352, 2925, 9848, 4668, 5608, 1831, 8701, 1167, 981, 173, 3621, 194, 483, 2441, 1075, 189, 1109, 5491, 5845, 3912, 2063, 9382, 1879, 1438, 6369, 5539, 477, 2781, 2594, 6332, 3777, 0}
};
TSPVC tsp = new TSPVC(distances);
List<Integer> path = tsp.findBestRoute();
// Poner nombre a los nodos siguiendo la secuencia del abecedario
List<String> nodeNames = new ArrayList<>();
for (int i = 0; i < distances.length; i++) {
char letter = (char) ('A' + i);
nodeNames.add(String.valueOf(letter));
}
// Imprimir ruta y distancia recorrida
System.out.println("> Mejor ruta encontrada:");
double totalDistance = 0;
for (int i = 0; i < path.size() - 1; i++) {
int node1 = path.get(i);
int node2 = path.get(i + 1);
double distance = distances[node1][node2];
totalDistance += distance;
System.out.printf("%s ", nodeNames.get(node1), distance);
}
// Imprimir el nodo final y la vuelta al nodo inicial
System.out.println(nodeNames.get(path.get(path.size() - 1)));
System.out.printf("> La distancia total recorrida es: %.0f\n", totalDistance);
}
}
Código 2 (TSPVC.java):
package tsp_vecinocercano;
import java.util.ArrayList;
import java.util.List;
public class TSPVC {
private final double[][] distances;
public TSPVC(double[][] distances) {
this.distances = distances;
}
public List<Integer> findBestRoute() {
List<Integer> bestPath = null;
double shortestDistance = Double.MAX_VALUE;
// Probar con cada nodo como punto de inicio
for (int startNode = 0; startNode < distances.length; startNode++) {
List<Integer> path = findPathStartingFrom(startNode);
double totalDistance = calculateTotalDistance(path);
if (totalDistance < shortestDistance) {
shortestDistance = totalDistance;
bestPath = path;
}
}
return bestPath;
}
private List<Integer> findPathStartingFrom(int startNode) {
List<Integer> path = new ArrayList<>();
path.add(startNode);
int currentNode = startNode;
for (int i = 0; i < distances.length - 1; i++) {
double minDistance = Double.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(startNode);
return path;
}
private double calculateTotalDistance(List<Integer> path) {
double 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];
}
return totalDistance;
}
}
Resultado:
run:
> Ruta:
_ P ` J S A Z W E X R Q Y H K \ M V F B L [ N C T G D ] ^ I O U _
> La distancia total recorrida es: 25606
BUILD SUCCESSFUL (total time: 0 seconds)
