Wie - Graph-Färbung in Prolog

Ich versuche, mich der einfache graph-coloring-Algorithmus in Prolog, aber ich bin ein bisschen eine harte Zeit zu verstehen, die Sprache. Ich weiß, was ich will - ich will gehen zu einem Eckpunkt, alle anderen vertices verbunden sind, überprüfen Sie meine vertex Farbe, und abhängig davon die Farbe der anderen Knoten mit verschiedenen Farben. Ich habe gerade eine harte Zeit zu übersetzen und diese zu Prolog. Wenn es ein C-Dialekt oder Java, es wäre ein Stück Kuchen für mich, aber das ist was mir passt.

Dies ist, was ich habe, so weit:

main:- graph_coloring.

%color_list([blue, red, green, yellow, white], colors).
%vertex_list([a, b, c, d], vertices).
%edge_list([(a,b),(b,c),(c,d)], edges).

%Our graph
color(blue).
color(red).
color(green).
color(black).
color(white).

%graph([a-b, b-c, b-d, c-d]).

vertex(a).
vertex(b).
vertex(c).
vertex(d).

%Subject to changing, so are asserted into listener at runtime.
init_dynamic_facts:-
    assertz(vertex_color(a, none)),
    assertz(vertex_color(b, none)),
    assertz(vertex_color(c, none)),
    assertz(vertex_color(d, none)),
    assertz(location(a)).

edge(a,b).
edge(b,c).
edge(b,d).
edge(c,d).

is_connect(A,B):-
    edge(A,B).
is_connect(A,B):-
    edge(B,A).

connections(Vertex):-
    edge(Vertex,X).
connections(Vertex):-
    edge(X,Vertex).

move(Vertex):-
    retract(location(_)),
    asserta(location(Vertex)).

paint_vertex(Vertex, Color):-
    retract(vertex_color(Vertex,_)),
    asserta(vertex_color(Vertex, Color)).

find_vertex_color(Vertex):-
    vertex_color(Vertex, X).


graph_coloring:-

    location(Current_vertex),
    vertex_color(Current_vertex, Curr_color),
    ( Curr_color =:= none ->
        connections(Current_vertex, Others),
        vertex_color(Others, Other_colors),
        paint_vertex(Current_vertex,

Wie kann ich dieses Algorithmus?

(edited: mehr code unter graph_coloring)

Wollen Sie nicht gehen, um eine verfärbungsfreie vertex, dann wählen Sie eine Farbe, die nicht von jedem Nachbar-vertex?
Ich fange an mit keine Scheitelpunkte gefärbt, obwohl, um sicher zu sein, könnte es besser sein, eine Farbe zuweisen, die erste und tun, was du sagst.
Können Sie etwas konkreter über das, was Problem, das Sie haben?
Ich versuche zu tun, der graph-coloring-Algorithmus in prolog, aber es ist so anders als alles, was ich verwendet habe, ich bin mir auch nicht ganz sicher, wo zu beginnen. Zum Beispiel Variablen. Sie werden verwendet, anders als im prolog, und ich habe Sie auch schon gebeten anders. Zum Beispiel, in C# kann ich sagen Variable_I_want = Method_that_returns_the_variable(). Ich kann es nicht ganz tun, dass im prolog, und ich haven ' T bekommen mein Kopf herum, wie dies der "prolog Weg".
Vielleicht sollten Sie beginnen mit etwas einfacherem, wie die Zuordnung aller Ihrer Scheitelpunkte einer bestimmten Farbe.
Was ich brauchen würde, dann ist ein Weg zum vergleichen der Scheitelpunkte' Farben, um Sie zu ändern, wenn ich muss. Ich kann zum Beispiel sagen: in C#: color_list //enthält alle Farben vertex_list // alle Eckpunkte für v in vertex_list { // Finden Sie heraus, die Farben der benachbarten Ecken zu v, und wenn die Farbe ist die gleiche, es ändern. } Dies ist im wesentlichen das, was ich versuche zu tun, aber ich weiß nicht, wie.
Wenn man das tut, Logik-Programmierung, die Sie wollen, um zu vermeiden, denken über die Dinge verändern. Stattdessen bauen Sie eine Antwort. Zur Beantwortung größerer Fragen, Sie bitten, kleinere Fragen. Zum Beispiel, um die Frage zu beantworten "wie sollten alle diese Eckpunkte gefärbt werden?", Sie müssen zuerst die Frage: "wie sollte der erste Eckpunkt gefärbt werden?", dann "wenn der erste Eckpunkt hat die Farbe X, was soll dann der zweite vertex-Farbe sein?"

InformationsquelleAutor Tino | 2012-05-23

2

Ich denke, dass Sie versuchen zu denken, in einer Weise, die nicht natürlich für Prolog-Programme; das heißt, Sie versuchen nicht, Rekursion zu verwenden :), Was ich kam mit ist das folgende, welches jedoch möglicherweise nicht ganz korrekt (es ist spät, und ich don ' T haben einen guten Ruf, wenn Sie versuchen zu denken, in Zeiten wie diesen...:) )

Nehmen wir an, Sie haben den graph beschrieben durch die folgenden Tatsachen:
```
edge(a,b).
edge(b,c).
edge(b,d).
edge(c,d).
```
ist und dass die verfügbaren Farben sind
```
color(blue).
color(red).
color(green).
```
(Sie benötigen nur 3 Farben Farbe ein planarer graph, so lassen Sie uns nur 3 hier). Lassen Sie uns auch annehmen, dass Sie wollen, die Antwort gegeben werden, als [Vertex-Farbe] Liste, wo dann enthält die Liste eine Farbe für jeden vertex von Ihrem Diagramm. Ich glaube, das folgende ist die korrekte Lösung:
```
coloring([V-C]) :-
        color(C),
        \+ edge(V,_).
coloring([V-C,V1-C1|Coloring]) :-
        color(C),
        edge(V,V1),
        V \== V1,
        coloring([V1-C1|Coloring]),
        C1 \== C.
```
Die erste Klausel besagt, dass, wenn es keine Kante von V zu jedem anderen Eckpunkt, nur versuchen, alle möglichen Farben. Die zweite Klausel besagt, dass Knoten V erhalten Farbe C und vertex V1 erhalten Farbe C1, wenn es eine Kante von V zu V1, wobei V != V1 und C != C1. (Ich habe auch angenommen, dass Ihr graph ist verbunden, d.h. es gibt keine Eckpunkte, welche keine Verbindung zu anderen Knoten).

Und da wollen wir nur Lösungen, bei denen alle Eckpunkte Farben haben, werden wir nur halten Listen der Länge |V|, wobei V die Menge der vertices, die Sie haben. Sie können diese Einschränkung implementiert, die in verschiedenen Formen; ich bevorzuge die "findall/3":
```
colors(X) :-
        coloring(X),
        findall(V,edge(V,_),List),
        length(List,Len),
        length(X,Len).
```
Nun, durch die Beratung dieses Programm und Fragen |?- colors(X). erhalten Sie alle möglichen farbzuweisungen für die Eckpunkte Ihres Graphen.

Wenn jemand feststellt, dass ein problem ich bin mir fast sicher, dass es vorhanden ist in der obigen Lösung, bitte, lassen Sie es uns wissen 🙂

Spyros
- Vielen Dank Spyros! Jetzt versuche ich herauszufinden, warum Farben(X). ist wieder 'Nein', aber jetzt ich bin dies zu verstehen ein bisschen mehr. Sollte es eine Liste wie [a-b, b-c, b-d, c-d], oder sollte der code laufen nur mit der Kante/2-farbig/1-Fakten?
- Offenbar ist die Liste ist das problem; nach findall(...), length(Liste, Len) schlägt fehl, weil aus irgendeinem Grund die Liste ist eine "Schlechte Ziel: H38".
- Ich lief den obigen code in XSB-Prolog und es gibt die richtige (hoffe ich 🙂 )Antwort. Die Prolog-compiler verwenden Sie? Vielleicht findall/3 erfordert andere Argumente in anderen Prologe...Die Verwendung von findall/3 ist hier genauso zu finden, wie viele vertices, die Sie haben. Sie können ersetzen es mit der tatsächlichen Anzahl, wenn Sie wollen. Fügen Sie einfach einen Knoten(4)" Tatsache, das die Anzahl der Scheitelpunkte, die Sie haben in Summe, und ersetzen Sie die Aufrufe von findall und-Länge(Liste,Len) mit den Eckpunkten(Len). Die einzigen Sachen, die ich in meinem source-code sind die Definitionen von Rand/2, color/1, Farben/1-Farben/1.
InformationsquelleAutor Spyros

Möchte ich erwähnen, dieses problem ist ein typisches constraint satisfaction problem und Leistungsfähigkeit sein können, gelöst mit dem CSP-Modul des SWI-Prolog. Hier ist der vollständige Algorithmus:

:- use_module(library(clpfd)). 

color(red).
color(blue).
color(green).

vertex(a).
vertex(b).
vertex(c).
vertex(d).
vertex(e).

edge(a,b).
edge(a,c).
edge(b,c).
edge(b,d).
edge(c,d).


colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

color/1 zeigt die verfügbaren Farben, vertex/1 zeigt die Eckpunkte auf dem Graphen und edge/2 definiert die Paare zwischen den Scheitelpunkten. Darüber hinaus colorGraph(?List) bestimmt die Farbe von den Ecken, wo List ist eine Liste von hasColor(Vertex, Color) Klauseln Vertex die farbigen vertex mit Color.

Let ' s details zu jedem Teil der obige Algorithmus zu verstehen, was passiert.

:- use_module(library(clpfd)).

Zeigt es SWI-Prolog laden Sie das Modul mit der Prädikate für constraint satisfaction Probleme.

colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

Dem Prädikat colorGraph/1 ist der Ausgangspunkt des Algorithmus. Es wandelt die Klauseln von Kanten/Knoten in Listen, Einschränkungen der ColorList die Liste von Eckpunkten definiert und schließlich mit den Zwängen, die Farben zuzuordnen und die Farben (Sie sind zwei getrennte Vorgänge).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

Den predictate createConstraint/2 einfach besagt, dass zwei miteinander verknüpften Punkten muss eine andere Farbe. Dies ist insofern erwähnenswert dif/2 ist ein CSP-Prädikat.

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

Dem Prädikat colorNodes/1 weist die richtige Farbe an den Ecken. Prolog zu betreuen zuordnen der richtigen Farben, basierend auf den Einschränkungen, die oben definiert werden.

Schließlich die Ergebnisse können gefunden werden, durch aufrufen das Prädikat colorGraph/1 wie:

?- colorGraph(L).
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, green)] ;

InformationsquelleAutor ZenLulz

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.