启发式搜索策略.ppt

P94 :
设计要求
给出搜索图,包括局部择优与全局择优,并在图中标示出搜索顺序标号,f(n),g(n),h(n)取值
设计相应算法实现所需要的数据结构、函数(在数据结构中已有的标准算法中选择)
给出局部择优与全局择优的流程图
2中的设计应对应局部择优与全局择优的流程图
提示
启发式函数为W左边B的个数,h(n)=m × W左边B的个数,m=1,2,3…,m为h(n)在本f(n)中的权重
耗散值为代价数值,即g(n)
启发式搜索策略
启发信息和估价函数
局部择优搜索
全局择优搜索
A*算法
宽度优先、深度优先搜索属于盲目搜索(按规定的路线搜索)。盲目搜索效率低,耗费过多的计算空间与时间。
Background & Questions: .-1
. 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.
2. 若选择最有希望的节点加以扩展(NOT按规定的路线盲目搜索) ,则搜索效率将会大为提高。
启发信息和估价函数
启发信息:
与具体问题求解相关的控制性知识。 Can make choice
Useful for searching solution.
.-2 bus debit cards for students or regular people
Blind searching is still useful in some cases.
估价函数: Expression of the useful information
启发信息的量化表示, 据此可估计OPEN表中各扩展节点的重要程度,给它们排定扩展次序。
5
定义评价函数/ 估计函数 f:
f(n)=g(n)+h(n)
其中n是被评价的节点。
g(n):表示从初始节点S到节点n的路径的代价;
h(n):表示从节点n到目标节点G的路径的代价;
f(n表示从初始节点S经过节点n到目标节点G的路径的代价。
g(n):cost paying already for searching
h(n):cost evaluation in further searching
f(n) : cost evaluation in searching along the rout
.-3 part of searching graph
33
…
n
11
定义一个评价函数 f
11 is start, 33 is goal
n is current node or searching n, now
A rout From11 to 33
Which is g?
Which is h?
…
gn
hn
fn
局部择优搜索
基本思想:
当一个节点扩展后, 在它的所有子节点中,选估价函数f(n)最优者作为下一个考察的节点。

. illustrate the basic idea by shopping
make the best choice among a certain area
例1 :用局部择优搜索策略求解八数码问题。
Understand what f(n), g(n) and h(n) mean

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