5

我正在尝试解决这个问题，并且我已经阅读了这个答案，但我的问题是无限循环，即使我使用了访问过的节点列表。

让我们看看我的两次尝试：

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).


% ------ simple path finding in a directed graph

% -----  simple exploration

path0(A,B, Result) :-
    path0(A, B, [], Result).

path0(A, B, _, [e(A,B)]):- 
    edge(A,B).    
path0(A, B, Visited, [e(A,X)|Path]):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path0(X, B, [A|Visited], Path ).    


%---- 1. exploration and length    

path(A, B, _, [e(A,B)], 1):- 
    edge(A,B).    
path(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),
    \+ member(X, Visited),
    length(Path, L),        % ERR: Path refers to a open list
    Length is L + 1,
    path(X, B, [A|Visited], Path, _).

% --- 2. not working

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, [], [e(A,B)], 1):- 
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.

这给了我类似的答案，即：

 ?- path(1,3, Path, Length).
Path = [e(1, 3)],
Length = 1 ;
Path = [e(1, 2), e(2, 3)],
Length = 2 ;

然后 Swi-Prolog IDE 冻结。

  • 我应该将什么定义为基本情况？
  • 如果是这种情况，为什么第二个实现会循环，即使我使用访问的节点列表和 dif() 来确保避免统一来回走动？我打错了函数名。

我想摆脱 length/2 的使用。谢谢。

编辑：

所以，我发现这应该是更干净的方法，即使我想要更类似于第二种实现的东西，这在最短路径问题求解器中更容易转换，因为它只是一个 min{ pathLengths }从第一次调用 path3/4 开始。

% ---- 3. working    
%   
min(A,B,A):- A =< B, !.       % for future use (shortest path)
min(_,B,B).

path3(From, To, Path, Len):-    
    path0(From, To, [], Path),
    length(Path, Len).
    %min(Len, MinLength, ?)

这是第二个实现路径2的更正版本：

% --- 2. 
% errors: 1. in base case I have to return Visited trough _, 
%             I can't pass a void list []
%         2. dif(X,B) is unuseful since base case it's the first clause

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, _, [e(A,B)], 1):-      % If an edge is found
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),  
    %tab(1),write(A),write('-'),write(X),
    \+ member(X, Visited),
    %tab(1),write([A|Visited]),write(' visited'),nl,
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.
4

1 回答 1

4

两者都path/4暴露path2/4相似的非终止行为的原因是因为两者都使用相同的辅助谓词path/5。您可能的意思是path2/5：

path2(A,B, Result, Length) :-
    path(A, B, [], Result, Length).
 %  ^^^^ replace by path2

也许首先，让我们看看你的path/4定义为什么会循环。为了看到这一点，我将false在你的程序中插入目标。这些目标将减少推理的数量。当剩余的片段仍然循环时，我们可以确定我们看到了负责不终止的部分。经过一些实验，我发现了以下片段，称为：

边缘（1,2）。
边缘（1,4）：-假。
边缘（1,3）：-假。
边缘（2,3）：-假。
边缘（2,5）：-假。
边缘（3,4）：-假。
边缘（3,5）：-假。
边缘（4,5）：-假。

路径（A，B，结果，长度）：-
    路径（A，B，[]，结果，长度），假。

路径（A，B，_，[e（A，B）]，1）：-假，
    边缘（A，B）。
路径（A，B，访问，[e（A，X）|路径]，长度）：-
    边（A，X），
    \+ 成员（X，已访问），
    length(Path, L), false ,
    长度是 L + 1 ,
     path(X, B, [A|Visited], Path, _)。

所以本质上是length/2谓词的使用。只要路径的长度不固定，这个片段就不会终止。所以对于查询

?- path(1, 3, Path, N).

它的Path长度不受限制，因此length/2会找到无限多的解决方案 - 因此不会终止。

但是，毕竟，你为什么要知道长度呢？path 参数已经隐含地描述了它。

对于您的定义，请path/4,5考虑查询的内容

?- path(1, X, Path, N).

应该产生作为答案。也应该Path = [1]是一个解决方案？这有点关于路径/步行的确切定义的问题。我认为应该。

有关通用解决方案，请参阅此答案。有了它，您可以像这样定义您感兴趣的谓词：

yourpath(A,B, Path, N) :-
   path(edge, Path, A,B),
   length(Path, N).

但是，我宁愿不添加关于路径长度的额外参数。无论如何，您可以稍后随时添加该信息。

于 2016-03-23T21:14:27.140 回答