Prolog：如何获得从起始节点到目标节点的路径

Question

我正在尝试编写一个序言程序，它将代表一个目标节点 G 并将 return 来自谓词的节点列表 get_path(StartNode, Path)从起始节点到目标节点。

我有一组节点，每个节点都有一个启发值，一些从一个节点到另一个节点的后继弧，以及这样做的成本。每个的启发值是：

h(a,12).
h(b,8).
h(c,4).
h(d,3).
h(f,5).
h(e,5).
h(g,0).

后继弧和相关成本为：

s(a,b,3).
s(a,c,6).
s(b,d,4).
s(b,e,2).
s(d,e,2).
s(d,g,1).
s(e,g,3).
s(c,e,5).
s(c,f,4).
s(f,g,7).

我有 drawn out a chart 映射我可以采用的所有节点路线，因此我知道 a->b->e->g 和 a->b->d->g 都是我可以遵循的最便宜的路径，每条路径都有总费用8。然而，我只是不完全确定我应该编写什么样的谓词来接收这些信息以及输出我需要的结果。我使用广度优先搜索吗？启发式值在何处与解决方案一起发挥作用？

非常感谢任何帮助，谢谢。

Answer 1

我将提供一个遍历图形的框架，希望您可以扩展它以利用相关成本。这是 Prolog 中非常常见的解决方案。这将直接回答主题问题，"How to get a path from a start node to a Goal Node".

查询的形式为：path(Start, Destination, Path)。我需要起点和终点来确定特定路径，因此 get_path(StartNode, Path) 的建议是不够的，因为它不表示终点。如果希望保留终点变量，可以查询，例如path(a, Destination, Path)，它会提供各种具体的Destination实例化的解决方案。

该方法将包括一个新的辅助变量来跟踪访问过的节点。这是为了避免循环。这也将假设一个有向图（原始问题中未阐明的一点），因此如果我有弧 s(a,b,3)，那么就有一条从 a 到 b 的路径，成本为3，但这并不意味着存在从 b 到 a 的路径。

path(Start, Destination, Path) :-
    path(Start, Destination, [], Path).

path(Start, Start, _, [Start]).   % I'm already where I want to be
path(Start, Destination, Visited, [Start|Nodes]) :-
    \+ member(Start, Visited),
    dif(Start, Destination),
    s(Start, Node, _),       % Ignoring cost
    path(Node, Destination, [Start|Visited], Nodes).

所以你可以这样查询，比如查找从a到g的路径：

| ?- path(a, g, Path).

Path = [a,b,d,e,g] ? ;

Path = [a,b,d,g] ? ;

Path = [a,b,e,g] ? ;

Path = [a,c,e,g] ? ;

Path = [a,c,f,g] ? ;

(15 ms) no
| ?-

您也可以尝试更一般的查询：

| ?- path(a, D, P).

D = a
P = [a] ? ;

D = b
P = [a,b] ? ;

D = d
P = [a,b,d] ? ;
...

如果你想看一个节点的成本，你会考虑，h(Node, Cost)。您可以包含一个参数以包含路径的总成本（无论您希望如何计算它）并通过 path 谓词调用在每次递归中累加它。

我知道在对原始问题的评论中，我说过您可以使用弧线列表来描述路径，哪一个都可以，但在这种情况下，我选择了节点。它们是同构的。

这应该给你一个合理的起点。

Answer 2

我想我可能已经解决了，感谢@lurkers 的帮助。

goal (g).
get_path (StartNode,Path) :- path (Start,g,[],Path).

path (Start,Start,_,[Start]).

path (Start,g,Visited,[Start|Nodes]):-
  \+member (Start,Visited),
 dif (Start, g),
 s(Start, Node,_),
 path (Node,g,[Start|Visited],Nodes).

Prolog：如何获得从起始节点到目标节点的路径

Prolog: How to get a path from a start node to a Goal Node

search

artificial-intelligence

predicate

prolog

nodes