Breadth-first in Prolog

Question

Qual è l'idea generale di utilizzare in ampiezza sopra lo schema di ricerca in profondità prima di default in Prolog?

Non prendere infiniti rami?

C'è un modo generale di utilizzare in ampiezza in Prolog? Sono stato googling in giro e non ho trovato troppe informazioni utili per un novizio.

Answer 1

Il vantaggio di ampiezza è che troverete tutte le soluzioni. Con in profondità si può diventare bloccato in un ramo infinito.

Lo svantaggio è che in ampiezza utilizza molta memoria, quindi non è utilizzato generalmente per l'esecuzione.

Se si desidera utilizzarlo è necessario per la sua attuazione in modo esplicito con qualche tipo di coda.

Modifica Se si vuole avere i vantaggi di ricerca in ampiezza senza utilizzare quantità di memoria è possibile utilizzare approfondimento iterativo. Si tratta di ricerca in profondità con una profondità-bound, che si aumenta successivamente. Questo fa sì che qualche calcolo duplicato, ma se il vostro spazio di ricerca non ha tratti lineari lunghi senza ramificazione allora questa duplicazione è piccolo.

Answer 2

C'è qualcosa che ho avuto modo di conoscere come " Ricerca agenda ". Mentre attraversa l'albero (di dati, relazioni, regole, ...) si mantiene un "agenda" (una lista) di cosa fare dopo. Quando si entra in un nodo si mette i suoi figli all'ordine del giorno, e poi continuare con il primo elemento del programma, che si pop. In questo modo, se si mette i nuovi elementi alla fine dell'ordine del giorno, si ottiene in ampiezza. Se li metti di fronte all'ordine del giorno, si ottiene in profondità.

E 'facile da implementare con Prolog.

EDIT: mi potrebbe anche dare un suggerimento implementazione qui. Si tratta di un'implementazione molto di base dell'algoritmo dell'agenda di ricerca.

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).

Si basa su predicati doWithNode esterna che si distingue per l'azione che si desidera eseguire con ogni nodo (ad esempio confrontare i dati dei nodi ad un termine di ricerca, serializzare il contenuto del nodo, ASF.). E getNodeChildren che legherà la lista dei figli del nodo dato a C (cioè questo predicato in realtà conosce la struttura ad albero e come trovare i figli). Naturalmente il predicato doWithNode potrebbe aver bisogno di parametri aggiuntivi per fare il suo lavoro, che sarebbe anche apparire nella lista degli argomenti di agenda_search.

È possibile richiamare in questo modo:

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

e

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

Inoltre ho trovato un po 'di spiegazione della ricerca dell'agenda in questa pagina web . La cosa bella con la ricerca ordine del giorno è che si può passare facilmente tra le due varianti df e bf e giocare con i risultati. L'algoritmo è abbastanza ben comportata-memory-saggio, come l'ordine del giorno, i nodi ancora da esplorare, coglie solo una piccola parte (più o meno) di nodi dell'albero in qualsiasi momento (la cosiddetta frangia).

Answer 3

Il codice per agenda_search dovrebbe funzionare bene. Per l'efficienza si potrebbe desiderare di considerare l'utilizzo di un altro datastructure; infatti, nel modo in ampiezza l'intero elenco di nodi (T) sarà attraversato da accodamento (T, C, A). Si potrebbe per esempio utilizzare il modulo di libreria (code) da SICStus. Breadth-first ricerca sarebbe poi apparire come segue (parametrizzato da predicati start / 1, il successore predicato s / 2 e l'obiettivo predicato di obiettivo / 1). Nota, ho aggiunto anche il controllo del ciclo.

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).

(Si potrebbe anche provare e sostituire / integrare il componente del percorso da un datastructure migliore;. Ad esempio, AVL-alberi) Un problema da risolvere ad esempio potrebbe essere:

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)).

È anche possibile sostituire la coda da una coda di priorità, e calcolare la priorità utilizzando una funzione euristica. Si raggiunge quindi Una ricerca * (che può emulare in profondità, ampiezza, best-first, ...). Il libro di Bratko (Programmazione Logica per l'Intelligenza Artificiale) dovrebbe essere buona fonte di leggere questo materiale.