使用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。它将创建另外两个列表，其中包含域变量(即颜色索引)以及节点和颜色之间的关联。

无论如何，从下面的代码中，你可以看到真正的问题是在different/2的头部，其中使用了一个列表而不是一个'tuple‘来匹配一个边……

:- 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种颜色，有很多解决方案...