使用启发式值贪婪搜索prolog

Question

我有一个图表和一个启发式表，列表连接和节点值以及成本（启发式表）。

图：

启发式表：

他们在prolog中的代表如下。

s(a,b,2).
s(a,c,1).
s(b,e,4).
s(b,g,2).
s(c,d,1).
s(c,x,3).
s(x,g,1).

h(a,9)
h(b,3)
h(c,2)
h(d,8)
h(e,4)
h(g,0)
h(x,2)

我的查询，如何使用启发式值h（a，9）执行贪婪搜索，以在每次迭代中查找下一个节点。

我知道如何使用DFS获取最短路径并使用列表存储该路径。我不知道如何在每个节点上考虑启发式值以在贪婪的搜索中考虑到这一点 - 我知道它扩展了最低的h值节点，以找到它的下一个邻居。

DFS：

depthfirstsearch(GoalN,Path,[GoalN|Path]) :- goal(GoalN).

depthfirstsearch(Node,Path,Solution) :- s(Node,NextNode,_), \+member(NextNode,Path), 
depthfirstsearch(NextNode,[Node|Path],Solution) 

当我搜索SO和网络（查找关于贪婪搜索如何工作的注释）但没有解释它如何使用prolog代码实际工作。它解释了如何在java，C++等中执行此操作，但我没有使用这些语言。

谁能让我朝着正确的方向前进？我读到了一些可以使用的地方吗？但是如何将启发式值与节点相结合，例如节点“B”，成本为2，从A到B.我用2的成本替换，启发式值/成本为3.请在更多中解释详细或指导我另一个现在有益的资源？

我可以创建一个谓词来帮助在每次迭代中找到下一个节点（当然使用启发式值）？

请记住，我是prolog的初学者，并尝试各种方法，但努力将它们拼凑在一起。

更新：这个link是我找到大部分搜索信息的地方

Answer 1

我想你需要知道什么是启发式值以及如何在搜索算法中使用它。

在我的回答中：

• n是我们想要达到的节点
• s是源节点
• h()是启发式功能。 h(n)是一个可接受的(?)值，我更倾向于认为从源n到达s的估计成本。只有在没有安全地高估成本的情况下，我们才称之为启发式优势。
• w(a,b)是从a到b的实际成本
• g()是一个函数，通过总结n给s节点w(a,b)的实际成本，其中a和b都是从n到s的路径中的节点。

现在回答你的问题，AFAIK你可以用两种方式使用这种启发式方法：

• 正如您所说，您可以懒惰地忽略w(a,b)值并使用h(b)值对后继节点进行排序（其中b是任何后继节点） - 这称为最佳第一搜索算法
• 另一种方法是基于值

  h(b) +
  g(b)

  （其中b是任何后继节点）对后继节点进行排序 - 这称为A *搜索算法。

推荐阅读：

• Stuart J Russell和Peter Norvig， - 人工智能 - 现代方法，第三版
• Ivan Brakto， - 人工智能的原理编程，Pearson Education，2011年8月。

附： findall是在prolog中用于实现这两个搜索的正确选择。