反转循环图序言中的搜索

Question

我在 prolog 程序中遇到了这个问题，因为我是一个完全的初学者，我想我会来这里寻求一些答案或帮助。

这是我的数据库：

road(hoor,horby).
road(horby,lund).
road(horby,sjobo).
road(lund,sjobo).
road(sjobo,tomelilla).
road(sjobo,ystad).
road(tomelilla,ystad).
road(ronne,gudhjem).

那么这些是我的规则：

:- op(150, xfy, to).

X to Y :-
    findall(Waypoint, get_waypoints(X,Y,Waypoint), Waypoints),
    write(Waypoints).

get_waypoints(Start, End, []) :- 
    road(Start, End).
get_waypoints(Start, End, [Waypoint|Result]) :-
    road(Start, Waypoint),
    get_waypoints(Waypoint, End, Result).

当我问时它工作正常

?- horby to ystad.

然后输出变成：

[[lund,sjobo],[lund,sjobo,tomelilla],[sjobo],[sjobo,tomelilla]]
true.

太完美了。但是假设我想找到从 ?- ystad 到 horby 的路径。当我要求这个时，它只给我：

[]
true.

我可以采用哪些方法来解决这个问题？提前致谢！

Answer 1

双向使用道路

问题是你的道路是单向的。您需要同时使用它们。

您可以通过添加新规则来实现：

connected(X, Y):- road(X, Y) ; road(Y, X).

现在，如果您只是将 road(Start, Waypoint) 替换为 connected(Start, Waypoint)，您现在可以在所有方向上搜索，但是您的谓词 get_waypoints 将产生无限数量的解决方案，因为它可能会返回并返回穿梭于城市之间。

检查一个城市是否已经访问过

您需要检查您访问的城市是否以前没有访问过。您可以使用到目前为止您访问过的城市的列表（累加器）来做到这一点：

get_waypoints(Start, End, Waypoints):-
    get_waypoints(Start, End, [Start], Waypoints).

get_waypoints(Current, End, Acc, Waypoints):-
    connected(Current, End),
    reverse(Acc, [_|Waypoints]).

get_waypoints(Current, End, Acc, Waypoints):-
    connected(Current, Waypoint),
    Waypoint \== End,
    \+ member(Waypoint, Acc),
    get_waypoints(Waypoint, End, [Waypoint|Acc], Waypoints).

子目标 Waypoint \== End 确保一旦您到达目的地，您将不会在该路径上进一步构建。 \+ member(Waypoint, Acc) 确保您不会两次访问同一个城市。

因为你需要检查你是否没有return到起始城市，累加器也会包含它。这样一来，最后累加器取反的时候，第一个元素（起始城市）就被舍弃了：reverse(Acc, [_|Waypoints]).

查询示例

| ?- ystad to horby.
[[sjobo],[sjobo,lund],[tomelilla,sjobo],[tomelilla,sjobo,lund]]

yes

更新：在结果列表中包括开始和结束节点（在评论中要求）

要将起始城市和结束城市与 waypoints 一起包含在结果中，只需将 End 节点添加到 [=21= 的第一条规则中的累加器中即可]:

get_waypoints(Current, End, Acc, Waypoints):-
    connected(Current, End),
    reverse([End|Acc], Waypoints]).

反转循环图序言中的搜索

Reverse the search in cycle graph prolog

prolog