El algoritmo de Heap es un algoritmo de generación de permutaciones que utiliza una estructura de datos conocida como heap. La idea es generar todas las permutaciones de un conjunto de elementos en orden lexicográfico. Tiene una complejidad temporal de O(n!).
Código Java (HeapPermutation.java):
import java.util.Arrays;
public class HeapPermutation {
private static int[] elements = {1, 2, 3, 4};
public static void main(String[] args) {
heapPermutation(elements.length);
}
private static void heapPermutation(int size) {
if (size == 1) {
System.out.println(Arrays.toString(elements));
return;
}
for (int i = 0; i < size; i++) {
heapPermutation(size - 1);
if (size % 2 == 1) {
int temp = elements[0];
elements[0] = elements[size - 1];
elements[size - 1] = temp;
} else {
int temp = elements[i];
elements[i] = elements[size - 1];
elements[size - 1] = temp;
}
}
}
}
Resultado:
[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[4, 2, 3, 1]
[2, 4, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
[2, 3, 4, 1]
[3, 2, 4, 1]
[4, 1, 3, 2]
[1, 4, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[1, 3, 4, 2]
[3, 1, 4, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 2, 4, 3]
[2, 1, 4, 3]
sábado, 28 de enero de 2023
miércoles, 28 de diciembre de 2022
Conversión de Infijo a Postfijo usando pilas (v.4). Mejorar formato de entrada.
Se incorpora mejoras en la función de limpieza y formateo que permite ajustar la calidad y la precisión de la expresión de entrada, eliminando cualquier elemento innecesario y corrigiendo posibles errores de formateo.
Código Java (InfijoPostfijo.java):
package infijopostfijo;
import java.util.Scanner;
import java.util.Stack;
public class InfijoPostfijo {
public static void main(String[] args) {
// Declaración de las pilas
Stack<String> E = new Stack<>(); // Pila entrada
Stack<String> P = new Stack<>(); // Pila temporal para operadores
Stack<String> S = new Stack<>(); // Pila salida
// Entrada de datos
System.out.println("> Ingresa expresión algebraica a convertir:");
Scanner leer = new Scanner(System.in);
// Pasar expresión algebraica a la Pila de entrada (E)
String[] arrayInfix = formato(leer.nextLine()).split(" ");
for (int i = arrayInfix.length - 1; i >= 0; i--) {
E.push(arrayInfix[i]);
}
// Conversor Infijo a Postfijo
while (!E.isEmpty()) {
switch (prioridad(E.peek())) {
case 1 ->
P.push(E.pop());
case 2 -> {
while (!P.peek().equals("(")) {
S.push(P.pop());
}
P.pop();
E.pop();
}
case 3, 4 -> {
while (prioridad(P.peek()) >= prioridad(E.peek())) {
S.push(P.pop());
}
P.push(E.pop());
}
case 5 ->
P.push(E.pop());
default ->
S.push(E.pop());
}
}
// Mostrar resultado:
System.out.println("> Expresión en notación Postfija:\n" + S.toString().replaceAll("[\\]\\[,]", ""));
}
// Prioridad de los operadores
private static int prioridad(String op) {
return switch (op) {
case "^" -> 5;
case "*", "/" -> 4;
case "+", "-" -> 3;
case ")" -> 2;
case "(" -> 1;
default -> 99;
};
}
// Formato expresión algebraica
private static String formato(String expr) {
expr = expr.trim();
expr = expr.charAt(0) == '-' ? "0-" + expr.substring(1) : expr;
expr = expr.replaceAll("\\(-(\\d)", "(0-$1");
expr = expr.replaceAll("(\\d)\\(", "$1*(");
expr = expr.replaceAll("\\)(\\d)", ")*$1");
expr = expr.replaceAll("([\\+|\\-|\\*|\\/|\\(|\\)|\\^|])", " $1 ");
expr = expr.replaceAll("\\s+", " ");
return "( " + expr + " )";
}
}
Resultado:
run:
> Ingresa expresión algebraica a convertir:
-4(56-3+5)/2-(45+34)+(-23*(-52)6+2)-1
> Expresión en notación Postfija:
0 4 56 3 - 5 + * 2 / - 45 34 + - 0 23 0 52 - * 6 * - 2 + + 1 -
BUILD SUCCESSFUL (total time: 2 seconds)
martes, 27 de diciembre de 2022
Problema del viajante de comercio TSP (IV). Cálculo mediante método Vecino Cercano.
El algoritmo de vecino más cercano funciona de la siguiente manera:
.Se elige una ciudad de inicio.
.Se selecciona la ciudad más cercana a la ciudad actual, y se añade al camino.
.Se repite el proceso anterior hasta que se haya visitado todas las ciudades.
.Se regresa al lugar de origen para completar el ciclo.
El algoritmo de vecino más cercano es una forma rápida y sencilla de encontrar una solución para el TSP, pero no garantiza que sea la solución óptima. En general, el algoritmo tiende a dar buenos resultados para problemas pequeños, pero puede no ser tan efectivo para problemas más grandes.
Código (TSP_MainVecinoCercano.java):
package tsp_mainvecinocercano;
import java.util.ArrayList;
import java.util.List;
public class TSP_MainVecinoCercano {
public static void main(String[] args) {
int n = 12;
int[][] distances = new int[n][n];
// Generar distancias aleatorias
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) {
distances[i][j] = 0;
} else {
distances[i][j] = (int) (Math.random() * 999 + 1);
distances[j][i] = distances[i][j];
}
}
}
// Imprimir matriz de distancias
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%5d ", distances[i][j]);
}
System.out.println();
}
TSP_VecinoCercano tsp = new TSP_VecinoCercano(distances);
List<Integer> path = tsp.findOptimalPath();
// Pone nombre a los nodos siguiendo la secuencia del abcedario
List<String> nodeNames = new ArrayList<>();
for (int i = 0; i < n; i++) {
char letter = (char) ('A' + i);
nodeNames.add(String.valueOf(letter));
}
// Imprimir ruta y distancia recorrida
System.out.println("\n> Ruta:");
path.forEach(node -> {
System.out.print(nodeNames.get(node) + " ");
});
System.out.println("\n> La distancia total recorrida es:");
int totalDistance = 0;
for (int i = 0; i < path.size() - 1; i++) {
int node1 = path.get(i);
int node2 = path.get(i + 1);
totalDistance += distances[node1][node2];
}
System.out.println(totalDistance);
}
}
Código 2 (TSP_VecinoCercano.java):
package tsp_mainvecinocercano;
import java.util.ArrayList;
import java.util.List;
public class TSP_VecinoCercano {
private final int[][] distances;
public TSP_VecinoCercano(int[][] distances) {
this.distances = distances;
}
public List<Integer> findOptimalPath() {
List<Integer> path = new ArrayList<>();
path.add(0); // Empezamos en el nodo 0
int currentNode = 0;
for (int i = 0; i < distances.length - 1; i++) {
int minDistance = Integer.MAX_VALUE;
int nextNode = -1;
for (int j = 0; j < distances.length; j++) {
if (distances[currentNode][j] < minDistance && !path.contains(j)) {
minDistance = distances[currentNode][j];
nextNode = j;
}
}
path.add(nextNode);
currentNode = nextNode;
}
// Volvemos al nodo de origen
path.add(0);
return path;
}
}
Resultado:
run:
0 138 758 967 823 983 914 935 369 522 282 990
138 0 997 828 997 770 963 398 590 668 312 716
758 997 0 849 945 774 952 47 859 52 438 582
967 828 849 0 556 800 501 589 928 149 409 912
823 997 945 556 0 856 172 696 375 240 335 887
983 770 774 800 856 0 213 39 549 694 102 65
914 963 952 501 172 213 0 164 79 243 646 907
935 398 47 589 696 39 164 0 205 571 392 504
369 590 859 928 375 549 79 205 0 167 253 203
522 668 52 149 240 694 243 571 167 0 475 578
282 312 438 409 335 102 646 392 253 475 0 314
990 716 582 912 887 65 907 504 203 578 314 0
> Ruta:
A B K F H C J D G I L E A
> La distancia total recorrida es:
3332
BUILD SUCCESSFUL (total time: 0 seconds)
Suscribirse a:
Comentarios (Atom)