Algoritmos de fuerza-
bruta
Características de los algoritmos de
fuerza bruta
• Exploración exhaustiva: Analizan todas las posibles combinaciones o
soluciones para encontrar la correcta.
• Simplicidad: Generalmente, son fáciles de diseñar y entender, ya que
no requieren técnicas complejas.
• Costo computacional: Son ineficientes para problemas grandes, ya
que su complejidad tiende a ser alta dependiendo del problema.
• Uso como punto de referencia: A veces se utilizan como referencia
para comparar con otros algoritmos más eficientes.
Ventajas:
• Fácil de implementar: No requiere técnicas avanzadas o matemáticas
complejas.
• Generalidad: Puede aplicarse a una amplia variedad de problemas sin
modificaciones significativas.
Desventajas:
• Ineficiencia: Consume mucho tiempo y recursos cuando el tamaño del
problema es grande.
• Escalabilidad: No escala bien con el tamaño del problema, ya que el número
de operaciones aumenta exponencialmente o factorialmente.
• Búsqueda lineal: Es un ejemplo típico, donde se busca un elemento en
una lista recorriendo cada elemento de la lista uno por uno hasta
encontrar el que se busca.
• Problema del viajero (TSP): El enfoque de fuerza bruta consiste en
generar todas las permutaciones posibles de las ciudades y calcular la
longitud del recorrido para cada una de ellas, eligiendo finalmente la
más corta.
• Multiplicación de matrices: El algoritmo de fuerza bruta para la
multiplicación de matrices utiliza el enfoque clásico que itera a través de
cada fila de la primera matriz y cada columna de la segunda,
multiplicando los elementos y sumando los productos.
• Subconjuntos de suma: Para el problema de encontrar subconjuntos
cuya suma sea igual a un valor dado, el enfoque de fuerza bruta
probaría todos los subconjuntos posibles.
• Pongamos un ejemplo sencillo, el problema de descifrar un password.
Para simplificar, supongamos que se tiene un password numérico
secreto de 4 cifras que queremos descubrir. Para cada cifra tenemos
10 dígitos posibles (0…9), lo que daría una cantidad de 10*10*10*10
= 10^4=10000 mil posibilidades, o candidatos para comparar contra el
password dado (que vale decir, es muy inseguro).
• Si se consideran 8 caracteres para la longitud del password, y se
admite además de los dígitos numéricos, 28 letras del alfabeto, la
cantidad de posibilidades aumentaría a 38^8 = 4347792138496.
public class BusquedaLineal { public class MochilaFuerzaBruta {
public static int buscar(int[] arreglo, int valorBuscado) { public static int mochila(int[] pesos, int[] valores, int capacidad, int n) {
for (int i = 0; i < arreglo.length; i++) { if (n == 0 || capacidad == 0) {
return 0;
if (arreglo[i] == valorBuscado) {
}
return i; // Retornar el índice donde se encontró if (pesos[n - 1] > capacidad) {
} return mochila(pesos, valores, capacidad, n - 1);
} else {
} return Math.max(valores[n - 1] + mochila(pesos, valores,
return -1; // Si no se encuentra capacidad - pesos[n - 1], n - 1),
mochila(pesos, valores, capacidad, n - 1));
}
}
}
public static void main(String[] args) {
public static void main(String[] args) {
int[] arreglo = {3, 7, 1, 9, 5}; int[] valores = {60, 100, 120};
int valor = 9; int[] pesos = {10, 20, 30};
int capacidad = 50;
int indice = buscar(arreglo, valor); int n = valores.length;
System.out.println("El valor " + valor + " está en el System.out.println("El valor máximo que se puede llevar es: " +
índice: " + indice); mochila(pesos, valores, capacidad, n));
}
}
}
}
public class MultiplicacionMatrices {
public static void main(String[] args) {
int[][] A = { {1, 2}, {3, 4} };
int[][] B = { {2, 0}, {1, 2} };
int[][] resultado = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
resultado[i][j] = 0;
for (int k = 0; k < 2; k++) {
resultado[i][j] += A[i][k] * B[k][j];
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
System.out.print(resultado[i][j] + " ");
}
System.out.println();
}
}
}
public class SumaDosNumeros {
public static void buscarSuma(int[] arreglo, int sumaObjetivo) {
int n = arreglo.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arreglo[i] + arreglo[j] == sumaObjetivo) {
System.out.println("Números encontrados: " + arreglo[i] + " y " + arreglo[j]);
return;
}
}
}
System.out.println("No se encontraron números que sumen " + sumaObjetivo);
}
public static void main(String[] args) {
int[] arreglo = {2, 4, 3, 5, 7, 8};
int sumaObjetivo = 10;
buscarSuma(arreglo, sumaObjetivo);
}
}
import java.util.ArrayList;
import java.util.List;
public class SubconjuntosFuerzaBruta {
public static List<List<Integer>> generarSubconjuntos(int[] conjunto) {
List<List<Integer>> subconjuntos = new ArrayList<>();
int n = conjunto.length;
int totalSubconjuntos = 1 << n; // 2^n subconjuntos
for (int i = 0; i < totalSubconjuntos; i++) {
List<Integer> subconjunto = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
subconjunto.add(conjunto[j]);
}
public static void main(String[] args) {
}
int[] conjunto = {1, 2, 3};
subconjuntos.add(subconjunto);
List<List<Integer>> subconjuntos = generarSubconjuntos(conjunto);
}
System.out.println("Subconjuntos: " + subconjuntos);
return subconjuntos;
}
}
}
int[][] tablero = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
La fuerza totalmente bruta
La fuerza un poco menos bruta
distancias = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
• Salida esperada: El recorrido más corto y la distancia total.
Algoritmo de fuerza bruta: Generar todas las posibles permutaciones
de las ciudades y calcular la distancia para cada permutación. Elegir la
que tenga la distancia mínima.
Encontrar pares que sumen a un valor específico
Problema: Dada una lista de enteros, encuentra todos los pares de
números cuya suma sea igual a un valor dado.
Entrada: Lista: [1, 5, 7, -1, 5], Suma objetivo: 6, Salida esperada: Pares
[(1, 5), (7, -1), (1, 5)]
Algoritmo de fuerza bruta: Comparar cada par de elementos en la lista
para verificar si su suma es igual al valor objetivo.
Encontrar todos los subconjuntos de un conjunto
Problema: Dado un conjunto de números, encuentra todos sus
subconjuntos.
Entrada: Conjunto: {1, 2, 3}, Salida esperada: Subconjuntos [{}, {1}, {2},
{3}, {1,2}, {1,3}, {2,3}, {1,2,3}]
Algoritmo de fuerza bruta: Generar todas las combinaciones posibles
de los elementos del conjunto.
Problema de suma de subconjuntos (Subset Sum Problem)
Problema: Dado un conjunto de números enteros, encuentra si existe un
subconjunto cuya suma sea igual a un valor objetivo.
Entrada: Conjunto: [3, 34, 4, 12, 5, 2], Suma objetivo: 9, Salida esperada:
True (porque el subconjunto [4, 5] suma 9).
Algoritmo de fuerza bruta: Generar todos los subconjuntos posibles y
verificar si alguno tiene una suma igual al objetivo.
Cesar - 4
Alfabeto original:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
Alfabeto desplazado en 4 posiciones:
E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A, B, C, D
Ejemplo 1:
Texto original: "HOLA"
Aplicamos el desplazamiento de 4 posiciones:
H→L
O→S
L→P
A→E
Texto cifrado: "LSPÉ"
César - 9
Alfabeto original:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
Alfabeto desplazado en 9 posiciones:
J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A, B, C, D, E, F, G, H, I
Ejemplo 1:
Texto original: "HOLA"
Aplicamos el desplazamiento de 9 posiciones:
H→Q
O→X
L→U
A→J
Texto cifrado: "QXUJ"
ROT5 Números originales:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Números desplazados con ROT5:
5, 6, 7, 8, 9, 0, 1, 2, 3, 4
Ejemplo 1:
Número original: "1234"
Aplicamos el desplazamiento ROT5:
1→6
2→7
3→8
4→9
Número cifrado: "6789"
ROT13 Alfabeto original:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
Alfabeto desplazado con ROT13:
N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A, B, C, D, E, F, G, H, I, J, K, L, M
Ejemplo 1:
Texto original: "HOLA"
Aplicamos el desplazamiento de 13 posiciones:
H→U
O→B
L→Y
A→N
Texto cifrado: "UBYN"
ROT47
• Caracteres que abarca ROT47: Desde el carácter 33 ("!") hasta el 126
("~") en la tabla ASCII.
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJ
KLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr
stuvwxyz{|}~
ROT47 Ejemplo 1:
Texto original: "Hello World!"
Aplicamos el desplazamiento ROT47:
•H → w
•e → 6
•l → @
•l → @
•o → C
•(espacio) → o
•W → 2
•o → C
•r → D
•l → @
•d → 5
•! → P
Texto cifrado: "w6@@Co2CD@5P"
Cifrado de Vigenère
Pasos:
• Texto original: El mensaje que deseas cifrar.
• Clave: Una palabra o frase que se repite para igualar la longitud del
texto original.
• Cifrado: Se suma la posición de cada letra del texto original con la
posición correspondiente de la letra en la clave, ambas según su
posición en el alfabeto.
Cifrado
de Texto original: "ATAQUE“, Clave: "CLAVE" (se repite para cubrir todo el texto)
Texto: A T A Q U E
Vigenère Clave: C L A V E C
Convierte cada letra a su posición en el alfabeto (A=0, B=1, C=2, ..., Z=25):
Texto: 0, 19, 0, 16, 20, 4
Clave: 2, 11, 0, 21, 4, 2
Suma los valores correspondientes de texto y clave (mod 26):
(0 + 2) % 26 = 2 (C)
(19 + 11) % 26 = 4 (E)
(0 + 0) % 26 = 0 (A)
(16 + 21) % 26 = 11 (L)
(20 + 4) % 26 = 24 (Y)
(4 + 2) % 26 = 6 (G)
El texto cifrado es: "CEALYG"
Cifrado
de Proceso inverso (descifrado):
Ejemplo de descifrado de "CEALYG" con clave "CLAVEC":
Vigenère
Convierte las letras cifradas y la clave a posiciones numéricas:
Texto cifrado: 2, 4, 0, 11, 24, 6
Clave: 2, 11, 0, 21, 4, 2
Resta las posiciones de las letras de la clave al texto cifrado (mod 26):
(2 - 2) % 26 = 0 (A)
(4 - 11) % 26 = 19 (T)
(0 - 0) % 26 = 0 (A)
(11 - 21) % 26 = 16 (Q)
(24 - 4) % 26 = 20 (U)
(6 - 2) % 26 = 4 (E)
El texto original es: "ATAQUE"
