使用启发式值在序言中进行贪婪搜索
Greedy search in prolog using heuristic value
我有一个图表和一个启发式算法 table,其中包含一个列表连接和节点值以及成本(启发式算法 table)。
图表:
启发式table:
它们在序言中表示如下。
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++
等语言中解释了如何执行此操作,但我没有使用这些语言。
谁能告诉我正确的方向?我在某处读到可以使用 findall?但是我如何将启发式值组合到节点,例如从 A 到 B 的成本为 2 的节点 "B"。我是否将成本 2 替换为启发式 value/cost 3。请更详细地解释或指导我到另一个现在有用的资源?
我也许可以创建一个谓词来帮助在每次迭代中找到下一个节点(当然使用启发式值)?
请记住,我是 prolog 的初学者,正在尝试各种方法,但很难将它们拼凑在一起。
更新:这个link是我找到大部分搜索信息的地方
我认为您需要了解什么是启发值以及如何在您的搜索算法中使用它。
我的回答是:
n
是我们要到达的节点
s
为源节点
h()
是启发式函数。 h(n)
是可以接受的 (?)
价值,我更愿意将其视为达到 n
的 估计成本
来自来源 s
。只有当它不安全时,我们才称之为启发式好
高估了成本。
w(a,b)
是从 a
到 b
的实际成本
g()
是一个函数,给出 实际成本 从 s
到达节点 n
通过总结 w(a,b)
其中 a
和 b
都是路径中的节点
n
到 s
.
现在回答你的问题,AFAIK 你可以通过两种方式使用这个启发式:
如您所说,您可以懒惰地忽略 w(a,b)
值并使用
h(b)
值对后继节点进行排序(其中 b
是任何后继节点
node) -- 这叫做best first search算法
另一种方法是根据值 h(b) +
g(b)
对后继节点进行排序(其中 b
是任何后继节点)——这称为 A*
搜索算法。
推荐阅读:
Stuart J Russell 和 Peter Norvig,“人工智能 - 现代方法,第三版
Ivan Brakto,―Prolog 人工智能编程,培生教育,2011 年 8 月。
P.S。 findall
是在 prolog 中用来实现这两个搜索的正确方法。
我有一个图表和一个启发式算法 table,其中包含一个列表连接和节点值以及成本(启发式算法 table)。
图表:
启发式table:
它们在序言中表示如下。
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++
等语言中解释了如何执行此操作,但我没有使用这些语言。
谁能告诉我正确的方向?我在某处读到可以使用 findall?但是我如何将启发式值组合到节点,例如从 A 到 B 的成本为 2 的节点 "B"。我是否将成本 2 替换为启发式 value/cost 3。请更详细地解释或指导我到另一个现在有用的资源?
我也许可以创建一个谓词来帮助在每次迭代中找到下一个节点(当然使用启发式值)?
请记住,我是 prolog 的初学者,正在尝试各种方法,但很难将它们拼凑在一起。
更新:这个link是我找到大部分搜索信息的地方
我认为您需要了解什么是启发值以及如何在您的搜索算法中使用它。
我的回答是:
n
是我们要到达的节点s
为源节点h()
是启发式函数。h(n)
是可以接受的 (?) 价值,我更愿意将其视为达到n
的 估计成本 来自来源s
。只有当它不安全时,我们才称之为启发式好 高估了成本。w(a,b)
是从a
到b
的实际成本
g()
是一个函数,给出 实际成本 从s
到达节点n
通过总结w(a,b)
其中a
和b
都是路径中的节点n
到s
.
现在回答你的问题,AFAIK 你可以通过两种方式使用这个启发式:
如您所说,您可以懒惰地忽略
w(a,b)
值并使用h(b)
值对后继节点进行排序(其中b
是任何后继节点 node) -- 这叫做best first search算法另一种方法是根据值
h(b) + g(b)
对后继节点进行排序(其中b
是任何后继节点)——这称为 A* 搜索算法。
推荐阅读:
Stuart J Russell 和 Peter Norvig,“人工智能 - 现代方法,第三版
Ivan Brakto,―Prolog 人工智能编程,培生教育,2011 年 8 月。
P.S。 findall
是在 prolog 中用来实现这两个搜索的正确方法。