1

我有一个问题描述如下：

编写一个为图形着色的 prolog 程序。颜色由 color/1 谓词定义，图形由子句 edge/2 定义。您必须编写谓词 coloring(Coloring) 来查找图形的节点 node_1、...、node_n 的着色。着色是列表 [node_1/color_1,..., node_n/color_m] 其中 color_1, ..., color_m 是颜色，满足每条边的节点具有不同颜色的属性。

让我们看一个例子。让颜色和边缘成为下面的谓词。

% 2 colors
color(blue).
color(red).
% the edges
edge(1,2).
edge(1,3).
edge(2,4).
edge(5,2).

对于这个数据，coloring(C) 是满足的。一种解决方案是

C = [ 1/blue, 2/red, 3/red, 4/blue, 5/blue].

在下面写下谓词颜色。

实际上，我刚刚开始做这个练习。所以我不知道。我认为四种颜色足以为图形着色。也许有人问过类似的问题。当我有一些想法时，我会尽快发布。

4

1 回答 1

2

您需要知道节点的名称。一种方法是使用 setof/3 ：

setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN)

X^Y 表示 X 和 Y 必须用于搜索，但不能用于结果。

现在我们使用谓词 set_color(List_of_nodes, List_of_association) 构建了关联节点/颜色的列表。

一个空的节点列表给出了一个空的关联列表！

set_color([], [])

现在，过程：

% we work with the current element of the list of nodes
set_color([H | T], [H/C | TC]) :-
    % we create the association for the rest of the list
    set_color(T, TC),
    % we choose the color
    color(C),
    % we check that two adjacent nodes of different colors
    forall(member(Node/Color, TC),
           (   (edge(Node, H) -> Color \= C; true),
           ( edge(H, Node) -> Color \= C; true))).

所以你得到：

% 2 colors
color(blue).
color(red).
% the edges
edge(1,2).
edge(1,3).
edge(2,4).
edge(5,2).

coloring(L) :-
    setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN),
    set_color(LN, L).


set_color([], []).

set_color([H | T], [H/C | TC]) :-
    set_color(T, TC),
    color(C),
    forall(member(Node/Color, TC),
           (   (edge(Node, H) -> Color \= C; true),
           ( edge(H, Node) -> Color \= C; true))).

我忘了说带有回溯的 Prolog 可以完成这项工作！

于 2013-07-29T11:40:12.713 回答