我正在尝试使用DCG表示法来解决传统的路径查找难题。这些是一些相连的数字，它们从开始到结束形成一条链。如果有这样或那样的连接，你可以像往常一样在两个数字之间切换。目前没有其他路线
connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).
step(X, Y) :-
connected(X, Y).
step(X, Y) :-
connected(Y, X).
我尝试了几个小时的事情，但没有过多地从开始连接到某个东西，某个东西连接到结束，中间的链条进入无限循环，或者发现它们之间没有链条的断开的步骤。目前我有：
path([start,B,C]) --> { step(start, B), step(B, C) }.
path([A,B|C]) --> { step(A, B) }, path([B|C]).
path([B,C,end]) --> { step(B, C), step(C, end) }.
其产生：
?- phrase(path(Ts), Ls)
Ls = [],
Ts = [start, 1, 2]
Ls = [],
Ts = [start, 1, start]
Stack limit (1.9Mb) exceeded
Stack sizes: local: 1.4Mb, global: 0.3Mb, trail: 67Kb
Stack depth: 5,534, last-call: 0%, Choice points: 8,270
Possible non-terminating recursion:
[5,532] path([length:2|_1460], _1452, [])
[5,531] path([length:3|_1494], _1486, [])
我认为链式规则是1->2->1->2->1.永远我似乎无法检查+ memberchk(B, C)，因为列表C尚未定义。
有了这个长度限制，它会生成其他模式：
?- length(Ts, _), phrase(path(Ts), Ls).
<snip>
Ts = [7, 8, 9, 8, 9, 10, end]
或者像这样：
?- length(Ts, _), phrase(path(Ts), Ls), nth0(0, Ts, start).
<snip>
Ts = [start, 1, 2, 1, start, 1, start, 1, start, 1, start]
但从头到尾都不是一条漂亮的链条。我可以添加一个约束吗；下一步一定是以前没有见过的"；？我该如何收集"；以前看到的一切"；当DCG风格似乎在描述"；将在未来看到的列表"；？(我只是试图根据事实列出一个列表，而不是单独分析任何内容，这是一个问题吗？(
我已经看过了https://www.metalevel.at/prolog/dcg并尝试使用CCD_ 3和CCD_。将这个窗口函数改编成一个重叠的窗口，并尝试使用它。制作[step(1,2), step(2,3)列表而不是[1,2,3。在列表上做准备更像path([C|A,B]，好像这可能会给我一个历史记录。
以这种方式使用DCG没有任何好处。。。隐藏的参数永远不会被使用。
:- module(so_path_finding,
[path//3]).
connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).
step(X, Y) :-
connected(X, Y).
step(X, Y) :-
connected(Y, X).
path(A,B,P) --> path(A,B,[],P).
path(A,B,S,P) --> {step(A,I),+memberchk(I,S)},path(I,B,[A|S],P).
path(A,B,S,P) --> {step(A,B),+memberchk(B,S),reverse([B|S],P)}.
测试：
?- phrase(path(start,end,P),[]),writeln(P).
[start,1,2,3,4,5,6,7,8,9,end]
P = [start, 1, 2, 3, 4, 5, 6, 7, 8|...] ;
false.
然后，至少使用隐藏参数来获得输出路径
:- module(so_path_finding,
[path//2]).
connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, 5).
connected(5, 6).
connected(6, 7).
connected(7, 8).
connected(8, 9).
connected(9, 10).
connected(10, end).
step(X, Y) :-
connected(X, Y).
step(X, Y) :-
connected(Y, X).
path(A,B) --> path(A,B,[]).
path(A,B,S) --> {step(A,I),+memberchk(I,S)},[A],path(I,B,[A|S]).
path(A,B,S) --> {step(A,B),+memberchk(B,S)},[B].
现在我们有了一个不同的界面：
?- phrase(path(start,end),P),writeln(P).
[start,1,2,3,4,5,6,7,8,9,end]
P = [start, 1, 2, 3, 4, 5, 6, 7, 8|...] ;
false.
编辑
在OP评论中澄清后，这里有一个尝试(通过图形简化来减少混乱…(
:- module(so_path_finding,
[path//0]).
connected(start, 1).
connected(1, 2).
connected(2, 3).
connected(3, 4).
connected(4, end).
step(X, Y) :-
connected(X, Y).
step(X, Y) :-
connected(Y, X).
path --> {connected(start,S)}, path(S).
% variables naming convention:
% V: vertex, I: intermediate, N:next
path(V) --> [V], {connected(V,end)}.
path(I) --> [I], {step(I,N)}, path(N).
被称为
?- phrase(path,P).
P = [1, 2, 3, 4] ;
P = [1, 2, 3, 4, end, 4] ;
...
很明显，它还不完整，但也许它朝着正确的方向发展？如果是这种情况，那么只需要重新引入迄今为止看到的顶点累加器和+memberchk(.,.)的"实现细节"，以避免循环。。。
继续
因此，让我们实现这个细节：
path --> {connected(start,S)}, path(S,[]).
path(V,S) --> [V], {+memberchk(V,S), connected(V,end)}.
path(I,S) --> [I], {+memberchk(I,S), step(I,N)}, path(N,[I|S]).
现在我们有
?- phrase(path,P).
P = [1, 2, 3, 4] ;
false.
正如预期的那样。