4

我知道 Prolog 在技术上没有“回报”,但我不知道如何提出这个问题。

我找到了一些用于查找地铁站之间路线的算法的示例代码。它工作得很好,但是它应该只打印结果,因此很难扩展或做一个findall/3例子。

% direct routes
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Y,Stations),
    append(Output,[[X,Line,Y]],NewOutput),
    print(NewOutput).

% needs intermediate stop
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Intermediate,Stations),
    X\=Intermediate,Intermediate\=Y,
    append(Output,[[X,Line,Intermediate]],NewOutput),
    findRoute(Intermediate,Y,[Line|Lines],NewOutput).

line是一个带有一个原子和一个包含站点的列表的谓词。
例如:line(s1, [first_stop, second_stop, third_stop])

所以我要做的是print在第 11 行去掉它,并在我的规则中添加一个额外的变量来存储结果以供以后使用。但是我失败了,因为无论我尝试什么,它要么进入无限循环,要么返回 false。

现在:

?- findRoute(first_stop, third_stop, [], []).
% prints [[first_stop,s1,third_stop]]

想:

?- findRoute(first_stop, third_stop, [], R).
% [[first_stop,s1,third_stop]] is stored in R
4

1 回答 1

4

和你一样,我在 Prolog 初学者中也经常看到这种模式,尤其是当他们使用糟糕的书籍和其他材料时:

solve :-
     .... some goals ...
     compute(A),
     write(A).

上面几乎每一行都是有问题的,原因如下:

  1. “解决”势在必行。这在像 Prolog 这样的声明性语言中没有意义,因为您可以在多个方向使用谓词。
  2. “计算”也是必不可少的。
  3. write/1是一个副作用,它的输出只能在系统终端上使用。这使我们没有简单的方法来实际测试谓词。

这样的模式应该总是简单地看起来类似于:

solution(S) :-
     condition1(...),
     condition2(...),
     condition_n(S).

wherecondition1等只是纯粹的目标,描述S了解决方案的含义。

查询时

?- solution(S).

然后绑定S自动打印在顶层。让顶层为您打印!

在您的情况下,有一个直截了当的解决方法:只需提出NewOutput一个论点,然后删除最终的副作用:

路线(X,Y,线,输出,输出):-
    线路(线路,车站),
    \+ 成员(线,线),
    成员(X,站),
    成员(Y,车站),
    追加(输出,[[X,线,Y]],新输出)。

另请注意,我已将名称更改为 just ,因为如果参数都已实例化route/5,谓词也有意义,这对于测试等很有用。

此外,在描述列表时,您通常会从使用表示法中受益匪浅。

代码将与此类似:

路线(S,S,_)-> []。% case 1: 已经存在
route(S0, S, Lines) --> % case 2: 需要中间停止
    { line_stations(Line, Stations0),
      地图列表(差异(线),线),
      选择(S0,Stations0,Stations),
      成员(S1,站)},
    [链接(S0,Line,S1)] ,
    路线(S1,S,[线|线])。

方便地,您可以使用它来描述列表的串联,而不需要append/3太多。我还进行了一些其他更改以提高纯度和可读性,并且我将找出确切的差异作为一个简单的练习。

您可以使用 DCG 接口 predicate 调用它phrase/2,使用:

?- phrase(route(X,Y,[]), Rs).

Rs找到的路线在哪里。另请注意,我使用表单术语link/3来表示路线的链接。当数量已知时,使用专用术语是一种很好的做法。例如,如果您事先不知道需要表示多少元素,那么列表就很好。

于 2016-03-25T16:27:58.997 回答