Erreichbarkeitsbeschränkung in SWI/CLP(FD)

Question

Ich versuche, diese Form eines gerichteten Graphen zu bestimmen, indem ich Einschränkungen für das Vorhandensein von Knoten und Bögen, z. B. einer binären Variablen, löse V1V2 Ist 1 wenn es einen Bogen vom Knoten gibt V1 Zu V2.Ich möchte die Erreichbarkeitsbeschränkung ausdrücken (oder alternativ einen transitiven Abschluss finden), z. B. um zu verlangen, dass der Graph verbunden ist oder dass es einen Pfad von einem gegebenen Knoten zu einem anderen gegebenen Knoten gibt.

Ich habe gesehen, dass SICStus Prolog hat fd_closure für diesen Zweck, aber ich konnte nichts Ähnliches in SWI Prolog finden.Sollte ich es benutzen CHR?Ich habe mir die Beispiele für die Bogen-/Pfad-Konsistenz angesehen, bin mir aber nicht sicher, ob ich in die richtige Richtung schaue.

Answer 1

SICStus' fd_closure/2 ist dem von SWI-Prolog sehr ähnlich term_attvars/2.Sie erhalten alle Variablen, die transitiv über Attribute erreicht werden können (und CLP(FD) von SWI verwendet Attribute zum Speichern von Einschränkungen).

Beachten Sie, dass dies normalerweise der Fall ist nicht brauche diese Prädikate.Sie werden beispielsweise auf der obersten Ebene eingesetzt, um Residualziele zu erreichen.

Sie können einen Graphen mit endlichen Domänenbeschränkungen ausdrücken, ohne eines dieser Prädikate zu verwenden.Verwenden Sie beispielsweise eine endliche Domänenvariable B_i_j Das ist 1 wenn Es gibt einen Bogen vom Knoten ich zum Knoten J.

Wenn Sie stärkere Eigenschaften benötigen, benötigen Sie wahrscheinlich stärkere Einschränkungen.Zum Beispiel, circuit/1 ist in SICStus und SWI verfügbar und beschreibt einen Hamilton-Kreis.Für andere Eigenschaften können Sie dedizierte Filteralgorithmen implementieren.

Answer 2

Mit copy_term/3 Und term_variables/2 Sie sollten in der Lage sein, (Bearbeiten:fast) der gleiche Effekt wie fd_closure/2.

Bitte beachte, dass fd_closure funktioniert in SICStus nur für FD-Einschränkungen.Andere Zusammenhänge zwischen Variablen werden nicht berücksichtigt.

Bearbeiten:Auf diese Weise erhalten Sie nur Kopien interner Variablen – dies sollte ausreichen, um die Form zu bestimmen.Möglicherweise möchten Sie jedoch später auf diese Variablen verweisen. In diesem Fall ist die Lösung von @mat die richtige.