文档介绍：第二章产生式系统的搜索策略
本章主要内容:
回溯策略算法
图的搜索策略*
启发式图搜索(A算法*,爬山法,分支界限法,动态规划法*,A*算法*)
(*为重点内容)
无信息引导:不考虑知识,按事先排好的固定顺序,依次或随机调
两种基本方式: 用规则(盲目)。
有信息引导(启发式):根据该领域知识(动态确定规则排序),优
先调用较合适的规则。
求任一解的搜索策略
目前常用的策略: 求最优解的搜索策略
求与或关系组图的搜索策略
回溯策略
呈递为性质
例:四皇后问题
综合库:DATA=L(表),L的元素∈( i ,j)
如
(12,24,31,43)
规则集:if 1≤i≤4,且length(DATA)=i-1 then Append(DATA(i,j))。
共16条,Rij表示满足前提条件,在i,j处放一棋子。
控制策略①:按固定顺序R11 ,R12……R43,R44调用BACKTRACK时,(共
回溯22次,得到解组R12 ,R24,R31,R43)。
控制策略②:利用知识对规则排序(用对角线函数diag(i,j)计算过(i,j)点的对角
线长度),得到规则序列R12,R13,R11 R14,R21 R24 R22 R23,R31 R34 R32 R33,R42R43R41R44。
(只回溯2次)。
图搜索策略
若控制系统保留所有规则应用后生成并连接起来的状态记录图,则称为使用了图
搜索策略。
术语回顾:①节点深度:根节点为0,其它节点为父节点深度加1。
②路径:若节点序列(n0,n1,…,ni,…,nk),每个ni都有一个后继节点
ni+1,则该节点序列称为n0—nk的一条路径。
③路径耗散值:为路径上各节点间连线耗散值的总和。
C(ni,t)=C(ni,nj)+C(nj,t)
ni—t的路径的耗散值。
④扩展一个节点:对当前节点生成所有后继节点,并给出连接弧线的耗散。
一般图搜索算法:P58
其中:G : 搜索图
open : 练扩展节点表
closed : 已扩展节点表
{mi} : 当前节点的子节点集(={mj}∪{mk}∪{ml})
mj : open和closed中未出现过的子节点(新节点) 对于树不会出现如下
mk : 已出现在open中的子节点节点
ml : closed中的子节点
简例:P59 ←例
1. 深度优先
启发式搜索过程
搜索中,对open表进行排序,使最有希望通向目标节点的待扩展节点优先扩展。
①节点处在最优路径上的概率
建立节点评价函数f:
或②节点与目标节点之间的距离或差异度量
1. 启发式搜索算法A
利用评价函数,评价节点通向t的希望程度,来排列open表节点。
f(n,mi)=g(n,mi)+h(mi)
其中:f(n,mi):从S通过n,mi 到目标t的耗散估计;
g(n,mi):从S通过n到mi的耗散(能准确计算); 越小,近路
h(mi) :从mi 到目标节点的最小耗散估计。越小离目标越近
例:P65 八码问题:
设评