31. Algoritmo A(estrella) con profundidad iterada (IDA(estrella))

Esta unidad presenta el Algoritmo A de Profundidad Iterada (IDA)**, una variante optimizada del A* diseñada específicamente para resolver el problema del consumo excesivo de memoria en espacios de búsqueda extensos.

---

Síntesis: Lo más importante de IDA*

El algoritmo IDA* combina la eficiencia en memoria de la búsqueda en profundidad con la optimalidad de A*. Sus pilares fundamentales son:

• Uso de Memoria: A diferencia del A* convencional, que almacena todos los nodos generados, IDA* solo mantiene la ruta actual en memoria. Su complejidad de memoria es lineal, $O(b \times d)$, donde $b$ es el factor de ramificación y $d$ la profundidad de la solución.

• Cota de Costo Dinámica: En lugar de usar una cota de profundidad fija (como en IDS), utiliza una cota de costo $f(n) = g(n) + h(n)$.

• Funcionamiento Iterativo:

  1. Comienza con una cota igual a la heurística del nodo inicial ($h(S_0)$).

  2. Realiza una búsqueda tipo profundidad ignorando cualquier nodo que supere la cota actual.

  3. Si no encuentra la meta, identifica el valor $f$ más pequeño de todos los nodos que superaron la cota y lo establece como la nueva cota para la siguiente iteración.

• Garantías: El algoritmo garantiza encontrar la solución óptima. Esto se debe a que la cota aumenta de forma mínima y controlada, asegurando que no se pase por alto ninguna ruta más corta.

• Optimización de Sucesores: Los sucesores de un nodo se ordenan mediante su valor $f$ antes de ser procesados para mejorar la velocidad de hallazgo dentro de una misma iteración.

---

Código del Algoritmo IDA* (Versión Iterativa)

Basado en la descripción lógica proporcionada en el texto , aquí tienes la representación del algoritmo:

def IDA_star(S0, es_meta, expandir, h):
    # 1. Establecer cota inicial [cite: 98-100]
    cota = h(S0)
    
    while True: # Ciclo de aumento de cota [cite: 101, 102]
        # Inicializar estructuras por iteración [cite: 103-107]
        agenda = [S0]        # Pila (LIFO) para profundidad [cite: 110]
        X = set()            # Conjunto para rastrear la ruta actual [cite: 107]
        minimo = float('inf') # Para calcular la siguiente cota [cite: 105, 106]
        
        while agenda: # Iterar sobre elementos en la agenda [cite: 109]
            n = agenda[-1] # Operación "Peek" (inspeccionar tope) [cite: 110-112]
            
            # Verificar condición de paro [cite: 113, 114]
            if es_meta(n):
                return recuperar_ruta(n) 
            
            if n not in X:
                X.add(n) # Agregar a la ruta [cite: 116, 117]
                
                # Obtener y ordenar sucesores por f(n) [cite: 117-119]
                sucesores = sorted(expandir(n), key=lambda s: s.g + h(s))
                
                for s in sucesores:
                    f_s = s.g + h(s)
                    # Verificar si está dentro de la cota y no en la ruta [cite: 121]
                    if f_s <= cota:
                        if s not in X:
                            agenda.append(s) # Agregar a agenda [cite: 122]
                    else:
                        # Actualizar el mínimo para la siguiente cota [cite: 123, 124]
                        if f_s < minimo:
                            minimo = f_s
            else:
                # Si ya se exploró o terminó su rama, hacer Pop [cite: 126]
                X.remove(agenda.pop())
        
        # Actualizar cota para la siguiente iteración [cite: 127]
        if minimo == float('inf'):
            return "Ninguna ruta encontrada" [cite: 128]
        cota = minimo

---

Algoritmo IDA

relatedInteligencia Artificial