Búsqueda recursiva en la primera mejor coincidencia

Algoritmos RPPNS
para buscar en grafos
Lleva el nombre de Buscar por primera mejor coincidencia
Autor Richard E. Korf [d]
Estructura de datos grafico
peor momento

Recursive Best -First Search (RBFS ) es un algoritmo recursivo simple que intenta imitar el trabajo de una búsqueda estándar de primera mejor coincidencia, perousandosolo espacio lineal  .

Disposiciones generales

Un ejemplo de implementación del algoritmo en pseudocódigo

función Recursive-Best-First-Search (problema) devuelve el resultado de la solución o falla del indicador de falla RBFS( problema , Make-Node(Initial-State[ problema ]), ∞) función RBFS (problema, nodo, f_limit) devuelve el resultado de la solución o el indicador de falla y el nuevo límite de costo f f_limit si Goal-Test[ problema ](Estado[ nodo ]) entonces devolver nodos sucesores ← Expand( nodo , problema ) si el conjunto de nodos sucesores está vacío entonces devolver falla, ∞ para cada s en sucesores do f[s] ← max ( g (s)+h(s) , f[ nodo ] ) repetir mejor ← el nodo con el valor f más pequeño en el conjunto de sucesores si f[mejor] > f_limit luego devuelve falla , f[ mejor ] alternativa ← del segundo al valor f más bajo en el conjunto de sucesores resultado, f[mejor] ← RBFS(problema, mejor, min{f_limit, alternativa)) si el resultado ≠ falla , devuelve el resultado

Tiene una estructura similar a la búsqueda primero en profundidad recursiva , pero en lugar de recorrer infinitamente la ruta actual, este algoritmo controla el valor f de la mejor ruta alternativa disponible de cualquier ancestro del nodo actual. Si el nodo actual excede el límite dado, entonces la etapa actual de la recursividad finaliza y la recursividad continúa a lo largo de una ruta alternativa. Después de la terminación de esta etapa de recursividad en el algoritmo RPPN , el valor f de cada nodo a lo largo de la ruta dada se reemplaza por el mejor valor f de su nodo hijo. Debido a esto, el valor f del mejor nodo hoja del subárbol olvidado se recuerda en el algoritmo RPPN y, por lo tanto, en algún momento siguiente, se puede tomar la decisión de expandir este subárbol nuevamente [1] .

Ventajas y desventajas

El algoritmo RPPNS es un poco más eficiente que IDA* , pero aún tiene la desventaja de regenerar nodos con demasiada frecuencia [2] . Estos cambios de decisión se producen porque cada vez que se despliega la mejor ruta actual, existe una buena posibilidad de que su valor f aumente, ya que la función h suele volverse menos optimista a medida que se despliegan los nodos más cercanos al objetivo. Una vez que ocurre esta situación, especialmente en espacios de búsqueda grandes, la ruta que fue la segunda mejor puede convertirse en la mejor ruta, por lo que el algoritmo de búsqueda debe realizar un retroceso para seguirla. Cada cambio de decisión corresponde a una iteración del algoritmo IDA* y puede requerir muchas reexpansiones de nodos olvidados para reproducir la mejor ruta y expandir la ruta a un nodo más.

Al igual que el algoritmo de búsqueda A* , RPPN es un algoritmo óptimo si la función heurística h(n) es admisible. Su complejidad espacial es 0(bd) , pero es bastante difícil caracterizar la complejidad temporal : depende tanto de la precisión de la función heurística como de la frecuencia con la que cambia la mejor ruta a medida que se implementan los nodos. Tanto el algoritmo IDA* como el algoritmo RPPN son propensos a un aumento exponencial potencial de la complejidad asociada con las búsquedas de gráficos, ya que estos algoritmos no pueden detectar la presencia de estados repetidos que no sean los de la ruta actual. Por lo tanto, estos algoritmos pueden explorar repetidamente el mismo estado.

Los algoritmos IDA* y RPPNS tienen la desventaja de que utilizan muy poca memoria. Entre iteraciones, el algoritmo IDA* guarda solo un número, el límite de costo f actual . El algoritmo RPPN almacena más información en la memoria, pero la cantidad de memoria utilizada se mide solo por el valor de 0 (bd) : incluso si hubiera más memoria disponible, el algoritmo RPPN no puede usarla.

Notas

  1. ↑ La sección Aplicación no está completamente escrita en el artículo original, por lo que no tiene sentido incluirla en este artículo todavía.
  2. ↑ Debería haber un fragmento aquí

    En el ejemplo que se muestra en la fig. 1, 2 y 3, el algoritmo RPPNS primero sigue el camino a través del nodo RimnicuVilcea , luego “cambia de opinión” e intenta pasar por el nodo Fagaras , después de eso regresa a la solución previamente rechazada,

    pero se refiere a una sección de Aplicación inconclusa en el artículo original.

Literatura

 Algoritmos de búsqueda de gráficos
Métodos no informados
Métodos informados
Atajos
Árbol de expansión mínimo
Otro