Búsqueda y heurística

📐 Fundamento

Formalización de un problema de búsqueda:

class ProblemaBusqueda:
    def estado_inicial(self) -> Estado: ...
    def es_objetivo(self, estado: Estado) -> bool: ...
    def acciones(self, estado: Estado) -> list[Accion]: ...
    def resultado(self, estado: Estado, accion: Accion) -> Estado: ...
    def costo(self, estado: Estado, accion: Accion) -> float: ...

Ejemplo — La Esquina: repartidor de delivery

Estado inicial: local San Miguel Centro
Estado objetivo: casa del cliente (Colonia Las Flores)
Acciones: avanzar por cada calle disponible
Costo: distancia en km de cada segmento
Espacio de estados: el mapa de San Miguel (grafo de calles)

Criterios para comparar algoritmos:

b = factor de ramificación (acciones promedio por estado)
d = profundidad de la solución más superficial
m = profundidad máxima del árbol

📐 Fundamento

BFS — Breadth-First Search:

from collections import deque

def bfs(problema):
    nodo_inicial = Nodo(problema.estado_inicial())
    if problema.es_objetivo(nodo_inicial.estado):
        return nodo_inicial
    
    frontera = deque([nodo_inicial])  # cola FIFO
    explorados = set()
    
    while frontera:
        nodo = frontera.popleft()
        explorados.add(nodo.estado)
        
        for accion in problema.acciones(nodo.estado):
            hijo = expandir(problema, nodo, accion)
            if hijo.estado not in explorados and hijo not in frontera:
                if problema.es_objetivo(hijo.estado):
                    return hijo  # solución encontrada
                frontera.append(hijo)
    
    return None  # sin solución

# Propiedades:
# Completitud: Sí (si b y d son finitos)
# Optimalidad: Sí (si todos los costos son iguales)
# Tiempo: O(b^d)
# Espacio: O(b^d) — guarda todos los nodos en la frontera

DFS — Depth-First Search:

def dfs(problema):
    frontera = [Nodo(problema.estado_inicial())]  # pila LIFO
    explorados = set()
    
    while frontera:
        nodo = frontera.pop()  # toma el último
        if problema.es_objetivo(nodo.estado):
            return nodo
        explorados.add(nodo.estado)
        for accion in problema.acciones(nodo.estado):
            hijo = expandir(problema, nodo, accion)
            if hijo.estado not in explorados:
                frontera.append(hijo)
    return None

# Propiedades:
# Completitud: No (puede perderse en ramas infinitas)
# Optimalidad: No
# Tiempo: O(b^m)
# Espacio: O(b*m) — solo guarda el camino actual

Comparación:

UCS = Uniform Cost Search: BFS pero expandiendo el nodo de menor costo acumulado.

📐 Fundamento

Algoritmo A:*

import heapq

def a_star(problema, heuristica):
    nodo_inicial = Nodo(problema.estado_inicial(), g=0)
    frontera = [(0, nodo_inicial)]  # (f, nodo) — cola de prioridad
    explorados = {}  # estado → costo g conocido
    
    while frontera:
        f, nodo = heapq.heappop(frontera)
        
        if problema.es_objetivo(nodo.estado):
            return reconstruir_camino(nodo)
        
        if nodo.estado in explorados and explorados[nodo.estado] <= nodo.g:
            continue  # ya encontramos un camino mejor
        
        explorados[nodo.estado] = nodo.g
        
        for accion in problema.acciones(nodo.estado):
            hijo = expandir(problema, nodo, accion)
            h = heuristica(hijo.estado)
            f_hijo = hijo.g + h
            heapq.heappush(frontera, (f_hijo, hijo))
    
    return None

# Propiedades (si h es admisible):
# Completitud: Sí
# Optimalidad: Sí
# Tiempo: Depende de la heurística
# Espacio: O(b^d) en el peor caso

Heurística admisible: nunca sobreestima el costo real.

donde $h^$(n)h∗(n) es el costo real al objetivo. Si sobreestima, A puede no encontrar la solución óptima.

Heurística consistente (monótona):

Para cada nodo n y sucesor n'. Garantiza que A* nunca necesita revisitar nodos.

Ejemplos de heurísticas:

Efectividad de la heurística — factor de ramificación efectivo (b):*

Cuanto más cerca esté b* de 1, más eficiente es la heurística. Una heurística perfecta (h = h*) tiene b* = 1 — nunca explora nodos innecesarios.

📐 Fundamento

def hill_climbing(problema, heuristica_maximizar):
    estado = problema.estado_inicial()
    
    while True:
        vecinos = problema.acciones(estado)
        mejor_vecino = max(vecinos, key=lambda a: heuristica_maximizar(
            problema.resultado(estado, a)
        ))
        
        if heuristica_maximizar(mejor_vecino) <= heuristica_maximizar(estado):
            return estado  # máximo local encontrado
        
        estado = mejor_vecino

# Problema: se queda en máximos locales, mesetas, o crestas
# Solución: Random restart — correr hill climbing desde múltiples puntos iniciales

Variantes:

• Simulated Annealing: Acepta movimientos "hacia abajo" con probabilidad decreciente. Puede escapar de máximos locales.
• Algoritmos genéticos: Poblaciones de soluciones que se combinan y mutan. Buenos para espacios de búsqueda muy grandes.