我正在尝试编写一个Prolog程序，用于表示目标节点G，并返回从起始节点到目标节点的一系列节点列表，类似于get_path(StartNode, Path)这样的谓词。

我有一组节点，每个节点都有一个启发式值，还有一些从一个节点到另一个节点的 successor arcs，以及相应的成本。每个节点的启发式值如下：

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

而 successor arcs 和相关的成本是：

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).

我已经绘制了一张图表，展示了我可以采取的所有节点路线，因此我知道a->b->e->g和a->b->d->g是成本最低的路径，每条路径的总成本为8。然而，我不太确定应该编写什么样的谓词来处理这些信息并输出我需要的结果。我应该使用广度优先搜索吗？启发式值在解决方案中扮演什么角色？

任何帮助都将非常感激，谢谢。

回答：

我将提供一个遍历图的框架，希望你能在此基础上扩展，以利用相关的成本。这在Prolog中是一个非常常见的解决方案。这将直接回答主题问题，“如何从起始节点到目标节点获取路径”。

查询的形式将是：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]).   % 我已经到达我想去的地方path(Start, Destination, Visited, [Start|Nodes]) :-    \+ member(Start, Visited),    dif(Start, Destination),    s(Start, Node, _),       % 忽略成本    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 = aP = [a] ? ;D = bP = [a,b] ? ;D = dP = [a,b,d] ? ;...

如果你想查看一个节点的成本，你可以考虑h(Node, Cost)。你可以包含一个参数来包括路径的总成本（你希望如何计算它），并在每次通过path谓词调用时累积它。

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

这应该为你提供一个合理的起点。