Este código Java genera puntos aleatorios en la línea de la circunferencia de un círculo y crea una matriz de distancias entre ellos. Esta matriz de distancias generada, que representa un grafo completo con propiedades geométricas especiales, es el núcleo del programa. Es ideal para probar diversos algoritmos, especialmente variantes del Problema del Viajante de Comercio (TSP).
La disposición circular de los puntos ofrece una característica importante: la ruta óptima del TSP es conocida (seguir la circunferencia), y el algoritmo del del TSP Vecino Más Cercano la encuentra eficientemente. Esto proporciona un valioso punto de referencia para evaluar y comparar el rendimiento de diferentes algoritmos de optimización sobre la misma matriz de distancias.
Código Java (CircunferenciaDistancias.java):
package circunferenciadistancias;
import java.util.Random;
public class CircunferenciaDistancias {
public static int N = 16;
public static int diametro = 1024;
public static void main(String[] args) {
double radio = diametro / 2.0;
double[][] puntos = new double[N][2];
double[][] distancias = new double[N][N];
Random random = new Random();
// Generar N puntos aleatorios en la circunferencia
for (int i = 0; i < N; i++) {
double angulo = random.nextDouble() * 2 * Math.PI;
double x = radio + radio * Math.cos(angulo);
double y = radio + radio * Math.sin(angulo);
puntos[i][0] = x;
puntos[i][1] = y;
}
// Calcular la matriz de distancias entre los puntos y mostrarlas en pantalla
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j) {
distancias[i][j] = Math.sqrt(
Math.pow(puntos[i][0] - puntos[j][0], 2)
+ Math.pow(puntos[i][1] - puntos[j][1], 2)
);
} else {
distancias[i][j] = 0;
}
System.out.printf("%6d", Math.round(distancias[i][j]));
}
System.out.println();
}
}
}
Resultado:
run:
0 264 299 950 996 894 199 901 673 1023 895 941 258 701 1024 812
264 0 541 820 901 993 67 996 452 998 993 805 505 485 981 946
299 541 0 1020 1022 710 483 720 869 968 711 1018 42 888 988 595
950 820 1020 0 149 796 858 787 465 414 795 26 1016 432 352 881
996 901 1022 149 0 693 930 684 593 274 693 174 1024 562 209 796
894 993 710 796 693 0 974 13 1002 467 1 811 740 993 525 149
199 67 483 858 930 974 0 978 511 1011 975 844 446 543 998 918
901 996 720 787 684 13 978 0 999 455 12 803 749 990 514 162
673 452 869 465 593 1002 511 999 0 795 1001 442 846 37 751 1022
1023 998 968 414 274 467 1011 455 795 0 466 437 981 770 67 595
895 993 711 795 693 1 975 12 1001 466 0 811 741 993 524 150
941 805 1018 26 174 811 844 803 442 437 811 0 1012 409 376 894
258 505 42 1016 1024 740 446 749 846 981 741 1012 0 867 998 629
701 485 888 432 562 993 543 990 37 770 993 409 867 0 725 1019
1024 981 988 352 209 525 998 514 751 67 524 376 998 725 0 648
812 946 595 881 796 149 918 162 1022 595 150 894 629 1019 648 0
BUILD SUCCESSFUL (total time: 0 seconds)
martes, 13 de agosto de 2024
Matriz de conectividad circular.
Problema del Viajante de Comercio TSP (V.3.1). Análisis estadístico de eficiencia de N-Opt.
Este programa Java implementa una solución multihilo para el Problema del Viajante de Comercio (TSP) utilizando el algoritmo N-opt, con un enfoque especial en el análisis estadístico de eficiencia. El código está diseñado para evaluar sistemáticamente diferentes combinaciones de parámetros del algoritmo N-opt, permitiendo un estudio exhaustivo de su rendimiento bajo diversas condiciones.
Características principales:
1. Análisis estadístico de eficiencia: El programa realiza un análisis exhaustivo combinando varios parámetros clave del algoritmo N-opt:
- Utiliza diferentes valores de N (2, 3, 4, 5) para el N-opt.
- Varía el número de iteraciones (50, 100, 200, 400, 800, 1600, 3200, 6400, 12800).
- Ejecuta cada combinación de parámetros múltiples veces (64 ejecuciones) para obtener resultados estadísticamente significativos.
Nota: Estas arrays permiten un análisis sistemático y exhaustivo del rendimiento del algoritmo N-opt bajo diferentes configuraciones. Al combinar cada valor de N con cada número de iteraciones, el programa puede evaluar un total de 36 configuraciones diferentes (4 valores de N × 9 valores de iteraciones), proporcionando una visión completa del comportamiento del algoritmo en diversas condiciones.
2. Uso de ExecutorService: Emplea un pool de hilos fijo (8 hilos) para ejecutar tareas en paralelo, maximizando la utilización de los recursos de la CPU.
3. Paralelización de experimentos: Cada combinación de N y número de iteraciones se ejecuta como una tarea independiente, permitiendo la evaluación simultánea de múltiples configuraciones.
4. Recopilación y agregación de resultados: Los resultados de cada tarea se agregan de forma segura, calculando promedios de tiempo de ejecución y calidad de la solución (distancia) para cada configuración.
5. Análisis comparativo: Al final, se presentan los 100 mejores resultados, ordenados por distancia media y tiempo de ejecución, facilitando la comparación entre diferentes configuraciones del algoritmo.
Este enfoque multihilo no solo acelera la ejecución del gran número de experimentos necesarios para el análisis estadístico, sino que también permite una evaluación más completa del rendimiento del algoritmo N-opt bajo diferentes parámetros. Esto es crucial para determinar las configuraciones óptimas del algoritmo para diferentes tamaños de problema y restricciones de tiempo de ejecución.
El uso de arrays predefinidos para N y el número de iteraciones (Ns y iterationsArray) permite una fácil modificación y expansión del espacio de parámetros a evaluar, facilitando futuros análisis más detallados o enfocados en rangos específicos de estos parámetros.
Código Java (TSP_Optimization.java):
package tsp_optimization;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
public class TSP_Optimization {
private static final List<Result> aggregatedResults = new ArrayList<>();
public static void main(String[] args) throws Exception {
// Matriz de distancias de 32x32
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}
};
/* Define los diferentes valores de Ns para el algoritmo N-opt.
N representa el número de ciudades que se intentarán optimizar simultáneamente en cada iteración.
Se evalúan 2-opt, 3-opt, 4-opt y 5-opt, permitiendo comparar la eficacia de diferentes grados de optimización local.
*/
int[] Ns = {2, 3, 4, 5};
/* Especifica el número de iteraciones que se ejecutarán para cada configuración de N.
Utiliza una secuencia que se duplica en cada paso, abarcando un amplio rango desde 50 hasta 12800 iteraciones.
Permite evaluar cómo el aumento del número de iteraciones afecta la calidad de la solución y el tiempo de ejecución.
*/
int[] iterationsArray = {50, 100, 200, 400, 800, 1600, 3200, 6400, 12800};
// Crear un pool de hilos con un número fijo de hilos (8 hilos)
ExecutorService executor = Executors.newFixedThreadPool(8);
for (int i = 0; i < 64; i++) {
System.out.println("Ejecución número " + (i + 1));
List<Future<Result>> futures = new ArrayList<>();
for (int N : Ns) {
for (int iterations : iterationsArray) {
// Crear una tarea para cada experimento y enviarla al executor
futures.add(executor.submit(new ExperimentTask(distances, N, iterations)));
}
}
// Esperar a que todas las tareas terminen y recoger los resultados
List<Result> executionResults = new ArrayList<>();
for (Future<Result> future : futures) {
executionResults.add(future.get());
}
aggregateResults(executionResults);
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.HOURS);
printFinalTop100Results();
}
private static class ExperimentTask implements Callable<Result> {
private final double[][] distances;
private final int N;
private final int iterations;
ExperimentTask(double[][] distances, int N, int iterations) {
this.distances = distances;
this.N = N;
this.iterations = iterations;
}
@Override
public Result call() {
long startTime = System.nanoTime();
TSPNOpt tspN = new TSPNOpt(distances, N);
List<Integer> bestRoute = tspN.findBestRoute(iterations);
double bestDistance = tspN.calculateTotalDistance(bestRoute);
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1_000_000;
return new Result(distances.length, N, iterations, duration, bestDistance, bestRoute);
}
}
private static void aggregateResults(List<Result> executionResults) {
executionResults.forEach(result -> {
Optional<Result> existingResult = aggregatedResults.stream()
.filter(r -> r.nOpt == result.nOpt && r.iterations == result.iterations)
.findFirst();
if (existingResult.isPresent()) {
Result aggResult = existingResult.get();
aggResult.addExecution(result);
} else {
aggregatedResults.add(new Result(result));
}
});
}
private static void printFinalTop100Results() {
// Ordenar por la distancia media y luego por tiempo medio
aggregatedResults.sort(Comparator
.comparingDouble((Result r) -> r.averageBestDistance())
.thenComparingDouble(Result::averageDuration));
System.out.println("| Nodos | N-opt | Iteraciones | Tiempo medio (ms) | Distancia media | Mejor ruta promedio ·>>");
System.out.println("|-------|-------|-------------|-------------------|-----------------|---------------------···");
// Limitar a top 100
aggregatedResults.stream().limit(100).forEach(result -> {
System.out.printf("| %5d | %5d | %11d | %17.2f | %15.2f | %s |%n",
result.numCities, result.nOpt, result.iterations,
result.averageDuration(), result.averageBestDistance(),
routeToString(result.bestRoute));
});
}
private static String routeToString(List<Integer> route) {
return route.stream()
.map(i -> String.valueOf((char) ('A' + i)))
.collect(Collectors.joining(""));
}
private static class Result {
int numCities, nOpt, iterations;
long totalDuration;
double totalBestDistance;
List<Integer> bestRoute;
int count;
Result(int numCities, int nOpt, int iterations, long duration, double bestDistance, List<Integer> bestRoute) {
this.numCities = numCities;
this.nOpt = nOpt;
this.iterations = iterations;
this.totalDuration = duration;
this.totalBestDistance = bestDistance;
this.bestRoute = new ArrayList<>(bestRoute);
this.count = 1;
}
// Constructor para crear un nuevo Result a partir de otro
Result(Result other) {
this.numCities = other.numCities;
this.nOpt = other.nOpt;
this.iterations = other.iterations;
this.totalDuration = other.totalDuration;
this.totalBestDistance = other.totalBestDistance;
this.bestRoute = new ArrayList<>(other.bestRoute);
this.count = other.count;
}
void addExecution(Result other) {
this.totalDuration += other.totalDuration;
this.totalBestDistance += other.totalBestDistance;
this.count++;
}
double averageDuration() {
return (double) this.totalDuration / this.count;
}
double averageBestDistance() {
return this.totalBestDistance / this.count;
}
}
}
Código Java (TSPNOpt.java):
package tsp_optimization;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TSPNOpt {
private final double[][] distances;
private final int numCities;
private final int N;
public TSPNOpt(double[][] distances, int N) {
this.distances = distances;
this.numCities = distances.length;
this.N = N;
}
public List<Integer> findBestRoute(int numRuns) {
List<Integer> bestRoute = null;
double bestDistance = Double.MAX_VALUE;
for (int run = 0; run < numRuns; run++) {
List<Integer> route = generateRandomRoute();
route = optimizeRoute(route);
double distance = calculateTotalDistance(route);
if (distance < bestDistance) {
bestDistance = distance;
bestRoute = new ArrayList<>(route);
}
}
return bestRoute;
}
private List<Integer> generateRandomRoute() {
List<Integer> route = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
route.add(i);
}
Collections.shuffle(route);
return route;
}
private List<Integer> optimizeRoute(List<Integer> route) {
boolean improved = true;
while (improved) {
improved = false;
for (int i = 0; i < numCities - N + 1; i++) {
for (int j = i + 1; j < numCities - N + 2; j++) {
List<Integer> newRoute = nOptSwap(route, i, j);
if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
route = newRoute;
improved = true;
}
}
}
}
return route;
}
private List<Integer> nOptSwap(List<Integer> route, int i, int j) {
List<Integer> newRoute = new ArrayList<>(route.subList(0, i));
List<Integer> subRoute = new ArrayList<>(route.subList(i, j + 1));
Collections.reverse(subRoute);
newRoute.addAll(subRoute);
newRoute.addAll(route.subList(j + 1, route.size()));
return newRoute;
}
public double calculateTotalDistance(List<Integer> route) {
double totalDistance = 0;
for (int i = 0; i < route.size(); i++) {
totalDistance += distances[route.get(i)][route.get((i + 1) % route.size())];
}
return totalDistance;
}
}
Resultado:
run:
Ejecución número 1
Ejecución número 2
...
...
...
Ejecución número 63
Ejecución número 64
| Nodos | N-opt | Iteraciones | Tiempo medio (ms) | Distancia media | Mejor ruta promedio ·>>
|-------|-------|-------------|-------------------|-----------------|---------------------···
| 32 | 3 | 12800 | 21358,67 | 18835,03 | CJSFBL`P_HK\OUI^QY[NAZWEXR]GDVMT
| 32 | 2 | 12800 | 22551,59 | 18852,16 | \KHY[NQ^IOUMTCJS_P`LBFVDG]RXEWZA
| 32 | 2 | 6400 | 12418,63 | 18907,08 | AN[LBFVD\KG]RXEWZCTMUOI^QYH_P`JS
| 32 | 3 | 6400 | 11719,80 | 18932,08 | ^QN[YH_P`LBFVD\KG]RXEWZASJCTMUOI
| 32 | 3 | 3200 | 5967,63 | 19003,86 | SJCZWETM\KH_P`LBFVDG]RXUOI^QY[NA
| 32 | 2 | 3200 | 6311,00 | 19011,36 | TLBFSJCZA\KGDVWEXR]^QN[YH_P`IOUM
| 32 | 2 | 1600 | 3226,63 | 19076,80 | LBFVDG]RXEWZCJS_P`[NA\KHYQ^IOUMT
| 32 | 3 | 1600 | 3019,42 | 19108,42 | QY[NAZWEXR]GDVMTCJSFBL`P_HK\OUI^
| 32 | 4 | 12800 | 18555,02 | 19287,33 | L`P_HK\OUI^QY[NASJCZWEXR]GDVFBMT
| 32 | 2 | 800 | 1643,80 | 19331,39 | G]RQ^IOUXEWZAN[YHK\MTCJS_P`LBFVD
| 32 | 4 | 6400 | 10526,55 | 19362,56 | WVDG]RXUOI^QY[NAZCJSFBL`P_HK\MTE
| 32 | 3 | 800 | 1512,89 | 19406,67 | VM\KH_P`JCZWETLBFSAN[YQ^IOUXR]GD
| 32 | 3 | 400 | 772,70 | 19550,09 | MTCZWEXR]GK\DVFBL[NASJ`P_HYQ^IOU
| 32 | 2 | 400 | 867,86 | 19578,63 | \MTEWZCJSAN[YQ^IOUXR]GDVFBL`P_HK
| 32 | 4 | 3200 | 5431,09 | 19668,63 | OUMTCZWEXR]GDVFBL[YQNA\KH_P`JS^I
| 32 | 3 | 200 | 387,34 | 19926,53 | IOH_P`LBFSJCTMUEXR]GK\DVWZAN[YQ^
| 32 | 2 | 200 | 447,53 | 19938,53 | OI^QY[NAZCTLBFSJ`P_HK\DG]RXEWVMU
| 32 | 4 | 1600 | 2729,55 | 19944,30 | CZAN[LBFVDG]RXUOI^QYWESJ`P_HK\MT
| 32 | 5 | 12800 | 15715,53 | 20226,56 | FSJ`P_HK\OUI^QYWEXR]GDVMTCZAN[LB
| 32 | 2 | 100 | 228,02 | 20314,23 | ]RXEWZCJ`P_STMUOI^QYHK\AN[LBFVDG
| 32 | 3 | 100 | 203,81 | 20318,09 | _P`L[NA\KHYQ^IOUXR]GDVFBMTEWZCJS
| 32 | 4 | 800 | 1365,69 | 20390,78 | BLTCZWEUOI^QYXR]GDVM\KH_P`JSAN[F
| 32 | 2 | 50 | 113,28 | 20553,84 | AN[YQ^IUO\KH_P`LDVFBMTCZWEXR]GJS
| 32 | 3 | 50 | 104,23 | 20606,63 | GDVWZAN[LBFS_P`JCTM\KHYQ^IOUEXR]
| 32 | 5 | 6400 | 8862,86 | 20664,75 | XEWZCJSAN[YQ^IUOH_P`LTM\KGDVFB]R
| 32 | 4 | 400 | 684,28 | 20685,34 | OI`P_HK\AN[YBLTCZWEXRQ^]GDJSFVMU
| 32 | 5 | 3200 | 4832,70 | 20953,80 | UI^QN[YH_P`JSA\KGD]RXEWZCTLBFVMO
| 32 | 4 | 200 | 341,08 | 21262,47 | ZWEUOI^QN[YH_P`LBFVMTCXR]GK\DJSA
| 32 | 5 | 1600 | 2470,16 | 21434,16 | JCZA_P`HYWETMVD\KG]RXUOI^QN[LBFS
| 32 | 4 | 100 | 171,50 | 21762,75 | G]RXEWVFBMTL`P_SJCZA\KHOUI^QN[YD
| 32 | 5 | 800 | 1232,75 | 21828,98 | SFBLTMVDG]RXEWZANQ^IUO\KHY[`P_CJ
| 32 | 4 | 50 | 85,17 | 22325,89 | WZK\OUI`P_SJCTMAN[LBFVDG]^QYHRXE
| 32 | 5 | 400 | 616,48 | 22443,19 | P_SJCTMBF[NAZR]GDVWEXUOI^QYHK\L`
| 32 | 5 | 200 | 306,70 | 23201,78 | LBFS_HYQ^IOUXR]GK\MVDJCP`[NAZWET
| 32 | 5 | 100 | 152,92 | 24017,14 | BFVM\AN[YHKIOUXRQ^]GDJ`P_SEWZCTL
| 32 | 5 | 50 | 75,78 | 24890,53 | WZASJCTM\KIOUXRH_P`L[NQ^]GDVFBYE
BUILD SUCCESSFUL (total time: 30 minutes 1 second)
lunes, 12 de agosto de 2024
Problema del viajante de Comercio TSP (IV.2). Método Vecino Cercano mejorado.
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)