Prolog:图遍历中的处理周期 [英] Prolog: handling cycles in graph traversal

问题描述

road(london, paris, 135).
road(paris, london, 135).
road(paris, madrid, 250).
road(madrid, paris, 250).
road(madrid, barcelona, 70).
road(barcelona, madrid, 70).

route(X, Y, [X|Y], N) :-
   road(X, Y, N).
route(X, Y, [X|T], N) :- 
   road(X, Z, A),
   route(Z, Y, [_|T], B),
   N is A + B.

这是我面临的问题的示例代码.我的测试输入是

This is a sample code of the problem I am facing. My test input is

?- route(london, barcelona, R, 455).

此输入将继续在london-paris和paris-london上重复，但是我注意到，如果我删除循环paris-london，它将找到从london-barcelona出发的路线.

This input will keep re-iterating through london-paris and paris-london, however I have noticed that it will find the route from london-barcelona if I remove, the cycle paris-london.

我的问题是，是否有任何方法可以实现谓词，从而使我可以忽略循环.

My question is if there is any way I can implement a predicate which will allow me to ignore a cycle.

推荐答案

您可以进行以下修改:

road(london, paris, 135).
road(paris, madrid, 250).
road(madrid, paris, 250). 
road(madrid, barcelona, 70).
road(barcelona, madrid, 70).

path(From, To, List, N) :-
   route(From, To, [From], N).

route(X, Y, Passed_city, N) :-
   road(X, Y, N).
route(X, Y, Passed_city, N) :- 
   road(X, Z, A),
   \+ member(Z, Passed_city),
   route(Z, Y, [Z|Passed_city], B),
   N is A + B.

并调用查询

?- path(london, barcelona, R, 455).

我所做的是为path/4创建新规则 将第一个城市来自插入包含您通过的所有城市的列表中，例如:route(From, To, [From], N).

What I did is to create a new rule for path/4 to insert the first city From in the list which contains all the cities you passed, like so: route(From, To, [From], N).

然后我插入了目标\+ member(Z, Passed_city) 在第二条规则的正文中.

Then I've inserted the goal \+ member(Z, Passed_city) in the body of the second rule.

\+的意思是不可证明"，因此 如果member(Z, Passed_city)失败，即Z不在Passed_city中，则\+ member(Z, Passed_city)为true.

\+ means "not provable", so \+ member(Z, Passed_city) is true if member(Z, Passed_city) fails, that is, if Z is not in Passed_city.

这篇关于Prolog:图遍历中的处理周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！