0

我有一个充满事实的数据库，例如：

overground(newcrossgate,brockley,2).
overground(brockley,honoroakpark,3).
overground(honoroakpark,foresthill,3).
overground(foresthill,sydenham,2).
overground(sydenham,pengewest,3).
overground(pengewest,anerley,2).
overground(anerley,norwoodjunction,3).
overground(norwoodjunction,westcroydon,8).
overground(sydenham,crystalpalace,5).
overground(highburyandislington,canonbury,2).
overground(canonbury,dalstonjunction,3).
overground(dalstonjunction,haggerston,1).
overground(haggerston,hoxton,2).
overground(hoxton,shoreditchhighstreet,3).

例如：newcrossgate 到布罗克利需要 2 分钟。

然后我创建了一个规则，这样如果我输入查询 istime(newcrossgate,honoroakpark,Z)。那么prolog应该给我在这两个站之间旅行的时间。（我制定的规则旨在计算任何两个站点之间的距离，而不仅仅是相邻站点）。

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).
istime(X,Y,T,Z):- overground(X,Y,Z), T1 is T + Z.
istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

它似乎非常适合 newcrossgate 到前几个车站，例如 newcrossgate 到 Foresthill 或 sydenham。然而，在测试 newcrossgate 到 westcroydon 需要 26 分钟之后，我尝试了 newcrossgate 到水晶宫，prolog 说它应该需要 15 分钟......尽管事实上它是 westcroydon 之后的下一站。显然这里出了点问题，但是它适用于大多数车站，但时不时地偶尔会出现错误，谁能告诉我有什么问题吗？:S

4

3 回答 3

2

这和你上一个问题本质上是一样的问题，唯一的区别是你需要边走边积累时间。

我看到的一件事是您的“公共”谓词istime/3试图做太多事情。它应该做的就是为累加器播种并调用工作者谓词istime/4。由于您正在寻找双向的路线/时间，因此公共谓词应该只是

istime( X , Y , Z ) :- istime( X , Y , 0 , Z ) .
istime( X , Y , Z ) :- istime( Y , X , 0 , Z ) .

以上基本上是您的istime/3谓词的第一个子句

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).

的其余子句istime/3，递归子句：

istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

应适当地成为蓄能器的一部分istime/4并存在蓄能器。这就是你的问题所在。

再试一次并编辑您的问题以显示下一次迭代。如果您仍然无法弄清楚，我将向您展示一些不同的方法来做到这一点。

一些提示

  1. 您的“工人”谓词可能看起来很像您之前的“在两个站点之间找到一条路线”练习，但它会有一个额外的参数，即经过时间的累加器。

  2. 有两种特殊情况。如果您使用“在两个站点之间查找路线”解决方案中使用的方法，则特殊情况是

    • A 和 B 直接相邻。
    • A 和 B 通过至少一个中间站连接。

还有另一种方法，可能被描述为使用前瞻，在这种情况下，特殊情况是

  • A 和 B 是相同的，在这种情况下你就到了。
  • A 和 B 不是，而是由零个或多个中间停靠点连接。

FWIW，您不必期望经过时间最短或跳数最少的路线是找到的第一个解决方案。回溯会产生所有的路径，但是它们被发现的顺序与事实在数据库中的存储顺序有关。图的最小成本搜索完全是另一锅鱼。

于 2012-01-13T23:41:29.587 回答
1

您是否尝试过使用 循环浏览答案;？26分钟不是newcrossgate和westcroydon之间最短的时间……

编辑：我的坏！显然，较短的结果是由于您的代码中的错误造成的（请参阅我对第 4 条的评论）。但是，您的代码是正确的，15 分钟是 newcrossgate 和水晶宫之间的最短路线。仅仅因为有一条路线从 newcrossgate 到 westcroydon，然后是水晶宫，这并不意味着它是最短的路线，或者您的程序将首先产生的路线。

更新：如果您在寻找某些路线的答案时遇到问题，我建议将第 3 条更改为：

istime(X,Y,_,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.

原因很简单：您的第一个子句将 X 与 Y 交换，这很好，因为您说的路线是对称的。但是，第 3 个子句并没有从中受益，因为它从未被交换过的子句调用。忽略第三个参数（无论如何您都没有使用），从而让第一个子句调用第三个可能会解决您的问题，因为一些以前未使用的有效路由现在将是。

（另外：我同意 Nicholas Carey 的回答，最好使用第三个参数作为累加器；但正如我所说，暂时忽略它可能会起作用）

于 2012-01-13T23:28:49.673 回答
1

为了使它起作用，您需要对上一条中所述的两次旅程进行相反的操作。保持谓词原样，istime(X,Y,Z) 并创建另一个包含反向旅程的子句。通过这种方式，它适用于所有站点。（经过试验和测试）

于 2012-01-14T15:00:03.720 回答