0

我正在尝试使用 Prolog 中的 CLP(FD) 解决地图/图形着色问题。我从论文“CLP(FD) 和 ASP 解决方案对 NP 完全问题的比较”中获取了谓词，并尝试使用以下示例：

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）。当我添加另一种颜色时它工作正常，似乎节点集的大小应该与颜色集相同。但这不是地图着色应该做的。任何人都能够帮助我理解上述谓词有什么问题？

4

1 回答 1

1

我认为create_output/3应该只用实例化的节点来调用。它将使用域变量（即颜色索引）以及节点和颜色之间的关联创建其他 2 个列表。

无论如何，从下面的代码中，您可以看到真正的问题在于不同/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)]).

请注意，图表只能用 2 种颜色着色：

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

于 2021-05-11T18:42:10.823 回答