Breadth-First in Prolog

Question

¿Cuál es la idea general de usar primero el ancho sobre el esquema de búsqueda de profundidad predeterminado en Prolog?

¿No está tomando infinitas ramas?

¿Hay alguna forma general de usar ancho de primera en Prolog? He estado buscando en Google y no encontré demasiada información útil para un novato.

Answer 1

La ventaja de la amplitud es que encontrará todas las soluciones. Con la profundidad primero, puedes quedarte atrapado en una rama infinita.

La desventaja es que primero utiliza una gran cantidad de memoria, por lo tanto, no se usa generalmente para la ejecución.

Si desea utilizarlo deberá implementarlo explícitamente con algún tipo de cola.

Edit: Si quiere tener las ventajas de la búsqueda de ancho sin utilizar mucha memoria, puede utilizar la profundización iterativa. Esta es una búsqueda en profundidad con un límite de profundidad, que aumenta sucesivamente. Esto ocasiona algunos cálculos duplicados, pero si su espacio de búsqueda no tiene largos tramos lineales sin ramificación, esta duplicación es pequeña.

Answer 2

Hay algo que llegué a saber como "búsqueda de agenda". Mientras recorre el árbol (de datos, relaciones, reglas, ...) mantiene una "agenda" (una lista) de qué hacer a continuación. Cuando ingresa a un nodo, coloca sus hijos en la agenda y luego continúa con el primer elemento de la agenda, que muestra. De esta manera, si coloca nuevos elementos al final de la agenda, obtiene la amplitud primero. Si los pones delante de la agenda, obtienes primero la profundidad.

Es fácil de implementar con Prolog.

EDITAR: También podría dar una sugerencia de implementación aquí. Esta es una implementación muy básica del algoritmo de búsqueda de agenda.

agenda_search([N|T],Mode):- 
    doWithNode(N),   % do whatever you do the searching for 
    getNodeChildren(N,C), 
    (Mode=bf ->    % bf or df (depth-first) 
     append(T,C,A); 
     append(C,T,A)), 
    agenda_search(A,Mode). 

Se basa en predicados externos doWithNode que representa la acción que desea realizar con cada nodo (por ejemplo, comparar datos de nodo a un término de búsqueda, serializar contenido del nodo, ASF.). Y getNodeChildren que enlazará la lista de hijos del nodo dado al C (es decir, este predicado realmente conoce la estructura del árbol y cómo encontrar nodos secundarios). Por supuesto, el predicado doWithNode puede necesitar parámetros adicionales para hacer su trabajo, que también aparecería en la lista de argumentos de agenda_search.

Puede invocar así:

agenda_search([RootNode], bf) % for breadth-first search 

y

agenda_search([RootNode], df) % for depth-first search 

También he encontrado un poco de explicación de la búsqueda on this web page orden del día. Lo bueno de la búsqueda de agenda es que puedes cambiar fácilmente entre las dos variantes df y bf y jugar con los resultados. El algoritmo se comporta bien desde el punto de vista de la memoria, ya que la agenda, los nodos que aún deben explorarse, solo captura una (más o menos) pequeña fracción de nodos en el árbol en cualquier momento (el denominado margen).

Answer 3

El código para agenda_search debería funcionar bien. Para mayor eficiencia, es posible que desee considerar el uso de otra estructura de datos; de hecho, en el modo de amplitud primero, la lista completa de nodos (T) será atravesada por append (T, C, A). Podría, por ejemplo, usar el módulo de biblioteca (colas) de SICStus. Breadth-First search tendría el siguiente aspecto (parametrizado por los predicados start/1, el predicado sucesor s/2 y el meta predicate goal/1). Tenga en cuenta que también he agregado la verificación de bucles.

 
bfs(Res) :- start(Start), empty_queue(EQ), 
    queue_append(EQ,[e(Start,[])],Q1), 
    bfs1(Q1,Res). 

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue), 
    bfs2(Next,Path,NQ,Res). 

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res). 
bfs2(H,Path,NQ,Res) :- 
       findall(e(Succ,[H|Path]), 
         (s(H,Succ),\+ member(Succ,Path)),AllSuccs), 
       queue_append(NQ,AllSuccs,NewQueue), 
       bfs1(NewQueue,Res). 

(. También puede probar y sustituir/complementar el componente de trazado por una mejor estructura de datos; por ejemplo, AVL-árboles) Un ejemplo de problema a resolver sería:

 
start(env(0,0)). 
s(env(X,Y),env(X1,Y)) :- X1 is X+1. 
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1. 
goal(env(3,3)). 

También puede reemplace la cola por una cola de prioridad y calcule la prioridad usando una función heurística. Luego obtienes A * búsqueda (que puede emular la profundidad primero, ancho primero, mejor primero ...). El libro de Bratko (Programación Lógica para la Inteligencia Artificial) debería ser una buena fuente para leer este material.