Este código en Java implementa un juego de texto interactivo llamado "La Mansión Misteriosa".
Características:
. El juego utiliza un sistema de escenas conectadas.
. Cada escena tiene una descripción, opciones para el jugador y enlaces a las siguientes escenas.
. El jugador navega por la mansión tomando decisiones en cada escena.
. Las escenas están precargadas en un mapa (java.util.Map).
. El juego comienza con un prólogo y termina cuando el jugador llega a una escena final o de "horror".
Código Java (LaMansionMisteriosa.java):
package lamansionmisteriosa;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class LaMansionMisteriosa {
private static final Scanner scanner = new Scanner(System.in);
private static final Map<String, Escena> escenas = new HashMap<>();
public static void main(String[] args) {
mostrarPrologo();
EscenaLoader.cargarEscenas(escenas);
jugar("start");
}
private static void jugar(String escenaActual) {
while (true) {
Escena escena = escenas.get(escenaActual);
if (escena == null) {
System.out.println("Error: Escena no encontrada. Fin del juego.");
break;
}
System.out.println(escena.getDescripcion());
if (escena.getOpciones().length == 0) {
escenaActual = "horror_final"; // Redirigir a la escena final
escena = escenas.get(escenaActual);
System.out.println(escena.getDescripcion());
System.out.println("FIN DEL JUEGO");
break;
}
for (int i = 0; i < escena.getOpciones().length; i++) {
System.out.println((i + 1) + ". " + escena.getOpciones()[i]);
}
int eleccion;
while (true) {
try {
eleccion = Integer.parseInt(scanner.nextLine()) - 1;
if (eleccion >= 0 && eleccion < escena.getSiguienteEscena().length) {
break;
} else {
System.out.println("Opción no válida. Por favor, elige un número entre 1 y " + escena.getOpciones().length);
}
} catch (NumberFormatException e) {
System.out.println("Por favor, ingresa un número válido.");
}
}
escenaActual = escena.getSiguienteEscena()[eleccion];
}
}
private static void mostrarPrologo() {
System.out.println("La Mansión Misteriosa\n");
System.out.println("Hace muchos años, en una región olvidada por el tiempo, se erige una mansión rodeada de misterio. "
+ "Nadie sabe realmente qué ocurrió allí, pero los rumores hablan de desapariciones, fantasmas y un mal "
+ "inimaginable que acecha en sus pasillos. Ahora, te encuentras frente a esta mansión, dispuesto a descubrir "
+ "la verdad. Pero ten cuidado, ya que esta aventura puede ser tu última...");
System.out.println("\nPresiona Enter para continuar...");
scanner.nextLine(); // Espera a que el jugador presione Enter para continuar
}
}
Código Java (Escena.java):
package lamansionmisteriosa;
class Escena {
private final String descripcion;
private final String[] opciones;
private final String[] siguienteEscena;
public Escena(String descripcion, String[] opciones, String[] siguienteEscena) {
this.descripcion = descripcion;
this.opciones = opciones;
this.siguienteEscena = siguienteEscena;
}
public String getDescripcion() {
return descripcion;
}
public String[] getOpciones() {
return opciones;
}
public String[] getSiguienteEscena() {
return siguienteEscena;
}
}
Código Java (EscenaLoader.java):
package lamansionmisteriosa;
import java.util.Map;
class EscenaLoader {
public static void cargarEscenas(Map<String, Escena> escenas) {
escenas.put("start", new Escena(
"La lluvia golpea con fuerza los ventanales de la vieja mansión. Has oído rumores sobre este lugar, historias de personas que entraron y nunca salieron. Pero tú no crees en fantasmas... ¿verdad?",
new String[]{"Avanzar hacia la puerta principal", "Explorar los alrededores de la mansión"},
new String[]{"puerta_principal", "explorar_alrededores"}
));
escenas.put("puerta_principal", new Escena(
"La puerta de madera cruje mientras la empujas. El vestíbulo está oscuro, con solo la luz de tu linterna iluminando el polvo en el aire. Frente a ti, una escalera se eleva hacia la oscuridad del segundo piso, y un pasillo a la derecha parece perderse en las sombras.",
new String[]{"Subir por las escaleras", "Tomar el pasillo a la derecha"},
new String[]{"escaleras", "pasillo_derecho"}
));
escenas.put("explorar_alrededores", new Escena(
"Decides dar una vuelta alrededor de la mansión antes de entrar. La vegetación está densa y descuidada, y el aire se siente pesado. Llegas a una ventana rota que da a lo que parece ser una cocina.",
new String[]{"Entrar por la ventana rota", "Regresar a la puerta principal"},
new String[]{"cocina", "puerta_principal"}
));
escenas.put("cocina", new Escena(
"La cocina está en ruinas, con platos rotos y utensilios oxidados esparcidos por todos lados. El olor a humedad es casi insoportable. Un ruido sordo proviene de la despensa.",
new String[]{"Abrir la despensa", "Salir de la cocina rápidamente"},
new String[]{"despensa", "volver_vestibulo"}
));
escenas.put("despensa", new Escena(
"Abres la puerta de la despensa, pero está vacía. El ruido cesa de inmediato. Cuando miras hacia atrás, la puerta de la cocina está cerrada y una figura oscura aparece en el umbral...",
new String[]{},
new String[]{"horror_final"}
));
escenas.put("escaleras", new Escena(
"Los escalones crujen bajo tu peso, y cada paso que das resuena como un susurro en la oscuridad. Al llegar al segundo piso, ves tres puertas: una a la izquierda, una a la derecha y una al final del pasillo.",
new String[]{"Abrir la puerta de la izquierda", "Abrir la puerta de la derecha", "Ir hacia la puerta al final del pasillo"},
new String[]{"puerta_izquierda", "puerta_derecha", "puerta_final"}
));
escenas.put("puerta_izquierda", new Escena(
"La puerta se abre con un chirrido. El cuarto está lleno de polvo, con un gran espejo cubierto por una sábana vieja. Mientras te acercas al espejo, algo en él parece moverse...",
new String[]{"Quitar la sábana del espejo", "Salir de la habitación rápidamente"},
new String[]{"espejo", "salir_habitacion"}
));
escenas.put("espejo", new Escena(
"Retiras la sábana, revelando el espejo. Al principio, solo ves tu propio reflejo, pero de repente... una figura oscura aparece detrás de ti en el reflejo. Te das la vuelta, pero no hay nadie ahí. Cuando miras de nuevo al espejo, está roto.",
new String[]{},
new String[]{"horror_final"}
));
escenas.put("puerta_derecha", new Escena(
"Esta puerta conduce a una pequeña biblioteca. Los libros parecen intactos, pero el polvo indica que no han sido tocados en años. De repente, sientes una presencia detrás de ti...",
new String[]{"Ignorar la sensación y examinar los libros", "Voltear rápidamente"},
new String[]{"examinar_libros", "voltear"}
));
escenas.put("examinar_libros", new Escena(
"Pasas tus dedos por los lomos de los libros, pero cuando intentas sacar uno, se atora. Con un poco de esfuerzo, logras sacarlo, y al hacerlo, una sección de la estantería se abre, revelando un pasaje secreto.",
new String[]{"Entrar al pasaje secreto", "No entrar, regresar al vestíbulo"},
new String[]{"pasaje_secreto", "volver_vestibulo"}
));
escenas.put("pasaje_secreto", new Escena(
"Entras en el pasaje secreto, y la puerta de la biblioteca se cierra detrás de ti. El pasaje está oscuro y estrecho, con paredes de piedra fría. Sientes que algo te está observando desde la oscuridad.",
new String[]{"Seguir adelante", "Regresar a la biblioteca"},
new String[]{"seguir_pasaje", "volver_vestibulo"}
));
escenas.put("seguir_pasaje", new Escena(
"El pasaje te lleva a una habitación oculta. En el centro de la habitación hay un libro antiguo sobre un pedestal, cubierto de polvo y telarañas. Cuando te acercas, el libro se abre solo...",
new String[]{},
new String[]{"horror_final"}
));
escenas.put("pasillo_derecho", new Escena(
"El pasillo a la derecha es largo y oscuro, y cada paso que das parece más pesado que el anterior. A medida que avanzas, sientes como si las paredes se cerraran sobre ti. Finalmente, llegas a una puerta pequeña al final del pasillo.",
new String[]{"Abrir la puerta", "Regresar al vestíbulo"},
new String[]{"puerta_final", "volver_vestibulo"}
));
escenas.put("puerta_final", new Escena(
"La puerta al final del pasillo se abre con un rechinido metálico. Dentro, una vieja cuna se mece sola en medio de la habitación.",
new String[]{},
new String[]{"horror_final"}
));
escenas.put("salir_habitacion", new Escena(
"Decides que es mejor no enfrentar lo que sea que esté en esa habitación y te apresuras a salir. El aire en el pasillo es más frío de lo que recuerdas...",
new String[]{},
new String[]{"volver_vestibulo"}
));
escenas.put("volver_vestibulo", new Escena(
"Regresas al vestíbulo, pero algo ha cambiado. La puerta principal, por donde entraste, ahora está cerrada. No hay manera de abrirla...",
new String[]{},
new String[]{"horror_final"}
));
escenas.put("voltear", new Escena(
"Te das la vuelta rápidamente, pero no hay nadie detrás de ti. Sin embargo, sientes como si algo estuviera observándote desde las sombras. Decides que es mejor no arriesgarte y salir de la biblioteca.",
new String[]{},
new String[]{"volver_vestibulo"}
));
escenas.put("horror_final", new Escena(
"La mansión comienza a vibrar suavemente, y los susurros que escuchas se hacen más fuertes. Sabes que debes salir, pero cada salida parece estar bloqueada. Te das cuenta de que la mansión nunca tuvo intención de dejarte ir...\n"
+ "La oscuridad te envuelve por completo y sientes como algo frío y pegajoso te atrapa. Antes de que puedas gritar, todo se vuelve negro...",
new String[]{},
new String[]{}
));
}
}
Resultado:
run:
La Mansión Misteriosa
Hace muchos años, en una región olvidada por el tiempo, se erige una mansión rodeada de misterio. Nadie sabe realmente qué ocurrió allí, pero los rumores hablan de desapariciones, fantasmas y un mal inimaginable que acecha en sus pasillos. Ahora, te encuentras frente a esta mansión, dispuesto a descubrir la verdad. Pero ten cuidado, ya que esta aventura puede ser tu última...
Presiona Enter para continuar...
La lluvia golpea con fuerza los ventanales de la vieja mansión. Has oído rumores sobre este lugar, historias de personas que entraron y nunca salieron. Pero tú no crees en fantasmas... ¿verdad?
1. Avanzar hacia la puerta principal
2. Explorar los alrededores de la mansión
2
Decides dar una vuelta alrededor de la mansión antes de entrar. La vegetación está densa y descuidada, y el aire se siente pesado. Llegas a una ventana rota que da a lo que parece ser una cocina.
1. Entrar por la ventana rota
2. Regresar a la puerta principal
1
La cocina está en ruinas, con platos rotos y utensilios oxidados esparcidos por todos lados. El olor a humedad es casi insoportable. Un ruido sordo proviene de la despensa.
1. Abrir la despensa
2. Salir de la cocina rápidamente
1
Abres la puerta de la despensa, pero está vacía. El ruido cesa de inmediato. Cuando miras hacia atrás, la puerta de la cocina está cerrada y una figura oscura aparece en el umbral...
La mansión comienza a vibrar suavemente, y los susurros que escuchas se hacen más fuertes. Sabes que debes salir, pero cada salida parece estar bloqueada. Te das cuenta de que la mansión nunca tuvo intención de dejarte ir...
La oscuridad te envuelve por completo y sientes como algo frío y pegajoso te atrapa. Antes de que puedas gritar, todo se vuelve negro...
FIN DEL JUEGO
BUILD SUCCESSFUL (total time: 2 minutes 4 seconds)
martes, 27 de agosto de 2024
viernes, 16 de agosto de 2024
Problema del viajante de Comercio TSP (XV). Método Dinámica de Enjambre de Partículas (PSO).
El Algoritmo de Dinámica de Enjambre de Partículas (PSO) aplicado al Problema del Viajante de Comercio (TSP) busca encontrar la ruta más corta posible que visita una serie de ciudades y regresa al punto de partida. Cada partícula en PSO representa una posible ruta a través de todas las ciudades. Estas partículas se mueven dentro del espacio de soluciones ajustando sus rutas basadas en la mejor solución personal que han encontrado y la mejor solución global conocida.
Características:
. Representación de las Soluciones: Cada partícula es una permutación de las ciudades, representando una posible ruta en el TSP.
. Movimiento de las Partículas: Las partículas ajustan su ruta actual usando:
. Inercia (w): Mantienen parte de su ruta anterior.
. Cognitivo (c1): Se acercan a la mejor ruta que han encontrado.
. Social (c2): Se acercan a la mejor ruta conocida por todo el enjambre.
. Exploración y Explotación:
Inercia (w): Un valor moderado, como 0.7, ayuda a balancear entre explorar nuevas rutas y explotar rutas conocidas.
Cognitivo y Social (c1 y c2): Valores iguales, como 1.5, equilibran la influencia de la experiencia personal y la influencia del grupo.
. Actualización de las Rutas: Durante las iteraciones, las partículas intercambian segmentos de rutas para acercarse a las mejores soluciones, evitando quedarse atrapadas en soluciones subóptimas.
. Criterio de Parada: El algoritmo ejecuta un número fijo de iteraciones (por ejemplo, 10000) para asegurar que se explore adecuadamente el espacio de soluciones.
Ventajas:
. Flexibilidad: PSO puede adaptarse fácilmente a problemas con diferentes tamaños de ciudades.
. Capacidad de Escapar de Mínimos Locales: La influencia combinada de la inercia, la mejor solución personal y la global permite que las partículas exploren diferentes áreas del espacio de soluciones.
. Convergencia: PSO tiende a converger hacia una buena solución rápidamente, aunque no garantiza encontrar la solución óptima.
Código Java (TSP_DinamicaEnjambreParticulas.java):
package tsp_dinamicaenjambreparticulas;
import java.util.ArrayList;
public class TSP_DinamicaEnjambreParticulas {
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}
};
int numParticles = 100; // Número partículas
double w = 0.5; // Inercia reducida
double c1 = 2.0; // Coeficiente cognitivo (mayor peso en la mejor solución personal)
double c2 = 2.0; // Coeficiente social (mayor peso en la mejor solución global)
TSPPSO tsp = new TSPPSO(distanceMatrix, numParticles, w, c1, c2);
ArrayList<Integer> bestRoute = tsp.solve(10000); // 10000 iteraciones
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
System.out.println("Distancia mínima aproximada: " + bestDistance);
}
}
Código Java (TSPPSO.java):
package tsp_dinamicaenjambreparticulas;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class TSPPSO {
private final double[][] distanceMatrix;
private final int numCities;
private int numParticles = 50; // Número partículas
private double w = 0.7; // Inercia
private double c1 = 1.5; // Coeficiente cognitivo
private double c2 = 1.5; // Coeficiente social
private final Random random = new Random();
public TSPPSO(double[][] distanceMatrix, int numParticles, double w, double c1, double c2) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
this.numParticles = numParticles;
this.w = w;
this.c1 = c1;
this.c2 = c2;
}
public TSPPSO(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
public ArrayList<Integer> solve(int maxIterations) {
ArrayList<ArrayList<Integer>> particles = new ArrayList<>();
ArrayList<ArrayList<Integer>> personalBestPositions = new ArrayList<>();
ArrayList<Double> personalBestDistances = new ArrayList<>();
ArrayList<Integer> globalBestPosition = null;
double globalBestDistance = Double.MAX_VALUE;
// Inicializar las partículas
for (int i = 0; i < numParticles; i++) {
ArrayList<Integer> route = generateRandomRoute();
particles.add(route);
personalBestPositions.add(new ArrayList<>(route));
double routeDistance = calculateTotalDistance(route);
personalBestDistances.add(routeDistance);
// Actualizar mejor global
if (routeDistance < globalBestDistance) {
globalBestPosition = route;
globalBestDistance = routeDistance;
}
}
// Iterar hasta alcanzar el criterio de parada
for (int iter = 0; iter < maxIterations; iter++) {
for (int i = 0; i < numParticles; i++) {
ArrayList<Integer> currentPosition = particles.get(i);
ArrayList<Integer> newPosition = updatePosition(currentPosition, personalBestPositions.get(i), globalBestPosition);
double newDistance = calculateTotalDistance(newPosition);
double personalBestDistance = personalBestDistances.get(i);
// Actualizar la mejor posición personal
if (newDistance < personalBestDistance) {
personalBestPositions.set(i, newPosition);
personalBestDistances.set(i, newDistance);
}
// Actualizar la mejor posición global
if (newDistance < globalBestDistance) {
globalBestPosition = newPosition;
globalBestDistance = newDistance;
}
particles.set(i, newPosition);
}
}
return globalBestPosition;
}
private ArrayList<Integer> generateRandomRoute() {
ArrayList<Integer> route = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
route.add(i);
}
Collections.shuffle(route);
return route;
}
private ArrayList<Integer> updatePosition(ArrayList<Integer> currentPosition, ArrayList<Integer> personalBest, ArrayList<Integer> globalBest) {
ArrayList<Integer> newPosition = new ArrayList<>(currentPosition);
// Aplicar intercambios para simular "velocidades"
for (int i = 0; i < numCities; i++) {
if (random.nextDouble() < w) {
int swapIndex1 = random.nextInt(numCities);
int swapIndex2 = random.nextInt(numCities);
Collections.swap(newPosition, swapIndex1, swapIndex2);
}
if (random.nextDouble() < c1) {
int swapIndex = personalBest.indexOf(newPosition.get(i));
Collections.swap(newPosition, i, swapIndex);
}
if (random.nextDouble() < c2) {
int swapIndex = globalBest.indexOf(newPosition.get(i));
Collections.swap(newPosition, i, swapIndex);
}
}
return newPosition;
}
public double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Retorno al inicio
return totalDistance;
}
}
Resultado:
run:
Ruta óptima aproximada encontrada: [15, 9, 5, 2, 7, 10, 3, 4, 0, 13, 8, 11, 12, 1, 6, 14]
Distancia mínima aproximada: 25093.0
BUILD SUCCESSFUL (total time: 1 second)
jueves, 15 de agosto de 2024
Problema del viajante de Comercio TSP (XIV). Método Programación Lineal Entera (PLE).
El algoritmo formula el TSP como un problema de optimización matemática donde las variables de decisión son enteras (generalmente binarias). Busca minimizar la distancia total del recorrido sujeto a restricciones que aseguran que cada ciudad se visite exactamente una vez y que el tour sea continuo.
Características:
. Exactitud: Garantiza encontrar la solución óptima global, si existe y si el algoritmo se ejecuta hasta su finalización.
. Formulación matemática: Utiliza variables binarias para representar las decisiones de viaje entre ciudades.
. Función objetivo: Minimiza la suma de las distancias entre las ciudades visitadas consecutivamente.
. Complejidad: Es un problema NP-duro, lo que significa que el tiempo de ejecución puede crecer exponencialmente con el tamaño del problema.
. Métodos de resolución: Suele utilizar técnicas como ramificación y acotación (branch and bound) o planos de corte (cutting planes).
. Escalabilidad: Eficiente para instancias pequeñas a medianas, pero puede volverse computacionalmente intensivo para problemas grandes.
. Flexibilidad: Permite incorporar fácilmente restricciones adicionales al problema base.
. Precisión: No se ve afectado por errores de redondeo como algunos métodos heurísticos.
. Uso de software especializado: A menudo se implementa utilizando solucionadores de programación lineal entera como CPLEX, Gurobi o CBC.
Código Java (TSP_IntegerProgramming):
package tsp_programacionlinealentera;
import java.util.ArrayList;
public class TSP_ProgramacionLinealEntera {
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}
};
TSPIP tsp = new TSPIP(distanceMatrix);
ArrayList<Integer> bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("Ruta óptima aproximada encontrada: " + bestRoute);
System.out.println("Distancia mínima aproximada: " + bestDistance);
}
}
Código Java (TSPIP.java):
package tsp_programacionlinealentera;
import java.util.ArrayList;
public class TSPIP {
private final double[][] distanceMatrix;
private final int numCities;
public TSPIP(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
public ArrayList<Integer> solve() {
ArrayList<Integer> currentRoute = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
currentRoute.add(i);
}
double currentDistance = calculateTotalDistance(currentRoute);
boolean improved = true;
while (improved) {
improved = false;
for (int i = 1; i < numCities - 1; i++) {
for (int j = i + 1; j < numCities; j++) {
ArrayList<Integer> newRoute = new ArrayList<>(currentRoute);
reverse(newRoute, i, j);
double newDistance = calculateTotalDistance(newRoute);
if (newDistance < currentDistance) {
currentRoute = newRoute;
currentDistance = newDistance;
improved = true;
}
}
}
}
return currentRoute;
}
private void reverse(ArrayList<Integer> route, int start, int end) {
while (start < end) {
int temp = route.get(start);
route.set(start, route.get(end));
route.set(end, temp);
start++;
end--;
}
}
public double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Return to start
return totalDistance;
}
}
Resultado:
run:
Ruta óptima aproximada encontrada: [0, 4, 3, 10, 7, 8, 11, 2, 14, 5, 12, 1, 9, 15, 6, 13]
Distancia mínima aproximada: 30268.0
BUILD SUCCESSFUL (total time: 0 seconds)
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)
Problema del viajante de Comercio TSP (XII). Método de Recocido Simulado (Simulated Annealing).
El Algoritmo de Recocido Simulado (Simulated Annealing) es una técnica metaheurística inspirada en el proceso de enfriamiento de metales, donde se trata de encontrar una solución cercana al óptimo global para problemas de optimización, como el Problema del Viajero (TSP). El algoritmo funciona de la siguiente manera:
Inicialización: Comienza con una solución inicial (ruta en el caso del TSP) y una temperatura inicial alta.
Vecindario: En cada iteración, se genera una nueva solución en el vecindario de la solución actual, por ejemplo, intercambiando dos ciudades en la ruta.
Aceptación de Soluciones: La nueva solución se acepta automáticamente si es mejor que la solución actual. Si es peor, se acepta con una probabilidad que disminuye a medida que la temperatura baja, permitiendo así escapar de óptimos locales.
Enfriamiento: La temperatura se reduce gradualmente según una política de enfriamiento, hasta que se alcanza un umbral mínimo, momento en el que se detiene la búsqueda.
Criterio de Terminación: El algoritmo termina cuando la temperatura es muy baja o después de un número fijo de iteraciones sin mejora significativa.
Código Java (TSP_RecocidoSimulado.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
public class TSP_RecocidoSimulado {
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, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 5176, 967, 3706, 6509, 7380, 1942, 0, 6631, 1397},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 6631, 0, 2345},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 1397, 2345, 0}
};
// Parametros de entrada:
double TemperaturaInicial = 10000;
double TasaEnfriamiento = 0.9999;
int NumeroIteraciones = 1000000;
TSPRS tsp = new TSPRS(distanceMatrix, TemperaturaInicial, TasaEnfriamiento, NumeroIteraciones);
// Generar una solución inicial (ruta aleatoria)
ArrayList<Integer> initialRoute = new ArrayList<>();
for (int i = 0; i < distanceMatrix.length; i++) {
initialRoute.add(i);
}
Collections.shuffle(initialRoute);
// Resolver el TSP usando Recocido Simulado
ArrayList<Integer> bestRoute = tsp.solve(initialRoute);
double bestDistance = tsp.calculateTotalDistance(bestRoute);
// Imprimir los resultados
System.out.println("Ruta óptima encontrada: " + bestRoute);
System.out.println("Distancia mínima: " + bestDistance);
}
}
Código Java (TSPRS.java):
package tsp_recocidosimulado;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class TSPRS {
private final double[][] distanceMatrix;
private final double initialTemperature;
private final double coolingRate;
private final int maxIterations;
private final Random random;
public TSPRS(double[][] distanceMatrix, double initialTemperature, double coolingRate, int maxIterations) {
this.distanceMatrix = distanceMatrix;
this.initialTemperature = initialTemperature;
this.coolingRate = coolingRate;
this.maxIterations = maxIterations;
this.random = new Random();
}
public ArrayList<Integer> solve(ArrayList<Integer> initialRoute) {
ArrayList<Integer> currentRoute = new ArrayList<>(initialRoute);
ArrayList<Integer> bestRoute = new ArrayList<>(initialRoute);
double bestDistance = calculateTotalDistance(bestRoute);
double temperature = initialTemperature;
int iteration = 0;
while (temperature > 1 && iteration < maxIterations) {
ArrayList<Integer> newRoute = generateNeighbor(new ArrayList<>(currentRoute));
double currentDistance = calculateTotalDistance(currentRoute);
double newDistance = calculateTotalDistance(newRoute);
if (acceptanceProbability(currentDistance, newDistance, temperature) > random.nextDouble()) {
currentRoute = new ArrayList<>(newRoute);
}
if (calculateTotalDistance(currentRoute) < bestDistance) {
bestRoute = new ArrayList<>(currentRoute);
bestDistance = calculateTotalDistance(bestRoute);
}
temperature *= coolingRate;
iteration++;
}
return bestRoute;
}
private ArrayList<Integer> generateNeighbor(ArrayList<Integer> route) {
int pos1 = random.nextInt(route.size());
int pos2 = random.nextInt(route.size());
Collections.swap(route, pos1, pos2);
return route;
}
private double acceptanceProbability(double currentDistance, double newDistance, double temperature) {
if (newDistance < currentDistance) {
return 1.0;
}
return Math.exp((currentDistance - newDistance) / temperature);
}
double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Regreso a la ciudad de inicio
return totalDistance;
}
}
Resultado:
run:
Ruta óptima encontrada: [7, 8, 11, 2, 5, 14, 6, 1, 12, 3, 4, 0, 13, 15, 9, 10]
Distancia mínima: 23620.0
BUILD SUCCESSFUL (total time: 0 seconds)
Problema del viajante de Comercio TSP (XI). Método Búsqueda Local (LS).
El Algoritmo de Búsqueda Local (LS) es una técnica de optimización heurística que busca mejorar una solución inicial explorando el espacio de soluciones vecinas. Es especialmente útil para problemas de optimización combinatoria, como el Problema del Viajante de Comercio (TSP).
Características:
Solución Inicial: Comienza con una solución factible, que puede generarse de manera aleatoria o utilizando heurísticas simples.
Vecinos: En cada iteración, el algoritmo genera una lista de soluciones vecinas a partir de la solución actual. Estos vecinos se obtienen mediante movimientos locales, que son pequeñas modificaciones a la solución (por ejemplo, intercambiar dos elementos en el TSP).
Criterio de Evaluación: La búsqueda local evalúa cada solución vecina y selecciona la que tenga el mejor valor según la función objetivo (en el TSP, la distancia total).
Actualización de la Solución: La solución actual se actualiza con la mejor solución vecina encontrada. Si la mejor solución vecina es peor que la solución actual, el algoritmo puede detenerse o seguir buscando.
Criterios de Parada: El algoritmo puede detenerse si no se encuentra una mejor solución después de un número predefinido de iteraciones (1 millon) o si se alcanza un criterio de convergencia.
Ventajas:
Simplicidad: Es fácil de implementar y entender.
Rapidez: A menudo converge rápidamente a una solución, especialmente para problemas de menor dimensión.
Desventajas:
Óptimos Locales: Puede quedarse atrapado en soluciones subóptimas, conocidas como óptimos locales, ya que solo explora soluciones cercanas a la actual.
Dependencia de la Solución Inicial: La calidad de la solución final puede depender significativamente de la solución inicial elegida.
Código Java (TSP_BusquedaLocal.java):
package tsp_busquedalocal;
import java.util.Arrays;
import java.util.Random;
public class TSP_BusquedaLocal {
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, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 5032, 7380, 4943, 4289, 0, 984, 9450},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 984, 0, 5211},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 9450, 5211, 0}
};
TSPLS tsp = new TSPLS(distanceMatrix);
int[] bestRoute = tsp.solve();
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("> Ruta óptima encontrada: " + Arrays.toString(bestRoute));
System.out.println("> Distancia mínima: " + bestDistance);
}
}
Código Java (TSPLS.java):
package tsp_busquedalocal;
import java.util.Random;
class TSPLS {
private final double[][] distanceMatrix;
private final int n;
private final Random random = new Random();
public TSPLS(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.n = distanceMatrix.length;
}
public int[] solve() {
int[] bestRoute = null;
double bestDistance = Double.MAX_VALUE;
for (int i = 0; i < 100000; i++) {
int[] currentRoute = generateInitialRoute();
currentRoute = localSearch(currentRoute);
double currentDistance = calculateTotalDistance(currentRoute);
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
bestRoute = currentRoute.clone();
}
}
return bestRoute;
}
private int[] generateInitialRoute() {
int[] route = new int[n];
for (int i = 0; i < n; i++) {
route[i] = i;
}
for (int i = n - 1; i > 0; i--) {
int j = random.nextInt(i + 1);
int temp = route[i];
route[i] = route[j];
route[j] = temp;
}
return route;
}
private int[] localSearch(int[] route) {
boolean improved;
int iterations = 0;
do {
improved = false;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (trySwap(route, i, j)) {
improved = true;
}
}
}
iterations++;
} while (improved && iterations < 100); // Limitado a 100 iteraciones
return route;
}
private boolean trySwap(int[] route, int i, int j) {
double change = calculateSwapChange(route, i, j);
if (change < 0) {
int temp = route[i];
route[i] = route[j];
route[j] = temp;
return true;
}
return false;
}
private double calculateSwapChange(int[] route, int i, int j) {
double change = 0;
int prev_i = (i > 0) ? route[i - 1] : route[n - 1];
int next_j = (j < n - 1) ? route[j + 1] : route[0];
change -= distanceMatrix[prev_i][route[i]];
change -= distanceMatrix[route[j]][next_j];
change += distanceMatrix[prev_i][route[j]];
change += distanceMatrix[route[i]][next_j];
if (j == i + 1) {
change -= distanceMatrix[route[i]][route[j]];
change += distanceMatrix[route[j]][route[i]];
} else {
int next_i = route[i + 1];
int prev_j = route[j - 1];
change -= distanceMatrix[route[i]][next_i];
change -= distanceMatrix[prev_j][route[j]];
change += distanceMatrix[route[j]][next_i];
change += distanceMatrix[prev_j][route[i]];
}
return change;
}
double calculateTotalDistance(int[] route) {
double totalDistance = 0;
for (int i = 0; i < n - 1; i++) {
totalDistance += distanceMatrix[route[i]][route[i + 1]];
}
totalDistance += distanceMatrix[route[n - 1]][route[0]];
return totalDistance;
}
}
Resultado:
run:
> Ruta óptima encontrada: [4, 3, 11, 2, 5, 12, 1, 6, 14, 9, 10, 15, 7, 8, 13, 0]
> Distancia mínima: 21420.0
BUILD SUCCESSFUL (total time: 2 seconds)
Problema del viajante de Comercio TSP (X). Método Tabu Search (TS).
El algoritmo Tabú es un enfoque de optimización heurística utilizado para resolver problemas combinatorios complejos, como el TSP. Este algoritmo se basa en la búsqueda local, pero incorpora un mecanismo de memoria para evitar ciclos y mejorar la exploración de soluciones.
Características:
Búsqueda Local: El algoritmo comienza con una solución inicial y mejora iterativamente a partir de esta mediante movimientos locales. Un movimiento local implica realizar pequeños cambios en la solución actual (por ejemplo, intercambiar dos ciudades en el TSP).
Lista Tabú: Para evitar que el algoritmo se quede atrapado en óptimos locales, utiliza una lista tabú que almacena soluciones recientemente exploradas. Cualquier movimiento que produzca una solución que esté en esta lista es prohibido temporalmente, lo que obliga al algoritmo a explorar nuevas áreas del espacio de soluciones.
Criterios de Evaluación: Durante cada iteración, el algoritmo evalúa los vecinos de la solución actual (todas las soluciones generadas mediante movimientos locales) y selecciona el mejor vecino que no esté en la lista tabú. Esto garantiza que el algoritmo explore soluciones prometedoras sin regresar a las soluciones prohibidas.
Actualización de la Lista Tabú: La lista tabú tiene un tamaño fijo y, a medida que se agregan nuevas soluciones, las más antiguas se eliminan. Esto permite que el algoritmo mantenga una memoria de las soluciones prohibidas sin consumir demasiada memoria.
Iteraciones y Criterios de Parada: El algoritmo se ejecuta durante un número predefinido de iteraciones o hasta que se alcanza un criterio de convergencia, como la estabilización de la mejor solución encontrada.
*Ventajas:
Eficiencia: A menudo encuentra soluciones de alta calidad en un tiempo razonable, incluso para problemas grandes.
Evita Mínimos Locales: La lista tabú permite escapar de óptimos locales, aumentando las posibilidades de encontrar la solución global óptima.
*Desventajas:
Parámetros Dependientes: La efectividad del algoritmo puede depender en gran medida de la elección de parámetros como el tamaño de la lista tabú y el número de iteraciones.
Complejidad: La implementación puede ser más compleja que otros métodos de búsqueda local debido al manejo de la lista tabú.
Código Java (TSP_TabuSearch.java):
package tsp_tabusearch;
public class TSP_TabuSearch {
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, 1527, 4847, 4770, 5032, 3387, 3706},
{7162, 9412, 9965, 1642, 8507, 9297, 7754, 324, 7480, 1527, 0, 2399, 9453, 7380, 8661, 1177},
{2260, 9051, 908, 1045, 3802, 2086, 2366, 8704, 2266, 4847, 2399, 0, 3224, 4943, 8957, 8156},
{4441, 1931, 9481, 1760, 3302, 1372, 8314, 7602, 9346, 4770, 9453, 3224, 0, 4289, 5709, 2858},
{510, 5817, 7708, 5607, 2944, 5616, 1360, 8091, 967, 5032, 7380, 4943, 4289, 0, 984, 9450},
{7138, 8633, 1874, 5053, 8613, 1981, 623, 1608, 9585, 3387, 8661, 8957, 5709, 984, 0, 5211},
{6509, 8513, 9303, 7776, 7257, 3412, 3915, 1286, 9113, 3706, 1177, 8156, 2858, 9450, 5211, 0}
};
int maxIterations = 1000; // Ajusta según sea necesario
int tabuListSize = 100; // Ajusta según sea necesario
TSPTS tsp = new TSPTS(distanceMatrix, maxIterations, tabuListSize);
tsp.solve();
System.out.println("> Mejor ruta encontrada: " + tsp.getBestRoute());
System.out.println("> Distancia mínima: " + tsp.getBestDistance());
}
}
Código Java (TSP_TabuSearch.java):
package tsp_tabusearch;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
class TSPTS {
private final double[][] distanceMatrix;
private final int maxIterations;
private final int tabuListSize;
private ArrayList<Integer> bestRoute;
private double bestDistance;
public TSPTS(double[][] distanceMatrix, int maxIterations, int tabuListSize) {
this.distanceMatrix = distanceMatrix;
this.maxIterations = maxIterations;
this.tabuListSize = tabuListSize;
this.bestRoute = new ArrayList<>();
this.bestDistance = Double.MAX_VALUE;
}
public void solve() {
int numCities = distanceMatrix.length;
ArrayList<Integer> currentRoute = initializeRoute(numCities);
double currentDistance = calculateTotalDistance(currentRoute);
HashSet<String> tabuList = new HashSet<>();
for (int iteration = 0; iteration < maxIterations; iteration++) {
ArrayList<Integer> bestNeighbor = null;
double bestNeighborDistance = Double.MAX_VALUE;
// Generar y evaluar vecinos
for (int i = 0; i < numCities - 1; i++) {
for (int j = i + 1; j < numCities; j++) {
ArrayList<Integer> neighbor = new ArrayList<>(currentRoute);
Collections.swap(neighbor, i, j); // Realiza un movimiento
String neighborKey = neighbor.toString(); // Clave para la lista tabú
// Evaluar si el vecino no está en la lista tabú
if (!tabuList.contains(neighborKey)) {
double neighborDistance = calculateTotalDistance(neighbor);
if (neighborDistance < bestNeighborDistance) {
bestNeighborDistance = neighborDistance;
bestNeighbor = neighbor;
}
}
}
}
// Actualizar la ruta actual
if (bestNeighbor != null) {
currentRoute = bestNeighbor;
currentDistance = bestNeighborDistance;
// Actualizar mejor ruta global
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
bestRoute = new ArrayList<>(currentRoute);
}
// Agregar a la lista tabú
tabuList.add(currentRoute.toString());
if (tabuList.size() > tabuListSize) {
// Eliminar el elemento más antiguo si se supera el tamaño
tabuList.remove(tabuList.iterator().next());
}
}
}
}
private ArrayList<Integer> initializeRoute(int numCities) {
ArrayList<Integer> route = new ArrayList<>();
for (int i = 0; i < numCities; i++) {
route.add(i);
}
Collections.shuffle(route); // Ruta inicial aleatoria
return route;
}
private double calculateTotalDistance(ArrayList<Integer> route) {
double totalDistance = 0.0;
for (int i = 0; i < route.size() - 1; i++) {
totalDistance += distanceMatrix[route.get(i)][route.get(i + 1)];
}
totalDistance += distanceMatrix[route.get(route.size() - 1)][route.get(0)]; // Regresar a la ciudad de inicio
return totalDistance;
}
public ArrayList<Integer> getBestRoute() {
return bestRoute;
}
public double getBestDistance() {
return bestDistance;
}
}
Resultado:
run:
> Mejor ruta encontrada: [6, 1, 12, 5, 14, 9, 10, 15, 7, 8, 13, 0, 4, 2, 11, 3]
> Distancia mínima: 22067.0
BUILD SUCCESSFUL (total time: 0 seconds)
Suscribirse a:
Entradas (Atom)