3-4启发式搜索策略.ppt

启发式搜索策略
启发信息和估价函数
局部择优搜索
全局择优搜索
A*算法
宽度优先、深度优先搜索属于盲目搜索(按规定的路线搜索)。盲目搜索效率低,耗费过多的计算空间与时间。
2. 若选择最有希望的节点加以扩展(NOT按规定的路线盲目搜索) ,则搜索效率将会大为提高。
Background and Questions:
. 1
As to fig., which one , the children A,B and C of S, would be hopeful to get goal or get goal with little cost?
Make choice For each step searching.
启发信息和估价函数
启发信息:
与具体问题求解相关的控制性知识。 Can make choice
Useful for searching solution.
bus debit cards for students or regular people
Blind searching is still useful in some cases.
估价函数: Expression of the useful information
估计OPEN表中各扩展节点的重要程度,给它们排定扩展次序。
4
定义评价函数/ 估计函数 f:
f(n)=g(n)+h(n)
其中n是被评价的节点。
g(n):表示从初始节点S到节点n的路径的代价;
h(n):表示从节点n到目标节点G的路径的代价;
f(n表示从初始节点S经过节点n到目标节点G的路径的代价。
33
…
n
11
定义一个评价函数 f
…
gn
hn
fn
33
…
xn
11
定义一个评价函数 f
…
gn
hn
fn
局部择优搜索
基本思想:
当一个节点扩展后, 在它的所有子节点中,选估价函数f(n)最优者作为下一个考察的节点。
例1 :用局部择优搜索策略求解八数码问题。

估价函数定义为f(n)= g(n)+h(n) 。
其中,
g(n)=d(n)表示搜索depth,等代价时, g(n)对局部择优搜索没有影响.
g(n) is same when searching among the children.
h(n) = w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。
So,
估价函数定义为f(n)= w(n) 。
例1 局部择优搜索树-1:
Compare No. cards not in the position
在它的所有子节点中,选估价函数f(n)最优者
等代价时, g(n)对局部择优搜索没有影响.
例1 局部择优搜索树-2: