Wie kann ich wissen, ob alle Knoten in einem Diagramm besucht wurden, bevor der gewünschte Knoten erreicht wurde?

Question

Ich habe eine Wissensbasis dieser Art:

connect(a, b). 
connect(a, d). 
connect(a, e). 
connect(b, a). 
connect(b, c). 
... 

Mein Ziel ist es, einen Ursprung und ein Schicksal gegeben, auf einmal alle vorhandenen Knoten durchlaufen, bevor Sie den letzten Knoten erreicht.

Bisher ist das, was ich habe:

path(O, D, L):- 
    path(O, D, [O], L). 

path(D, D, _, [D]). 
path(O, D, A, [O|T]):- 
    connect(O, I), 
    \+ member(I, A), 
    path(I, D, [I|A], T). 

Um die Doppelverbindungen zu behandeln z.B. connect(a, b). connect(b, a). Ich benutze eine Liste, die jeden Knoten speichert, durch den ich gehe, und bevor ich in den Rekursionsaufruf gehe, stelle ich sicher, dass der Knoten, den ich gehe, nicht in diese Liste gehört.

Jetzt muss ich sicherstellen, dass ich durch alle vorhandenen Knoten gehe, bevor ich das letzte erreiche. Ich habe absolut keine Ahnung, wie ich das überhaupt angehen soll. Wie kann ich sicher sein, dass ich alle anderen Knoten besucht habe, bevor ich die letzte erreicht habe?

Answer 1

Sie haben ein Netzwerk als Liste von Kanten definiert. Eine schnelle und unsaubere Weise alle Knoten zu sammeln wäre, zum Beispiel:

findall(X, (connect(X, _) ; connect(_, X)), Xs), 
sort(Xs, Nodes) 

Dies wird zuerst alle „von“ s sammeln und „bis“ s Sie in Ihrem connect/2 aufgeführt haben, dann einen Satz entziffern davon durch das Sortieren und Entfernen von Duplikaten.

An diesem Punkt können Sie dieses Set nur mit dem Pfad vergleichen, den Sie gefunden haben (nachdem Sie es auch festgelegt haben).

Offensichtlich ist es wichtig, dass Ihr Prädikat fehlschlägt, es gibt keinen Pfad, der alle Knoten in dem von connect/2 definierten Netzwerk besucht.

Answer 2

Sie können es mit Ihrem eigenen Code (nicht mit findall) testen, indem Sie eine kleine Änderung vornehmen. Anstatt die Liste der besuchten Knoten wegzuwerfen, behalte sie. So ändern Pfad/4 Weg/5 wie folgt:

path(D, D, V, V, [D]). 
path(O, D, A, V, [O|T]):- 
    connect(O, I), 
    \+ member(I, A), 
    path(I, D, [I|A], V, T). 

Jetzt können Sie Pfad abfragen (a, c, [a], besuchte, Path) und testen, ob jeder Verbindungsknoten besteht, dass ist kein Mitglied von Besucht.