1

我想在双向图中的序言中找到从 A 站到 B 站的最短路线（如果 A 连接到 B，而不是 B 连接到 A），该图在分支上没有权重。问题是这样发布的 

solve(Start,End,Path).

始发站。
终点站。
路径最短的所有站点的路径列表。图中任意两个直接相连的站点之间的距离相等。事实上，基地是这样的： 

fact("Staion1","metroline","Station2","metroline").

地铁线是直接连接两个车站的线路数。如果第 2 和第 4 个参数相同，则站直接连接。

line("Abbesses","12","Pigalle","12").  
line("Abbesses","12","Lamarck Caulaincourt","12").  
line("Ale'sia","4","Mouton Duvernet","4").  
line("Ale'sia","4","Porte d'Orle'ans","4").  
line("Alexandre Dumas","2","Philippe Auguste","2").  
line("Alexandre Dumas","2","Avron","2").  
line("Alma Marcesu","9","Ie'na","9").

编辑：我试图解决这个问题，我发现如果使用 BFS 会更快。
这是我写的解决方案： 

solve(Start,End,Path):-solve1([Start],End,[Start],Path).   

solve1([P|O],End,Visited,[End|?]):-children(P,S),member(End,S),!.   
solve1([P|O],End,Visited,Path):-(not(member(P,Visited)),children(P,S),append(O,S,O1),solve1(O1,End,Visited,Path));  
(solve1(O,End,Visited,Path)).

?-应该是到目标节点
的路径列表唯一的问题是我不知道如何返回到目标节点的路径。
谢谢在前面。

4

2 回答 2

0

您可以使用 Dijkstra 算法。

http://en.wikipedia.org/wiki/Dijkstra's_algorithm _

于 2010-12-11T12:37:33.843 回答
0

这就引出了一个问题，广度优先算法是否比深度优先算法有任何优势。无论如何，您都通过 member/2 谓词检测循环，因此不存在完整性问题。

假设我们有这个图，没有任何循环：

在此处输入图像描述

这可以在 Prolog 中表示为以下事实：

% edge(-Vertex, -Vertex)
edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

然后使用聚合函数表来完成这项工作：

% path(+Vertex, +Vertex, -Integer)
:- table path(_,_,min).
path(X, X, 0).
path(X, Y, N) :-
   edge(X, Z), path(Z, Y, M), N is M+1.

以下是一些示例运行：

?- path(a, e, X).
X = 2
?- path(a, e, 3).
No

您还可以修改代码，以便它检测循环和/或返回路径。对后者有帮助的是使用自定义聚合函数。

免责声明：出于实际目的，您不会使用归结为 Dijkstra 算法的东西。您宁愿使用A* 算法系列中的一些东西。

于 2019-06-21T10:34:35.520 回答