Prolog 中的图形着色问题：程序未终止

Question

vertex(1).
vertex(2).
vertex(3).
vertex(4).

color(1).
color(2).
color(3).

edge(1,2).
edge(1,3).
edge(1,4).
edge(2,4).
edge(3,4).
edge(X,Y):-edge(Y,X).

getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).

check(Z):-edge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N,!,fail.


getcolor(1,red).
getcolor(2,blue).
getcolor(3,green).


colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),write([A,B,C,D]),check([A,B,C,D]),write([A,B,C,D]).

这是我的代码。它没有被终止的问题。但是代码逻辑清晰，如果大家发现哪里有问题请帮我改正。

输入：- colorit(Z).

output:- [1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 1, 3, 1]
[1, 1, 3, 2]
[1, 1, 3, 3]
[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]
[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]

它一直到这里，[1,2,2,3] 这是真正的解决方案，它在循环中并且不会通过返回 true.There 来终止，这只是需要进行的一个小修正。请帮帮我。

Answer 1

关于您的代码的一些注释：

规则 edge(X,Y):-edge(Y,X). 创建无限搜索树。

改为使用hasEdge(X,Y) :- edge(X,Y) ; edge(Y,X).

这意味着当 edge(X,Y) 或 edge(Y,X) 为真时 hasEdge(X,Y) 为真。然后将 check 谓词中 edge 的用法替换为 hasEdge.
您的检查定义没有提供任何肯定的案例。你说：当顶点 X 和 Y 之间有一条边时，着色列表 Z 的第 X 和第 Y 元素相等，然后失败。但是当这个条件不成立时，你无法让 check 为真，所以这条路径也会失败。为此，添加一个 check(Z). 声明在你的 check 规则之后（类似于你如何定义 not 谓词，见 here ).甚至更短，您可以完全删除失败路径，只需在 colorize.

not

根据这些观察结果，您的程序可以重写为（我跳过了事实）：

hasEdge(X,Y):-edge(X,Y) ; edge(Y,X).

getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).

check(Z):-hasEdge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N,!,fail.
check(Z).

colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),check([A,B,C,D]).

或使用not:

hasEdge(X,Y):-edge(X,Y) ; edge(Y,X).

getelement(1,[Z|_],Z).
getelement(X,[Z|Zs],M):-K is X-1,getelement(K,Zs,M).

check(Z):-hasEdge(X,Y),getelement(X,Z,M),getelement(Y,Z,N),M=:=N.

colorit([A,B,C,D]):-color(A),color(B),color(C),color(D),not(check([A,B,C,D])).

Prolog 中的图形着色问题：程序未终止

Graph Coloring Problem in Prolog : Program not terminating

prolog

graph-coloring