如何 - Prolog 中的图形着色

Question

我正在尝试在 Prolog 中制作简单的图形着色算法，但我很难理解这种语言。我知道我想做什么 - 我想去一个顶点，找到所有其他连接到它的顶点，检查我的顶点的颜色，并根据它，用不同的颜色为其他顶点着色。我只是很难将其翻译成 Prolog。如果它是 C 方言或 Java，那对我来说是小菜一碟，但这让我很不舒服。

这是我到目前为止：

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, 

我怎样才能完成这个算法？

（编辑：graph_coloring 下的更多代码）

Answer 1

我想提一下这个问题是一个典型的约束满足问题，可以使用SWI-Prolog的 CSP 模块高效解决。这是完整的算法：

:- 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指示可用的颜色，vertex/1指示图中的顶点并edge/2定义顶点之间的对。此外，colorGraph(?List)确定顶点的颜色，其中List是hasColor(Vertex, Color)子句列表，Vertex是使用 的着色顶点Color。

让我们详细说明上面算法的每个部分，以了解会发生什么。

:- use_module(library(clpfd)).

它指示SWI-Prolog加载包含约束满足问题的谓词的模块。

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

谓词colorGraph/1是算法的入口点。它将边/顶点的子句转换为列表，约束ColorList以定义顶点列表，最后创建对颜色的约束并分配颜色（它们是两个独立的操作）。

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

预测createConstraint/2简单地指出两个链接的顶点必须具有不同的颜色。这是一个值得一提dif/2的CSP谓词。

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

谓词colorNodes/1为顶点分配正确的颜色。Prolog 将根据上面定义的约束注意分配正确的颜色。

最后，可以通过调用 predicate 找到结果colorGraph/1，例如：

?- 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)] ;

Answer 2

我认为你试图以一种对于 Prolog 程序来说不自然的方式思考；也就是说，你试图不使用递归:)我想出的是以下内容，但可能并不完全正确（已经晚了，而且当我试图有时思考时，我没有良好的声誉这...：） ）

假设您有由以下事实描述的图表：

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

并且可用的颜色是

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

（你只需要 3 种颜色来为平面图着色，所以我们在这里只使用 3 种）。我们还假设您希望将答案作为 [Vertex-Color] 列表给出，其中该列表将包含图形的每个顶点的颜色。我相信以下是正确的解决方案：

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.

第一个子句表示，如果从 V 到任何其他顶点都没有边，则尝试所有可能的颜色。第二个子句表示，如果存在从 V 到 V1 的边，则顶点 V 将获得颜色 C，并且顶点 V1 将获得颜色 C1，其中 V != V1 且 C != C1。（我还假设您的图是连接的，即没有未连接到其他顶点的顶点）。

由于我们只想要所有顶点都有颜色的解决方案，因此我们只会保留长度 |V| 的列表，其中 V 是您拥有的顶点集。您可以通过多种方式实施此限制；我更喜欢使用“findall/3”：

colors(X) :-
        coloring(X),
        findall(V,edge(V,_),List),
        length(List,Len),
        length(X,Len).

现在，通过咨询该程序并询问，|?- colors(X).您将获得图形顶点的所有可能的颜色分配。

如果有人发现问题，我几乎肯定上述解决方案中存在问题，请告诉我们:)

斯皮罗斯