El algoritmo TSP Optimization (2-opt) es una técnica heurística utilizada para mejorar la solución del Problema del Viajante de Comercio, cuyo objetivo es encontrar la ruta más corta que visita un conjunto de ciudades exactamente una vez y regresa al punto de partida. El 2-opt es una de las maneras más simples y efectivas de optimizar una ruta existente, aunque no garantiza el óptimo global.
*Ejemplo visual de funcionamiento:
Imagina una ruta inicial que conecta las ciudades en el orden A -> B -> C -> D -> E -> A. El algoritmo 2-opt selecciona dos aristas, digamos A-B y D-E, y las intercambia invirtiendo el segmento entre ellas, resultando en la ruta A -> D -> C -> B -> E -> A. Si esta nueva ruta es más corta, se adopta como la nueva ruta y el proceso continúa.
Código Java 1 (TSP_Optimization.java):
package tsp_optimization;
import java.util.ArrayList;
import java.util.List;
public class TSP_Optimization {
public static void main(String[] args) {
double[][] distances = {
{0, 1190, 1255, 7549, 7009, 4245, 7539, 314, 993, 5236, 3676, 2508, 8987, 5886, 1835},
{1190, 0, 7723, 3900, 7082, 8972, 8360, 5127, 6002, 8613, 5598, 7216, 7303, 1013, 2294},
{1255, 7723, 0, 7843, 6636, 9905, 3190, 5337, 8012, 6704, 9300, 6966, 328, 2112, 1028},
{7549, 3900, 7843, 0, 2657, 5301, 9294, 1987, 8633, 6415, 2611, 8728, 3895, 7705, 7429},
{7009, 7082, 6636, 2657, 0, 8304, 2569, 9744, 7886, 9015, 8502, 4337, 5159, 32, 8341},
{4245, 8972, 9905, 5301, 8304, 0, 9945, 4113, 3297, 8881, 9562, 9211, 4182, 7529, 4457},
{7539, 8360, 3190, 9294, 2569, 9945, 0, 1714, 2308, 7467, 1861, 7895, 7867, 240, 2956},
{314, 5127, 5337, 1987, 9744, 4113, 1714, 0, 7642, 2461, 9780, 9201, 640, 9583, 8358},
{993, 6002, 8012, 8633, 7886, 3297, 2308, 7642, 0, 8584, 6593, 3903, 3533, 5105, 5461},
{5236, 8613, 6704, 6415, 9015, 8881, 7467, 2461, 8584, 0, 94, 9758, 2375, 5656, 3203},
{3676, 5598, 9300, 2611, 8502, 9562, 1861, 9780, 6593, 94, 0, 6284, 3894, 948, 633},
{2508, 7216, 6966, 8728, 4337, 9211, 7895, 9201, 3903, 9758, 6284, 0, 4675, 4214, 9524},
{8987, 7303, 328, 3895, 5159, 4182, 7867, 640, 3533, 2375, 3894, 4675, 0, 7004, 3146},
{5886, 1013, 2112, 7705, 32, 7529, 240, 9583, 5105, 5656, 948, 4214, 7004, 0, 1020},
{1835, 2294, 1028, 7429, 8341, 4457, 2956, 8358, 5461, 3203, 633, 9524, 3146, 1020, 0}
};
int n = distances.length;
// Pone nombre a los nodos siguiendo la secuencia del abcedario
List<String> cityNames = new ArrayList<>();
for (int i = 0; i < n; i++) {
char letter = (char) ('A' + i);
cityNames.add(String.valueOf(letter));
}
TSP2Opt tsp = new TSP2Opt(distances);
List<Integer> bestRoute = tsp.findBestRoute(1000);
double bestDistance = tsp.calculateTotalDistance(bestRoute);
System.out.println("Matriz de distancias :");
for (double[] distance : distances) {
for (int j = 0; j < distance.length; j++) {
System.out.printf("%7d", Math.round(distance[j]));
}
System.out.println();
}
System.out.println();
System.out.println("> Mejor ruta encontrada:");
bestRoute.forEach(city -> {
System.out.print(cityNames.get(city) + " ");
});
System.out.println(cityNames.get(bestRoute.get(0)));
System.out.println("> La distancia total recorrida es: " + bestDistance);
}
}
Código Java 2 (TSP2Opt.java):
package tsp_optimization;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TSP2Opt {
private final double[][] distances;
private final int numCities;
public TSP2Opt(double[][] distances) {
this.distances = distances;
this.numCities = distances.length;
}
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 - 1; i++) {
for (int j = i + 1; j < numCities; j++) {
List<Integer> newRoute = twoOptSwap(route, i, j);
if (calculateTotalDistance(newRoute) < calculateTotalDistance(route)) {
route = newRoute;
improved = true;
}
}
}
}
return route;
}
private List<Integer> twoOptSwap(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:
Matriz de distancias:
0 1190 1255 7549 7009 4245 7539 314 993 5236 3676 2508 8987 5886 1835
1190 0 7723 3900 7082 8972 8360 5127 6002 8613 5598 7216 7303 1013 2294
1255 7723 0 7843 6636 9905 3190 5337 8012 6704 9300 6966 328 2112 1028
7549 3900 7843 0 2657 5301 9294 1987 8633 6415 2611 8728 3895 7705 7429
7009 7082 6636 2657 0 8304 2569 9744 7886 9015 8502 4337 5159 32 8341
4245 8972 9905 5301 8304 0 9945 4113 3297 8881 9562 9211 4182 7529 4457
7539 8360 3190 9294 2569 9945 0 1714 2308 7467 1861 7895 7867 240 2956
314 5127 5337 1987 9744 4113 1714 0 7642 2461 9780 9201 640 9583 8358
993 6002 8012 8633 7886 3297 2308 7642 0 8584 6593 3903 3533 5105 5461
5236 8613 6704 6415 9015 8881 7467 2461 8584 0 94 9758 2375 5656 3203
3676 5598 9300 2611 8502 9562 1861 9780 6593 94 0 6284 3894 948 633
2508 7216 6966 8728 4337 9211 7895 9201 3903 9758 6284 0 4675 4214 9524
8987 7303 328 3895 5159 4182 7867 640 3533 2375 3894 4675 0 7004 3146
5886 1013 2112 7705 32 7529 240 9583 5105 5656 948 4214 7004 0 1020
1835 2294 1028 7429 8341 4457 2956 8358 5461 3203 633 9524 3146 1020 0
> Mejor ruta encontrada:
E D F I L A B O C M H J K G N E
> La distancia total recorrida es: 27834.0
BUILD SUCCESSFUL (total time: 0 seconds)
miércoles, 7 de agosto de 2024
Problema del Viajante de Comercio TSP (V.1). Método Optimization 2-Opt.
sábado, 27 de julio de 2024
Juegos VI: The Marconix Codebreaker (Juego de Posiciones)
The Marconix Codebreaker
Descripción del juego:
Este es un juego de ordenamiento en el que el jugador debe organizar una serie de casillas, cada una representada por una letra (A-F), en el orden correcto. Cada letra tiene asociado un número oculto (1-6) y el objetivo es ordenar las letras de manera que sus números asociados estén en orden ascendente.
Reglas del juego:
El juego comienza con 6 casillas (A-F) en orden alfabético y cada letra tiene un número oculto (1-6) asignado aleatoriamente.
El jugador tiene una puntuación inicial de 1000 puntos.
En cada turno, el jugador puede:
. Pedir una pista (cuesta 50 puntos)
. Reorganizar las casillas (cuesta 100 puntos)
. Intentar salir del juego
Las pistas proporcionan información sobre el orden relativo de tres letras.
Al reorganizar, el jugador debe ingresar un nuevo orden para todas las letras.
Después de cada acción, el juego verifica si las casillas están en el orden correcto.
El juego termina cuando:
.El jugador ordena correctamente las casillas (victoria)
.El jugador decide salir del juego
La puntuación final se basa en los puntos restantes después de restar el costo de las pistas y reorganizaciones utilizadas.
Estructura jerárquica
Marconix
├── Variables estáticas
│ ├── NUM_CASILLAS
│ ├── letras
│ ├── numeros
│ ├── letraANumero
│ ├── pistasUsadas
│ └── puntuacion
│
├── main()
│ ├── inicializarJuego()
│ └── jugar()
│
├── inicializarJuego()
│
├── jugar()
│ ├── mostrarCasillas()
│ ├── darPista()
│ │ └── generarPistaCompleja()
│ ├── reorganizarCasillas()
│ │ └── darFeedback()
│ └── estaOrdenado()
│
├── mostrarCasillas()
│
├── darPista()
│ └── generarPistaCompleja()
│
├── generarPistaCompleja()
│
├── reorganizarCasillas()
│ └── darFeedback()
│
├── darFeedback()
│
└── estaOrdenado()
Diagrama de funcionamiento
┌─► Inicio
├─► Inicializar juego
├◄───────────────────────────────────────────────────────┐
├─► Mostrar casillas actuales │
├─► Mostrar puntuación │
└─► Preguntar por pista │
├─► Sí │
│ └─► Dar pista │
│ Restar 50 puntos ───────────────────────────►┤
└─► No │
└─► Preguntar por reorganizar │
├─► Sí │
│ └─► Reorganizar casillas │
│ Restar 100 puntos ──────────────────►┤
└─► No │
└─► Preguntar por salir │
├─► Sí │
│ └─► Terminar juego* │
└─► No │
└─► Verificar si está ordenado │
├─► Sí │
│ └─► Mostrar victoria │
│ Terminar juego* │
└─► No ─────────────────────►┘
Código Java (Marconix.java):
package Marconix;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Marconix {
private static final int NUM_CASILLAS = 6;
private static final List<Character> letras = new ArrayList<>();
private static final List<Integer> numeros = new ArrayList<>();
private static final Map<Character, Integer> letraANumero = new HashMap<>();
private static final Set<String> pistasUsadas = new HashSet<>();
private static int puntuacion = 1000;
public static void main(String[] args) {
inicializarJuego();
jugar();
}
private static void inicializarJuego() {
for (char c = 'A'; c < 'A' + NUM_CASILLAS; c++) {
letras.add(c);
}
for (int i = 1; i <= NUM_CASILLAS; i++) {
numeros.add(i);
}
Collections.shuffle(numeros);
for (int i = 0; i < NUM_CASILLAS; i++) {
letraANumero.put(letras.get(i), numeros.get(i));
}
}
private static void jugar() {
try (Scanner scanner = new Scanner(System.in)) {
while (true) {
mostrarCasillas();
System.out.println("Puntuación actual: " + puntuacion);
System.out.println("¿Quieres una pista? (s/n)");
String respuesta = scanner.nextLine().toLowerCase();
if (respuesta.equals("s")) {
darPista();
puntuacion -= 50;
} else if (respuesta.equals("n")) {
System.out.println("¿Quieres reorganizar las casillas? (s/n)");
respuesta = scanner.nextLine().toLowerCase();
if (respuesta.equals("s")) {
reorganizarCasillas(scanner);
puntuacion -= 100;
} else if (respuesta.equals("n")) {
System.out.println("¿Quieres salir del juego? (s/n)");
if (scanner.nextLine().toLowerCase().equals("s")) {
break;
}
}
}
if (estaOrdenado()) {
System.out.println("¡Felicidades! Has ordenado correctamente las casillas.");
System.out.println("Puntuación final: " + puntuacion);
break;
}
}
}
}
private static void mostrarCasillas() {
System.out.println("Orden actual de las casillas:");
letras.forEach(letra -> System.out.print(letra + " "));
System.out.println();
}
private static void darPista() {
String pista;
do {
pista = generarPistaCompleja();
} while (pistasUsadas.contains(pista));
pistasUsadas.add(pista);
System.out.println("Pista: " + pista);
}
private static String generarPistaCompleja() {
List<Character> letrasAleatorias = new ArrayList<>(letras);
Collections.shuffle(letrasAleatorias);
char letra1 = letrasAleatorias.get(0);
char letra2 = letrasAleatorias.get(1);
char letra3 = letrasAleatorias.get(2);
int num1 = letraANumero.get(letra1);
int num2 = letraANumero.get(letra2);
int num3 = letraANumero.get(letra3);
if (num1 < num2 && num2 < num3) {
return letra1 + " < " + letra2 + " < " + letra3;
} else if (num1 < num2 && num2 > num3 && num1 < num3) {
return letra1 + " < " + letra3 + " < " + letra2;
} else if (num2 < num1 && num1 < num3) {
return letra2 + " < " + letra1 + " < " + letra3;
} else if (num2 < num3 && num3 < num1) {
return letra2 + " < " + letra3 + " < " + letra1;
} else if (num3 < num1 && num1 < num2) {
return letra3 + " < " + letra1 + " < " + letra2;
} else {
return letra3 + " < " + letra2 + " < " + letra1;
}
}
private static void reorganizarCasillas(Scanner scanner) {
System.out.println("Ingresa el nuevo orden de las letras (sin espacios):");
String nuevoOrden = scanner.nextLine().toUpperCase();
if (nuevoOrden.length() == NUM_CASILLAS && nuevoOrden.chars().distinct().count() == NUM_CASILLAS) {
letras.clear();
for (char c : nuevoOrden.toCharArray()) {
letras.add(c);
}
darFeedback();
} else {
System.out.println("Orden inválido. Asegúrate de incluir todas las letras una vez.");
}
}
private static void darFeedback() {
int posicionesCorrectas = 0;
for (int i = 0; i < NUM_CASILLAS; i++) {
if (letraANumero.get(letras.get(i)) == i + 1) {
posicionesCorrectas++;
}
}
System.out.println("Tienes " + posicionesCorrectas + " letra(s) en la posición correcta.");
}
private static boolean estaOrdenado() {
for (int i = 1; i < NUM_CASILLAS; i++) {
if (letraANumero.get(letras.get(i - 1)) > letraANumero.get(letras.get(i))) {
return false;
}
}
return true;
}
}
Resultado:
run:
Orden actual de las casillas:
A B C D E F
Puntuación actual: 1000
¿Quieres una pista? (s/n)
s
Pista: D < F < A
Orden actual de las casillas:
A B C D E F
Puntuación actual: 950
¿Quieres una pista? (s/n)
n
¿Quieres reorganizar las casillas? (s/n)
s
Ingresa el nuevo orden de las letras (sin espacios):
BCDEFA
Tienes 3 letra(s) en la posición correcta.
Orden actual de las casillas:
B C D E F A
Puntuación actual: 850
¿Quieres una pista? (s/n)
n
¿Quieres reorganizar las casillas? (s/n)
n
¿Quieres salir del juego? (s/n)
s
BUILD SUCCESSFUL (total time: 2 minutes 11 seconds)
lunes, 22 de julio de 2024
Juegos V.2: Approximate(GUI): El Juego de Números y Operaciones.
Este algoritmo proporciona una interfaz clara y funcional para la aplicación 'Approximate', permitiendo al usuario ingresar o generar números, realizar cálculos y ver los resultados de manera intuitiva mediante interfaz de usuario (GUI).
Desde NetBeans y en modo "Design" creamos la interfaz de usuario (GUI) siguiendo la siguiente nomenclatura:
Estructura GUI:
MainApproximate
│
└─── jPanel_Main
│
├─── jPanel_Botonera
│ ├─── jButtonRandom
│ ├─── jButtonLimpiar
│ └─── jButtonCalcular
│
├─── jPanel_NumeroObjetivo
│ └─── jTextField_NumObjetivo
│
├─── jPanel_NumerosDisponibles
│ ├─── jTextField1
│ ├─── jTextField2
│ ├─── jTextField3
│ ├─── jTextField4
│ ├─── jTextField5
│ └─── jTextField6
│
├─── jSeparator1
│
├─── jPanel_MejorAproximacion
│ └─── jTextField_MejorAproximacion
│
└─── jPanel_Expresion
└─── jTextField_Expresion
Código Java (MainApproximate.java):
package approximategui;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import javax.swing.JOptionPane;
public class MainApproximate extends javax.swing.JFrame {
private static final char[] OPERADORES = {'+', '-', '*', '/'};
private static int mejorResultado;
private static String mejorExpresion;
private static final int OBJETIVO_NO_ALCANZADO = Integer.MAX_VALUE;
private final Random random = new Random();
public MainApproximate() {
initComponents();
setLocationRelativeTo(null);
limpiarDatos();
}
@SuppressWarnings("unchecked")
// <editor-fold defaultstate="collapsed" desc="Generated Code">
private void initComponents() { ... } // Código generado por Netbeans desde modo "Design"
private void jButtonCalcularActionPerformed(java.awt.event.ActionEvent evt) {
calcularMejorAproximacion();
}
private void jButtonRandomActionPerformed(java.awt.event.ActionEvent evt) {
generarNumerosAleatorios();
// Limpiar los resultados
jTextField_MejorAproximacion.setText("");
jTextField_Expresion.setText("");
}
private void jButtonLimpìarActionPerformed(java.awt.event.ActionEvent evt) {
limpiarDatos();
}
private void limpiarDatos() {
// Limpiar el número objetivo
jTextField_NumObjetivo.setText("");
// Limpiar los números disponibles
jTextField1.setText("");
jTextField2.setText("");
jTextField3.setText("");
jTextField4.setText("");
jTextField5.setText("");
jTextField6.setText("");
// Limpiar los resultados
jTextField_MejorAproximacion.setText("");
jTextField_Expresion.setText("");
// Resetear las variables globales si es necesario
mejorResultado = OBJETIVO_NO_ALCANZADO;
mejorExpresion = "";
}
private void generarNumerosAleatorios() {
int objetivo = random.nextInt(999) + 1;
jTextField_NumObjetivo.setText(String.valueOf(objetivo));
Set<Integer> numerosSet = new HashSet<>();
while (numerosSet.size() < 6) {
int nuevoNumero = random.nextInt(100) + 1;
if (nuevoNumero != objetivo) {
numerosSet.add(nuevoNumero);
}
}
Integer[] numeros = numerosSet.toArray(new Integer[0]);
jTextField1.setText(String.valueOf(numeros[0]));
jTextField2.setText(String.valueOf(numeros[1]));
jTextField3.setText(String.valueOf(numeros[2]));
jTextField4.setText(String.valueOf(numeros[3]));
jTextField5.setText(String.valueOf(numeros[4]));
jTextField6.setText(String.valueOf(numeros[5]));
}
private void calcularMejorAproximacion() {
try {
int objetivo = Integer.parseInt(jTextField_NumObjetivo.getText());
Integer[] numeros = new Integer[6];
numeros[0] = Integer.parseInt(jTextField1.getText());
numeros[1] = Integer.parseInt(jTextField2.getText());
numeros[2] = Integer.parseInt(jTextField3.getText());
numeros[3] = Integer.parseInt(jTextField4.getText());
numeros[4] = Integer.parseInt(jTextField5.getText());
numeros[5] = Integer.parseInt(jTextField6.getText());
mejorResultado = OBJETIVO_NO_ALCANZADO;
mejorExpresion = "";
generarCombinaciones(numeros, objetivo);
if (mejorResultado != OBJETIVO_NO_ALCANZADO) {
jTextField_MejorAproximacion.setText(String.valueOf(mejorResultado));
jTextField_Expresion.setText(mejorExpresion);
} else {
jTextField_MejorAproximacion.setText("No encontrado");
jTextField_Expresion.setText("N/A");
}
} catch (NumberFormatException e) {
JOptionPane.showMessageDialog(this, "Por favor, ingrese números válidos en todos los campos.", "Error de entrada", JOptionPane.ERROR_MESSAGE);
}
}
private void generarCombinaciones(Integer[] numeros, int objetivo) {
for (int i = 1; i <= numeros.length; i++) {
generarPermutaciones(Arrays.asList(numeros), new ArrayList<>(), i, objetivo);
}
}
private void generarPermutaciones(List<Integer> numeros, List<Integer> permutacion, int longitud, int objetivo) {
if (permutacion.size() == longitud) {
generarOperaciones(permutacion, new ArrayList<>(), objetivo);
return;
}
for (int i = 0; i < numeros.size(); i++) {
List<Integer> nuevaPermutacion = new ArrayList<>(permutacion);
nuevaPermutacion.add(numeros.get(i));
List<Integer> nuevosNumeros = new ArrayList<>(numeros);
nuevosNumeros.remove(i);
generarPermutaciones(nuevosNumeros, nuevaPermutacion, longitud, objetivo);
}
}
private void generarOperaciones(List<Integer> numeros, List<Character> operadores, int objetivo) {
if (operadores.size() == numeros.size() - 1) {
evaluarExpresion(numeros, operadores, objetivo);
return;
}
for (char operador : OPERADORES) {
List<Character> nuevosOperadores = new ArrayList<>(operadores);
nuevosOperadores.add(operador);
generarOperaciones(numeros, nuevosOperadores, objetivo);
}
}
private void evaluarExpresion(List<Integer> numeros, List<Character> operadores, int objetivo) {
String expresion = construirExpresion(numeros, operadores);
try {
int resultado = evaluarExpresionAritmetica(expresion);
int diferencia = Math.abs(resultado - objetivo);
if (diferencia < Math.abs(mejorResultado - objetivo)) {
mejorResultado = resultado;
mejorExpresion = expresion;
}
} catch (ArithmeticException e) {
// Ignorar divisiones inválidas
}
}
private String construirExpresion(List<Integer> numeros, List<Character> operadores) {
StringBuilder expresion = new StringBuilder();
expresion.append(numeros.get(0));
for (int i = 0; i < operadores.size(); i++) {
expresion.append(operadores.get(i));
expresion.append(numeros.get(i + 1));
}
return expresion.toString();
}
private int evaluarExpresionAritmetica(String expresion) {
List<String> tokens = tokenizarExpresion(expresion);
return evaluarTokens(tokens);
}
private List<String> tokenizarExpresion(String expresion) {
List<String> tokens = new ArrayList<>();
StringBuilder numeroActual = new StringBuilder();
for (char c : expresion.toCharArray()) {
if (Character.isDigit(c)) {
numeroActual.append(c);
} else {
if (numeroActual.length() > 0) {
tokens.add(numeroActual.toString());
numeroActual = new StringBuilder();
}
tokens.add(String.valueOf(c));
}
}
if (numeroActual.length() > 0) {
tokens.add(numeroActual.toString());
}
return tokens;
}
private int evaluarTokens(List<String> tokens) {
// Primero, evaluamos multiplicaciones y divisiones
for (int i = 1; i < tokens.size() - 1; i += 2) {
String operador = tokens.get(i);
if (operador.equals("*") || operador.equals("/")) {
int a = Integer.parseInt(tokens.get(i - 1));
int b = Integer.parseInt(tokens.get(i + 1));
int resultado;
if (operador.equals("*")) {
resultado = a * b;
} else {
if (b == 0 || a % b != 0) {
throw new ArithmeticException("División inválida");
}
resultado = a / b;
}
tokens.set(i - 1, String.valueOf(resultado));
tokens.remove(i);
tokens.remove(i);
i -= 2;
}
}
// Luego, evaluamos sumas y restas
int resultado = Integer.parseInt(tokens.get(0));
for (int i = 1; i < tokens.size(); i += 2) {
String operador = tokens.get(i);
int numero = Integer.parseInt(tokens.get(i + 1));
if (operador.equals("+")) {
resultado += numero;
} else if (operador.equals("-")) {
resultado -= numero;
}
}
return resultado;
}
public static void main(String args[]) {
java.awt.EventQueue.invokeLater(() -> {
new MainApproximate().setVisible(true);
});
}
// Variables declaration - do not modify
private javax.swing.JButton jButtonCalcular;
private javax.swing.JButton jButtonLimpìar;
private javax.swing.JButton jButtonRandom;
private javax.swing.JPanel jPanel_Botonera;
private javax.swing.JPanel jPanel_Expresion;
private javax.swing.JPanel jPanel_Main;
private javax.swing.JPanel jPanel_MejorAproximacion;
private javax.swing.JPanel jPanel_NumeroObjetivo;
private javax.swing.JPanel jPanel_NumerosDisponibles;
private javax.swing.JSeparator jSeparator1;
private javax.swing.JTextField jTextField1;
private javax.swing.JTextField jTextField2;
private javax.swing.JTextField jTextField3;
private javax.swing.JTextField jTextField4;
private javax.swing.JTextField jTextField5;
private javax.swing.JTextField jTextField6;
private javax.swing.JTextField jTextField_Expresion;
private javax.swing.JTextField jTextField_MejorAproximacion;
private javax.swing.JTextField jTextField_NumObjetivo;
// End of variables declaration
}
Resultado:
sábado, 20 de julio de 2024
Juegos V: Approximate: El Juego de Números y Operaciones.
Caracteristicas del Juego:
. Objetivo: Calcular un número específico (el objetivo) usando los números disponibles y las operaciones aritméticas básicas.
. Números Disponibles: Se generan seis números aleatorios que pueden usarse cada uno una sola vez en los cálculos.
. Operaciones Permitidas: Suma, resta, multiplicación y división(siempre que el resultado sea un número entero).
. Uso de Números: Cada número puede usarse una sola vez.
. Resultado Entero: Todas las operaciones deben producir resultados enteros.
El algoritmo explora exhaustivamente todas las combinaciones posibles de los seis números generados aleatoriamente y las operaciones básicas, buscando alcanzar el número objetivo o el más cercano posible. Devuelve el mejor resultado encontrado junto con la expresión utilizada para llegar a él.
Estructura del código Approximate:
approximate (paquete)
│
└── Approximate (clase pública)
│
├── static fields (campos estáticos)
│ ├── OPERADORES (array de caracteres)
│ ├── mejorResultado (entero)
│ ├── mejorExpresion (cadena)
│ └── OBJETIVO_NO_ALCANZADO (constante entera)
│
├── main() (método principal)
│
└── private static methods (métodos privados estáticos)
├── generarCombinaciones()
├── generarPermutaciones()
├── generarOperaciones()
├── evaluarExpresion()
├── construirExpresion()
├── evaluarExpresionAritmetica()
├── tokenizarExpresion()
└── evaluarTokens()
Código Java (Approximate.java):
package approximate;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
public class Approximate {
private static final char[] OPERADORES = {'+', '-', '*', '/'};
private static int mejorResultado;
private static String mejorExpresion;
private static final int OBJETIVO_NO_ALCANZADO = Integer.MAX_VALUE;
public static void main(String[] args) {
Random random = new Random();
int objetivo = random.nextInt(999) + 1;
Set<Integer> numerosSet = new HashSet<>();
while (numerosSet.size() < 6) {
int nuevoNumero = random.nextInt(100) + 1;
if (nuevoNumero != objetivo) {
numerosSet.add(nuevoNumero);
}
}
Integer[] numeros = numerosSet.toArray(new Integer[0]);
System.out.println("Número objetivo: " + objetivo);
System.out.println("Números disponibles: " + Arrays.toString(numeros));
mejorResultado = OBJETIVO_NO_ALCANZADO;
mejorExpresion = "";
generarCombinaciones(numeros, objetivo);
if (mejorResultado != OBJETIVO_NO_ALCANZADO) {
System.out.println("Mejor aproximación: " + mejorResultado);
System.out.println("Expresión: " + mejorExpresion);
} else {
System.out.println("No se encontró una solución válida.");
}
}
private static void generarCombinaciones(Integer[] numeros, int objetivo) {
for (int i = 1; i <= numeros.length; i++) {
generarPermutaciones(Arrays.asList(numeros), new ArrayList<>(), i, objetivo);
}
}
private static void generarPermutaciones(List<Integer> numeros, List<Integer> permutacion, int longitud, int objetivo) {
if (permutacion.size() == longitud) {
generarOperaciones(permutacion, new ArrayList<>(), objetivo);
return;
}
for (int i = 0; i < numeros.size(); i++) {
List<Integer> nuevaPermutacion = new ArrayList<>(permutacion);
nuevaPermutacion.add(numeros.get(i));
List<Integer> nuevosNumeros = new ArrayList<>(numeros);
nuevosNumeros.remove(i);
generarPermutaciones(nuevosNumeros, nuevaPermutacion, longitud, objetivo);
}
}
private static void generarOperaciones(List<Integer> numeros, List<Character> operadores, int objetivo) {
if (operadores.size() == numeros.size() - 1) {
evaluarExpresion(numeros, operadores, objetivo);
return;
}
for (char operador : OPERADORES) {
List<Character> nuevosOperadores = new ArrayList<>(operadores);
nuevosOperadores.add(operador);
generarOperaciones(numeros, nuevosOperadores, objetivo);
}
}
private static void evaluarExpresion(List<Integer> numeros, List<Character> operadores, int objetivo) {
String expresion = construirExpresion(numeros, operadores);
try {
int resultado = evaluarExpresionAritmetica(expresion);
int diferencia = Math.abs(resultado - objetivo);
if (diferencia < Math.abs(mejorResultado - objetivo)) {
mejorResultado = resultado;
mejorExpresion = expresion;
}
} catch (ArithmeticException e) {
// Ignorar divisiones inválidas
}
}
private static String construirExpresion(List<Integer> numeros, List<Character> operadores) {
StringBuilder expresion = new StringBuilder();
expresion.append(numeros.get(0));
for (int i = 0; i < operadores.size(); i++) {
expresion.append(operadores.get(i));
expresion.append(numeros.get(i + 1));
}
return expresion.toString();
}
private static int evaluarExpresionAritmetica(String expresion) {
List<String> tokens = tokenizarExpresion(expresion);
return evaluarTokens(tokens);
}
private static List<String> tokenizarExpresion(String expresion) {
List<String> tokens = new ArrayList<>();
StringBuilder numeroActual = new StringBuilder();
for (char c : expresion.toCharArray()) {
if (Character.isDigit(c)) {
numeroActual.append(c);
} else {
if (numeroActual.length() > 0) {
tokens.add(numeroActual.toString());
numeroActual = new StringBuilder();
}
tokens.add(String.valueOf(c));
}
}
if (numeroActual.length() > 0) {
tokens.add(numeroActual.toString());
}
return tokens;
}
private static int evaluarTokens(List<String> tokens) {
// Primero, evaluamos multiplicaciones y divisiones
for (int i = 1; i < tokens.size() - 1; i += 2) {
String operador = tokens.get(i);
if (operador.equals("*") || operador.equals("/")) {
int a = Integer.parseInt(tokens.get(i - 1));
int b = Integer.parseInt(tokens.get(i + 1));
int resultado;
if (operador.equals("*")) {
resultado = a * b;
} else {
if (b == 0 || a % b != 0) {
throw new ArithmeticException("División inválida");
}
resultado = a / b;
}
tokens.set(i - 1, String.valueOf(resultado));
tokens.remove(i);
tokens.remove(i);
i -= 2;
}
}
// Luego, evaluamos sumas y restas
int resultado = Integer.parseInt(tokens.get(0));
for (int i = 1; i < tokens.size(); i += 2) {
String operador = tokens.get(i);
int numero = Integer.parseInt(tokens.get(i + 1));
if (operador.equals("+")) {
resultado += numero;
} else if (operador.equals("-")) {
resultado -= numero;
}
}
return resultado;
}
}
Resultado:
run:
Número objetivo: 127
Números disponibles: [49, 4, 53, 7, 87, 76]
Mejor aproximación: 127
Expresión: 49*4+7-76
BUILD SUCCESSFUL (total time: 2 seconds)
domingo, 14 de julio de 2024
Rotar matriz 90º. Uso de librería "Apache Commons Math".
Objetivo:
El objetivo del algoritmo es rotar una matriz o tabla de distancias 90 grados en sentido horario utilizando la librería Apache Commons Math.
La librería Apache Commons Math se utiliza para manejar eficientemente las operaciones matriciales, proporcionando una estructura de datos robusta (RealMatrix) y métodos optimizados para acceder y modificar los elementos de la matriz.
Requisitos:
- NetBeans IDE
- Apache Commons Math (versión 3.6.1)
Pasos:
1. Descarga la librería Apache Commons Math 3.6.1 desde:
https://archive.apache.org/dist/commons/math/binaries/
2. Buscar, descargar y descomprimir el archivo "commons-math3-3.6.1-bin.zip".
3. En NetBeans, añadir la librería "commons-math3-3.6.1.jar" al proyecto.
Código Java (MatrixRotator.java):
package matrixrotator;
import org.apache.commons.math3.linear.Array2DRowRealMatrix;
import org.apache.commons.math3.linear.RealMatrix;
public class MatrixRotator {
public static RealMatrix rotate90Degrees(RealMatrix matrix) {
int rows = matrix.getRowDimension();
int cols = matrix.getColumnDimension();
RealMatrix rotatedMatrix = new Array2DRowRealMatrix(cols, rows);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
rotatedMatrix.setEntry(j, rows - 1 - i, matrix.getEntry(i, j));
}
}
return rotatedMatrix;
}
public static void printMatrix(RealMatrix matrix) {
for (int i = 0; i < matrix.getRowDimension(); i++) {
for (int j = 0; j < matrix.getColumnDimension(); j++) {
System.out.printf("%6d", (int) matrix.getEntry(i, j));
}
System.out.println();
}
}
public static void main(String[] args) {
double[][] data = {
{0, 610, 703, 319, 90, 290, 219, 564},
{12, 0, 897, 165, 549, 786, 859, 303},
{505, 115, 0, 535, 445, 677, 639, 44},
{359, 366, 581, 0, 848, 322, 841, 165},
{500, 128, 653, 500, 0, 903, 789, 449},
{559, 93, 314, 176, 404, 0, 130, 964},
{55, 349, 2, 787, 622, 425, 0, 58},
{909, 447, 276, 860, 388, 624, 666, 0}
};
RealMatrix matrix = new Array2DRowRealMatrix(data);
System.out.println("Matriz original:");
printMatrix(matrix);
RealMatrix rotatedMatrix = rotate90Degrees(matrix);
System.out.println("\nMatriz rotada 90 grados:");
printMatrix(rotatedMatrix);
}
}
Resultado:
run:
Matriz original:
0 610 703 319 90 290 219 564
12 0 897 165 549 786 859 303
505 115 0 535 445 677 639 44
359 366 581 0 848 322 841 165
500 128 653 500 0 903 789 449
559 93 314 176 404 0 130 964
55 349 2 787 622 425 0 58
909 447 276 860 388 624 666 0
Matriz rotada 90 grados:
909 55 559 500 359 505 12 0
447 349 93 128 366 115 0 610
276 2 314 653 581 0 897 703
860 787 176 500 0 535 165 319
388 622 404 0 848 445 549 90
624 425 0 903 322 677 786 290
666 0 130 789 841 639 859 219
0 58 964 449 165 44 303 564
BUILD SUCCESSFUL (total time: 0 seconds)
jueves, 11 de julio de 2024
Conversor matriz de distancias a coordenadas cartesianas(MDS) usando librería "Apache Commons Math".
Este algoritmo implementa el algoritmo de Escalamiento Multidimensional (MDS) para transformar matrices de distancias en coordenadas cartesianas utilizando la librería "Apache Commons Math".
Requisitos:
- NetBeans IDE
- Apache Commons Math (versión 3.6.1)
Pasos:
1. Descarga la librería Apache Commons Math 3.6.1 desde:
https://archive.apache.org/dist/commons/math/binaries/
2. Busca y descarga el archivo "commons-math3-3.6.1-bin.zip".
3. En NetBeans, añadir la librería al proyecto.
Código Java (DistanceToCoordinates.java):
package distancetocoordinates;
import org.apache.commons.math3.linear.Array2DRowRealMatrix;
import org.apache.commons.math3.linear.EigenDecomposition;
import org.apache.commons.math3.linear.RealMatrix;
public class DistanceToCoordinates {
private final double[][] distanceMatrix;
private final int dimensions;
public DistanceToCoordinates(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.dimensions = distanceMatrix.length;
}
public double[][] calculateCoordinates() {
// Paso 1: Calcular la matriz B
double[][] B = calculateBMatrix();
// Paso 2: Realizar la descomposición en valores propios de B
EigenDecomposition eigen = new EigenDecomposition(new Array2DRowRealMatrix(B));
// Paso 3: Obtener los valores propios y vectores propios
double[] eigenvalues = eigen.getRealEigenvalues();
RealMatrix eigenvectors = eigen.getV();
// Paso 4: Ordenar los valores propios en orden descendente
Integer[] indices = new Integer[dimensions];
for (int i = 0; i < dimensions; i++) {
indices[i] = i;
}
java.util.Arrays.sort(indices, (a, b) -> Double.compare(eigenvalues[b], eigenvalues[a]));
// Paso 5: Calcular las coordenadas
double[][] coordinates = new double[dimensions][dimensions];
for (int i = 0; i < dimensions; i++) {
for (int j = 0; j < dimensions; j++) {
coordinates[i][j] = Math.sqrt(Math.max(0, eigenvalues[indices[j]])) * eigenvectors.getEntry(i, indices[j]);
}
}
return coordinates;
}
private double[][] calculateBMatrix() {
double[][] B = new double[dimensions][dimensions];
double[] rowMeans = new double[dimensions];
double totalMean = 0;
// Calcular los cuadrados de las distancias
for (int i = 0; i < dimensions; i++) {
for (int j = 0; j < dimensions; j++) {
B[i][j] = -0.5 * distanceMatrix[i][j] * distanceMatrix[i][j];
rowMeans[i] += B[i][j];
totalMean += B[i][j];
}
rowMeans[i] /= dimensions;
}
totalMean /= (dimensions * dimensions);
// Centrar la matriz B
for (int i = 0; i < dimensions; i++) {
for (int j = 0; j < dimensions; j++) {
B[i][j] = B[i][j] - rowMeans[i] - rowMeans[j] + totalMean;
}
}
return B;
}
public static void main(String[] args) {
double[][] distanceMatrix = {
{0, 3538196.0, 3735982.0, 6458578.0, 4011596.0, 1278244.0, 4456652.0, 7001752.0},
{3538196.0, 0, 6073624.0, 9765551.0, 5373577.0, 8563521.0, 9075418.0, 7378972.0},
{3735982.0, 6073624.0, 0, 4434730.0, 1077102.0, 1125242.0, 3435080.0, 2347484.0},
{6458578.0, 9765551.0, 4434730.0, 0, 7999311.0, 3946544.0, 1846094.0, 1283370.0},
{4011596.0, 5373577.0, 1077102.0, 7999311.0, 0, 8920411.0, 1777521.0, 7183199.0},
{1278244.0, 8563521.0, 1125242.0, 3946544.0, 8920411.0, 0, 6221466.0, 7883823.0},
{4456652.0, 9075418.0, 3435080.0, 1846094.0, 1777521.0, 6221466.0, 0, 2385324.0},
{7001752.0, 7378972.0, 2347484.0, 1283370.0, 7183199.0, 7883823.0, 2385324.0, 0}
};
DistanceToCoordinates calculator = new DistanceToCoordinates(distanceMatrix);
double[][] coordinates = calculator.calculateCoordinates();
// Imprimir las coordenadas
for (int i = 0; i < coordinates.length; i++) {
System.out.print("Nodo " + (char) ('A' + i) + ": [ ");
for (int j = 0; j < coordinates[i].length; j++) {
System.out.printf("%.4f ", coordinates[i][j]);
}
System.out.println("]");
}
}
}
Resultado:
run:
Nodo A: [ -2109176,7652 -2280795,2868 943542,6755 1167238,5398 -0,0000 -0,0000 -0,0000 0,0000 ]
Nodo B: [ -5501880,3926 -340732,2628 -2558730,8576 335704,8847 -0,0000 0,0000 0,0000 0,0000 ]
Nodo C: [ 100046,1854 -133636,2798 255465,7042 -1991154,7275 -0,0000 -0,0000 -0,0000 0,0000 ]
Nodo D: [ 4430934,9160 -101468,6811 -792915,6722 616290,8194 -0,0000 0,0000 -0,0000 0,0000 ]
Nodo E: [ -2944669,9418 2839449,1084 2485778,2633 -376992,5883 -0,0000 0,0000 -0,0000 -0,0000 ]
Nodo F: [ 1720031,9254 -4810714,6137 579380,6506 -443374,3002 -0,0000 -0,0000 0,0000 -0,0000 ]
Nodo G: [ 2087917,4093 2241964,4880 1969418,4176 812990,9949 -0,0000 -0,0000 0,0000 0,0000 ]
Nodo H: [ 2216796,6634 2585933,5278 -2881939,1813 -120703,6228 -0,0000 -0,0000 -0,0000 -0,0000 ]
BUILD SUCCESSFUL (total time: 0 seconds)
martes, 9 de julio de 2024
Conversor matriz de distancias a coordenadas cartesianas (MDS).
El algoritmo es conocido como Escalamiento Multidimensional(MDS) y puede ser utilizado para:
. Reconstrucción de coordenadas: A partir de las distancias entre puntos, reconstruye sus posiciones relativas en un espacio en coordenadas cartesianas.
. Visualización de datos: Permite representar en un espacio de menor dimensión (generalmente 2D o 3D) datos que originalmente están en un espacio de mayor dimensión.
Funcionamiento:
1. Entrada: El algoritmo toma como entrada las distancias entre cuatro puntos o nodos en un espacio tridimensional.
2. Proceso: Utiliza estas distancias para construir una matriz de distancias, la cual se transforma y se somete a una descomposición en valores singulares (SVD).
3. Salida: Produce las coordenadas cartesianas (x, y, z) de los cuatro puntos (en el espacio 3D).
Código Java (CalculadorCoordenadasMDS.java):
package calculadorcoordenadasmds;
public class CalculadorCoordenadasMDS {
public static void main(String[] args) {
// Distancias dadas entre los nodos
double d12 = 17;
double d13 = 40;
double d14 = 12;
double d23 = 64;
double d24 = 88;
double d34 = 12;
try {
double[][] coordinates = calculateCoordinates(d12, d13, d14, d23, d24, d34);
for (int i = 0; i < coordinates.length; i++) {
System.out.printf("Nodo %d: (%.4f, %.4f, %.4f)%n",
i + 1, coordinates[i][0], coordinates[i][1], coordinates[i][2]);
}
} catch (IllegalArgumentException e) {
System.out.println(e.getMessage());
}
}
public static double[][] calculateCoordinates(double d12, double d13, double d14, double d23, double d24, double d34) {
double[][] distances = {
{0, d12, d13, d14},
{d12, 0, d23, d24},
{d13, d23, 0, d34},
{d14, d24, d34, 0}
};
double[][] b = new double[4][4];
// Doble centrado de la matriz de distancias
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
b[i][j] = -0.5 * (distances[i][j] * distances[i][j]);
}
}
double[] rowMeans = new double[4];
double[] colMeans = new double[4];
double totalMean = 0.0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
rowMeans[i] += b[i][j];
colMeans[j] += b[i][j];
}
rowMeans[i] /= 4.0;
totalMean += rowMeans[i];
}
totalMean /= 4.0;
for (int i = 0; i < 4; i++) {
colMeans[i] /= 4.0;
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
b[i][j] += totalMean - rowMeans[i] - colMeans[j];
}
}
SVDResult svd = svd(b);
double[][] coordinates = new double[4][3];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
coordinates[i][j] = svd.u[i][j] * Math.sqrt(svd.s[j]);
}
}
return coordinates;
}
// Implementación simple de SVD
private static SVDResult svd(double[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
double[][] u = new double[m][m];
double[] s = new double[Math.min(m, n)];
double[][] v = new double[n][n];
// Implementación simplificada de SVD (no es una implementación completa)
// Esta implementación asume que la matriz es simétrica y positiva semidefinida
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
u[i][j] = matrix[i][j];
}
}
// Calculamos los valores propios (que serán nuestros valores singulares)
for (int i = 0; i < s.length; i++) {
double sum = 0;
for (int j = 0; j < n; j++) {
sum += matrix[i][j] * matrix[i][j];
}
s[i] = Math.sqrt(sum);
}
// Normalizamos las columnas de U
for (int j = 0; j < m; j++) {
double norm = 0;
for (int i = 0; i < m; i++) {
norm += u[i][j] * u[i][j];
}
norm = Math.sqrt(norm);
if (norm > 0) {
for (int i = 0; i < m; i++) {
u[i][j] /= norm;
}
}
}
return new SVDResult(u, s, v);
}
private static class SVDResult {
double[][] u;
double[] s;
double[][] v;
SVDResult(double[][] u, double[] s, double[][] v) {
this.u = u;
this.s = s;
this.v = v;
}
}
}
Resultado:
run:
Nodo 1: (-10,9518, 13,1281, -18,6443)
Nodo 2: (22,3223, 37,7579, -18,2671)
Nodo 3: (-20,6027, -11,8716, 15,7343)
Nodo 4: (9,2322, -39,0143, 21,1772)
BUILD SUCCESSFUL (total time: 0 seconds)