Breite-zuerst in Prolog

Question

Was ist die allgemeine Idee der Verwendung von Breitens zuerst über das Standard-Tiefensuchschema in Prolog?

Keine unendlichen Zweige?

Gibt es eine allgemeine Möglichkeit, in Prolog breath-first zu verwenden? Ich habe gegoogelt und ich habe nicht viele nützliche Informationen für einen Anfänger gefunden.

Answer 1

Der Vorteil von breath-first ist, dass Sie alle Lösungen finden. Mit der Tiefe können Sie zuerst in einem unendlichen Zweig stecken bleiben.

Der Nachteil ist, dass breath-first viel Speicher verwendet, daher wird es nicht allgemein zur Ausführung verwendet.

Wenn Sie es verwenden möchten, müssen Sie es explizit mit einer Art von Warteschlange implementieren.

Bearbeiten: Wenn Sie die Vorteile der Breitensuche ohne viel Speicher verwenden möchten, können Sie iterative Vertiefung verwenden. Dies ist die Tiefensuche mit einer Tiefenbindung, die Sie nacheinander erhöhen. Dies führt zu einer doppelten Berechnung, aber wenn Ihr Suchbereich keine langen linearen Abschnitte ohne Verzweigung aufweist, ist diese Duplizierung gering.

Answer 2

Da ist etwas, das ich als "Agendasuche" kennen gelernt habe. Während Sie den Baum (Daten, Beziehungen, Regeln, ...) durchlaufen, pflegen Sie eine "Agenda" (eine Liste), was als nächstes zu tun ist. Wenn Sie einen Knoten eingeben, setzen Sie seine Kinder auf die Tagesordnung und fahren dann mit dem ersten Element der Agenda fort, die Sie aufrufen. Auf diese Weise erhalten Sie, wenn Sie neue Elemente am Ende der Tagesordnung setzen, zuerst die Breite. Wenn Sie sie vor die Tagesordnung setzen, bekommen Sie zuerst Tiefe.

Es ist einfach mit Prolog zu implementieren.

EDIT: Ich könnte auch einen Implementierungshinweis hier geben. Dies ist eine sehr grundlegende Implementierung des Algorithmus zur Suche nach einer 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). 

Es externe Prädikate beruht doWithNode, die für die Aktion stehen Sie mit jedem Knoten ausgeführt werden sollen (zum Beispiel Knotendaten zu einem Suchbegriff vergleichen, Knoteninhalt, asf serialisiert.). Und getNodeChildren, die die Liste der untergeordneten Elemente des angegebenen Knotens an C binden wird (das heißt, dieses Prädikat kennt tatsächlich die Baumstruktur und wie man untergeordnete Knoten findet). Natürlich benötigt das Prädikat doWithNode möglicherweise zusätzliche Parameter, um seine Aufgabe zu erfüllen, was auch in der Argumentliste von agenda_search auftauchen würde.

Sie können es wie folgt aufrufen:

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

und

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

Ich habe auch ein bisschen Erklärung der Agenda Suche on this web page gefunden. Das Schöne an der Agenda-Suche ist, dass Sie einfach zwischen den beiden Varianten df und bf wechseln und mit den Ergebnissen spielen können. Der Algorithmus verhält sich recht gut im Gedächtnis, da die Agenda, die Knoten, die noch zu erforschen sind, nur einen (mehr oder weniger) kleinen Bruchteil von Knoten im Baum zu einem bestimmten Zeitpunkt erfassen (den sogenannten Rand).

Answer 3

Der Code für agenda_search sollte gut funktionieren. Aus Effizienzgründen sollten Sie eine andere Datenstruktur in Betracht ziehen. in der Tat wird in der ersten Breite die gesamte Liste der Knoten (T) von append (T, C, A) durchlaufen. Sie können zum Beispiel das Bibliotheksmodul (Warteschlangen) von SICStus verwenden. Die Breathth-First-Suche würde dann wie folgt aussehen (parametrisiert durch Prädikate start/1, das Nachfolgerprädikat s/2 und das Zielprädikatziel/1). Hinweis, ich habe auch eine Schleifenprüfung hinzugefügt.

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

(. Sie können auch den Pfad Komponente versuchen und ersetzen/ergänzen durch eine bessere Datenstruktur, zB AVL-Bäume) Ein Beispiel Problem wäre zu lösen:

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

Sie können auch Ersetzen Sie die Warteschlange durch eine Prioritätswarteschlange, und berechnen Sie die Priorität mithilfe einer heuristischen Funktion. Sie erhalten dann eine A * -Suche (die Tiefe emulieren kann - zuerst, Breite zuerst, beste zuerst, ...). Bratkos Buch (Logic Programming for Artificial Intelligence) sollte eine gute Quelle sein, um dieses Material zu lesen.