Búsqueda exhaustiva — Fuerza bruta

Al finalizar este tema

Podrás identificar situaciones en las que la búsqueda exhaustiva es adecuada y explorar sistemáticamente todos los casos posibles utilizando bucles, permutaciones y combinaciones.

El método más seguro

Si una contraseña consta de 4 dígitos numéricos, puedes encontrarla probando todos los valores desde 0000 hasta 9999. Esto es la búsqueda exhaustiva (fuerza bruta, búsqueda exhaustiva).

python

# Investigación exhaustiva de contraseñas numéricas de 4 dígitos
for code in range(10000):
    if check(code):
        print(f"Contraseña: {code:04d}")
        break

10 000 casos. Para una computadora, es cuestión de segundos.

La clave de la búsqueda exhaustiva: "Dado que no se omiten casos, la respuesta siempre se encuentra". Su mayor ventaja es que garantiza la precisión.

Cuándo usarlo

La búsqueda exhaustiva se utiliza cuando el número de casos es lo suficientemente pequeño.

text

Estándar basado en aproximadamente 100 millones (10^8) de operaciones por segundo:
  n ≤ 20     → 2^20 = aproximadamente 1 millón ✅
  n ≤ 10     → 10! = aproximadamente 3.6 millones ✅
  n ≤ 8      → 8! = 40,320 ✅
  n ≤ 25~30  → 2^30 = aproximadamente 1 mil millones ⚠️ Riesgo de tiempo de espera agotado

En las pruebas de código, si el tamaño de la entrada es pequeño (aproximadamente n ≤ 20), lo primero que se debe considerar es la búsqueda exhaustiva. Antes de implementar un algoritmo complejo, hay que verificar si no sería suficiente probar todas las posibilidades.

Patrón 1: Bucles anidados

Esta es la forma más básica:

python

# Encontrar pares cuya suma es target
def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Se prueban todas las combinaciones posibles. Tiene una complejidad de O(n²), pero es suficiente cuando n es pequeño.

Patrón 2: Permutación

Todos los casos en los que el orden es importante:

python

from itertools import permutations

# Todos los órdenes de disposición de [1, 2, 3]
for p in permutations([1, 2, 3]):
    print(p)
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)

El número de permutaciones de un conjunto de $n$ elementos es $n!$ . Por ejemplo: $3! = 6$ , $5! = 120$ , $10! = 3\,628\,800$ .

python

# El número más grande que se puede formar con tarjetas numéricas
cards = [3, 1, 4]
max_num = 0
for p in permutations(cards):
    num = int("".join(map(str, p)))
    max_num = max(max_num, num)

print(max_num)  # 431

Patrón 3 — Combinación

Todos los casos en los que el orden no es relevante:

python

from itertools import combinations

# Todas las formas de elegir 3 personas de 5
people = ["A", "B", "C", "D", "E"]
for team in combinations(people, 3):
    print(team)
# ('A', 'B', 'C')
# ('A', 'B', 'D')
# ('A', 'B', 'E')
# ... total de 10 combinaciones (5C3 = 10)

python

# Selecciona 2 elementos del menú dado para encontrar la combinación con la suma más baja
prices = {"ramen": 3500, "kimbap": 2500, "tteokbokki": 4000, "sundae": 3000}
items = list(prices.items())

cheapest = float('inf')
best_combo = None
for combo in combinations(items, 2):
    total = combo[0][1] + combo[1][1]
    if total < cheapest:
        cheapest = total
        best_combo = (combo[0][0], combo[1][0])

print(f"{best_combo}: {cheapest} won")  # ('kimbap', 'sundae'): 5500 won

Patrón 4 — Máscara de bits

Problema de subconjuntos en el que cada elemento se clasifica como "seleccionado" o "no seleccionado":

python

# El número de subconjuntos de n elementos es igual a 2^n
items = ["manzana", "plátano", "cereza"]
n = len(items)

for mask in range(1 << n):  # 0 ~ 2^n - 1
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(items[i])
    print(subset)

# []
# ['manzana']
# ['plátano']
# ['manzana', 'plátano']
# ['cereza']
# ['manzana', 'cereza']
# ['plátano', 'cereza']
# ['manzana', 'plátano', 'cereza']

1 << n es 2^n. Un bit determina si se incluye o no este elemento.

De la búsqueda exhaustiva a la optimización

Primero, se encuentra la respuesta correcta mediante una búsqueda exhaustiva; si el rendimiento es insuficiente, se optimiza:

Búsqueda exhaustiva	→	Técnica de optimización
Todos los pares (O(n²))	→	Mapa hash (O(n))
Todas las sumas parciales	→	Dos punteros, ventana deslizante
Todos los caminos	→	Programación dinámica (memoización)
Búsqueda exhaustiva	→	Poda

Orden para resolver problemas de pruebas de programación:

Escribir primero la solución exacta mediante búsqueda exhaustiva.
Si se produce un tiempo de ejecución excesivo, buscar patrones para optimizar.
Verificar si la solución optimizada produce la misma respuesta que la búsqueda exhaustiva.

Resumen clave

Método	Número de casos	Herramienta utilizada
Bucles anidados	O(n^k)	bucles `for`
Permutaciones	n!	`itertools.permutations`
Combinaciones	nCr	`itertools.combinations`
Subconjuntos	2^n	máscara de bits

Backtracking: búsqueda exhaustiva con poda

Es una técnica que, al determinar en la búsqueda exhaustiva que "esta dirección no puede llevar a una solución", retrocede sin continuar:

python

# Problema de las N-Reinas: colocar N reinas en un tablero de ajedrez de N×N sin que se ataquen entre sí
def solve_nqueens(n):
    solutions = []

    def backtrack(queens, row):
        if row == n:
            solutions.append(queens[:])
            return

        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)
                backtrack(queens, row + 1)
                queens.pop()  # deshacer (backtrack)

    def is_safe(queens, row, col):
        for r, c in enumerate(queens):
            if c == col or abs(r - row) == abs(c - col):
                return False
        return True

    backtrack([], 0)
    return solutions

print(len(solve_nqueens(8)))  # 92 soluciones posibles

En un tablero de ajedrez de 8×8, aunque existen aproximadamente 4300 millones de configuraciones posibles, la poda reduce el número de casos que se exploran realmente a unos pocos miles.

Elección entre recursión e iteración

python

# Recursión — natural para la exploración de estructuras de árbol
def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            paths.extend(find_all_paths(graph, node, end, path))
    return paths

# Bucle iterativo — adecuado para enumeración simple
for i in range(n):
    for j in range(i + 1, n):
        check(arr[i], arr[j])

Los bucles anidados se utilizan cuando la profundidad es fija, mientras que la recursión se utiliza cuando la profundidad es variable. Tenga en cuenta el límite de profundidad de recursión de Python (el valor predeterminado es 1000).

Consideraciones sobre el tiempo de ejecución

Para cumplir con los límites de tiempo en las pruebas de programación (generalmente entre 1 y 2 segundos), debe estimar el número de operaciones:

text

Referencia en Python (aproximado):
  10^6 operaciones → ~0.1 segundos
  10^7 operaciones → ~1 segundo
  10^8 operaciones → ~10 segundos (desbordamiento de tiempo)

python

# n=10 → 2^10 = 1,024 → búsqueda exhaustiva posible
# n=20 → 2^20 = 1,048,576 → posible pero ajustado
# n=30 → 2^30 = 1.073.741.824 → tiempo de espera agotado
# n! → si n=10 es 3.628.800, si n=12 es 479.001.600

Rango de n	Complejidad posible	Técnica
≤ 10	O(n!)	Búsqueda exhaustiva de permutaciones
≤ 20	O(2^n)	Conjuntos de subconjuntos / Máscara de bits
≤ 1.000	O(n²)	Bucles anidados
≤ 100.000	O(n log n)	Ordenación + búsqueda binaria
≤ 10.000.000	O(n)	Búsqueda lineal, tablas hash

Al observar el tamaño de la entrada y determinar primero qué complejidad es viable, se puede decidir si intentar una búsqueda exhaustiva o pasar directamente a la optimización.

La búsqueda exhaustiva no es un "método burdo". Es una línea base que garantiza la respuesta correcta y el punto de partida para algoritmos mejores.

BioPlayground

Búsqueda exhaustiva — Fuerza bruta

Búsqueda exhaustiva — Fuerza bruta

Al finalizar este tema

El método más seguro

Cuándo usarlo

Patrón 1: Bucles anidados

Patrón 2: Permutación

Patrón 3 — Combinación

Patrón 4 — Máscara de bits

De la búsqueda exhaustiva a la optimización

Resumen clave

Backtracking: búsqueda exhaustiva con poda

Elección entre recursión e iteración

Consideraciones sobre el tiempo de ejecución

💬 Preguntas y comentarios