CLP的图形着色(FD)

Question

我正试图在Prolog中使用CLP(FD(来解决映射/图着色问题。我从纸上取了谓词"NP完全问题的CLP(FD(和ASP解决方案的比较"；我正在尝试以下示例：

coloring(K, Output) :- graph(Nodes, Edges),
create_output(Nodes, Colors, Output), domain(Colors, 1, K),
different(Output, Edges), labeling([ff], Colors).
create_output([],[],[]).
create_output([N | Nodes], [C|Colors], [N-C|Output]) :-
create_output(Nodes, Colors, Output).
different(_, []).
different(Output, [[A,B]|R]) :- member(A-CA, Output),
member(B-CB, Output), CA #= CB, different(Output, R).
graph([1,2,3,4,5],[(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)]).

但是当我运行查询时

create_output([1,2,3,4,5],[a,b,c,d],A).

即使对于这个图，它可能只使用4种颜色(a，b，c，d(，这也给我带来了错误。当我添加另一种颜色时，效果很好，似乎节点集的大小应该和颜色集的大小相同。但这不是地图着色应该做的。有人能帮我理解上面的谓词有什么问题吗？

Answer 1

我认为create_output/3应该只在实例化Nodes的情况下调用。它将创建另外两个列表，其中包含域变量(即颜色索引(以及节点和颜色之间的关联。

无论如何，从下面的代码中，你可以看到真正的问题是在不同/2的头部，其中使用了列表而不是"元组"来匹配边。。。

:- module(mapcolor,
[coloring/2]).
:- use_module(library(clpfd)).
coloring(K, Output) :-
graph(Nodes, Edges),
create_output(Nodes, Colors, Output),
domain(Colors, 1, K),
different(Output, Edges),
labeling([ff], Colors).
domain(Colors, Low, High) :- Colors ins Low .. High.
create_output([],[],[]).
create_output([N | Nodes], [C|Colors], [N-C|Output]) :-
create_output(Nodes, Colors, Output).
different(_, []).
different(Output, [(A,B)|R]) :-  % note: was [[A,B]|R]
member(A-CA, Output),
member(B-CB, Output),
CA #= CB,
different(Output, R).
graph([1,2,3,4,5],[(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)]).

请注意，图形只能用两种颜色着色：

?- coloring(2,C).
C = [1-1, 2-2, 3-2, 4-1, 5-1] ;
C = [1-2, 2-1, 3-1, 4-2, 5-2] ;
false.

有4种颜色，有很多解决方案。。。