首页 文章

Prolog - 帮助修复规则

提问于
浏览
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到brockley需要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到crystalpalace和prolog说它应该需要15分钟......尽管事实上它是在westcroydon之后的下一站 . 显然这里有些不对劲,但它适用于大多数电台,偶尔会偶尔出现错误,有人能告诉我什么是错的吗? :S

3 回答

  • 1

    这与您之前的问题基本上是同一个问题,唯一的区别是您需要随时积累时间 .

    我看到的一件事是你的"public"谓词, istime/3 试图做太多 . 它应该做的只是为累加器播种并调用worker谓词 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 的一部分并且存在累加器 . 这就是你的问题所在 .

    再给它一个镜头并编辑你的问题以显示下一次迭代 . 如果你仍然无法弄明白,我会告诉你一些不同的方法 .

    Some Hints

    • 你的“ Worker ”谓词可能看起来很像你之前的“找到两站之间的路线”练习,但它会有一个额外的参数,即累计器的经过时间 .

    • 有两种特殊情况 . 如果您使用在“在两个站点之间找到路径”解决方案中使用的方法,则会出现特殊情况

    • A和B直接相邻 .

    • A和B通过至少一个中间挡块连接 .

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

    • A和B是相同的,在这种情况下你到了 .

    • A和B不是并且由零个或多个中间停止连接 .

    FWIW,您不应该期望具有最短经过时间或最小跳数的路由是找到的第一个解决方案 . 回溯将产生所有路径,但它们的发现顺序与事实存储在数据库中的顺序有关 . 图表的最低成本搜索完全是另一个鱼的水壶 .

  • 2

    您是否尝试使用 ; 循环回答? 26分钟是 not newcrossgate和westcroydon之间的最短时间......

    Edit :我的坏!显然,较短的结果是由于您的代码中的错误(请参阅我对第4条款的评论) . 但是,你的代码是正确的,15分钟是newcrossgate和crystalpalace之间的最短路径 . 只是因为有一条路线从newcrossgate到westcroydon,然后是crystalpalace,它不是 shortest 路线,或者是你的程序首先产生的路线 .

    Update :如果您建议将第3条改为:

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

    原因很简单:你的第一个子句用X交换X,这很好,因为你说这些路线是对称的 . 但是,第3个子句并没有从中受益,因为它从未被交换的子句调用 . 忽略第三个参数(你没有使用它)并因此让第一个子句调用第三个可能会解决你的问题,因为以前没有使用过的一些有效路由 .

    (另外:我同意Nicholas Carey的回答,最好使用第三个参数作为累加器;但正如我所说的,暂时忽略它可能会起作用)

  • 1

    为了使其工作,您需要执行与上一条款中规定的两种旅程相反的操作 . 保持谓词不变,istime(X,Y,Z)并且只创建包含反向旅程的另一个子句 . 这样它适用于所有站点 . (尝试和测试)

相关问题