第3章产生式系统的搜索策略

第三章产生式系统的搜索策略

1状态空间搜索概述

2回溯策略

3图搜索策略

4盲目的图搜索过程

5启发式图搜索过程搜索空间示意图

搜索策略的任务:确定选择规则的方式两种基本方式：盲目搜索(无信息引导)：按固定的步骤启发式搜索(有信息引导)：考虑领域的知识状态空间：求任一解路：回溯、爬山、宽度、深度、限定范围搜索、好的优先搜索.求最佳解路：大英博物馆法、分支限界法、动态规划法、最佳图搜索法A*.问题归约：求与或图：一般求与或图搜索法AO*、极大极小法、α-β剪支法、启发式剪支法.1状态空间搜索概述

1.1图的概念

图是由节点及连接它们的弧的集合组成.

有向图.节点深度的表示：dn+1=dn+1路径：N个有序的节点序列中，若相邻的每对节点都表示一条弧，则称该序列为长度为N的一条路径.路径耗散值：令C（ni，nj）为节点ni到节点nj这段路径（或弧线）的耗散值，一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。递归公式：C（ni，t）=C（ni，nj）+C（nj，t）节点的扩展：操作算子（规则）作用到节点（某一状态）上，生成出其所有的后继节点（新状态），并给出解弧线的耗散值（规则代价）.1.2状态空间图描述的特点形式:最直观的，显式描述.对应关系:节点表示问题的状态弧表示状态之间的关系，即求解问题的步骤初始状态对应于问题的已知信息，是根节点寻找从一种状态转换为另一种状态的某个操作算子序列,就等价于在一个图中寻找从一种状态到另一种状态的一条路径.1.3状态空间的搜索

思想：将问题求解转换为状态空间的图搜索表示方法：定义一状态空间S（表示状态的数据结构）规定一个或多个属于该空间的初始状态S0规定一个或多个属于该空间的目标状态G规定一组规则O（状态转换的操作）目的：将非形式的问题描述转换成状态空间形式描述后，便可利用状态空间的搜索方法应用规则和控制策略（搜索技术），找出从初始状态到目标状态的一条（或一组）路径1.4搜索的概念及问题

在状态空间中，问题的求解就是搜索即通过搜索某部分状态空间,以求得由规则序列组成的一个解答的过程，它对应于将一个隐式图中包含目的节点的一部分状态变为显式图的过程搜索过程存在的几个基本问题：

1）有解?是否一定能找到一个解2）终止?是否能终止运行或陷入一个死循环3）最佳解?若找到解时，是否是最佳解4）代价?时间与空间复杂性如何

搜索过程的具体步骤：

从初始状态出发，并将它作为当前状态;扫描规则集合，挑选适用于当前状态的一些规则作用在其上而得到新的状态，并建立与父母节点的连接指针;检查所生成的新状态是否满足结束状态，如果满足，则得解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将这新状态作为当前状态，返回前一步再进行搜索.2回溯策略

含义:按规则的一个固定排序，系统地尝试状态空间中各种不同路径的技术.是一种盲目搜索.过程：从初始状态出发，不停地、试探地寻找路径,当遇到“死胡同”(无可用规则或规则都用完)就回溯到路径中最近的父节点上，查看该节点是否还有其他的子节点未被扩展，如有，则沿这些子节点继续搜索；如果找到目标，就成功退出搜索，返回解的路径.特征：呈现出递归的性质。求解过程在每个节点上的检查遵循着递归方式.

递归的思想从前有座山……

从前有座山……

从前有座山……递归过程示例：--阶乘函数的递归intfactorial(intn){if(n==1){return1;}else{returnn*factorial(n-1);}}

只要初始值大于零，这个函数就能够终止停止的位置称为基线条件，可返回一个结果递归必须至少拥有一个基线条件，且须确保最终会达到某个基线条件；一些符号的含义：变量：

DATA=当前状态；RULES=规则集合序列表；R=当前调用规则；RDATA=新生成的状态；PATH=当前解路径表常量：

NIL=空表；FAIL=回溯点标记；LOOP=循环标号；谓词：

TERM(DATA)；DEADEND(DATA)；NULL(RULES)；函数：APPRULES求可应用的规则表；FIRST从表中取表头的一个元素,TAIL除去表头一个元素后得到的新表；GEN调用规则生成新状态；CONS在表头插入新元素，构造新表；递归过程BACKTRACK(DATA)

BACKTRACK(DATA)ifTERM(DATA),returnNIL;满足终止条件ifDEADEND(DATA)returnFAIL;

不合法，须回溯RULES←APPRULES(DATA)可应用的规则表.LOOP:ifNULL(RULES)returnFAIL;

无可用规则，须回溯R←FIRST(RULES);选头条规则RULES←TAIL(RULES);删除该规则RDATA←GEN（R，DATA）;把R作用于当前状态PATH←BACKTRACK(RDATA)对新状态递归调用ifPATH=FAILgoLOOP;如递归失败，选另一规则returnCONS(R,PATH);否则把R加在解路径表中，过程返回解路径规则表（或局部解路径子表）.举例综合数据库：DATA=L（表），L元素用{ij}表示，i，j的值域为{1，2，3，4}。即L表的元素表示皇后所在的行和列。如（12243143）、（13213442）、（1121）、（1122）、（112331）.四皇后问题：在一个4*4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不能相互俘获.棋盘的几种状态

共16个规则，每条规则Rij表示满足前提条件下，在ij处放一个棋子.控制策略:若以R11、R12、R13、R14、R21、…、R44这种先行后列固定的排序方式调用递归时，搜索示意图如下图所示.

规则集：()Q(11)R11(*,21)R21Q①(*,22)Q②(*,23)Q(*,*,31)Q③(*,*,32)Q④(*,*,33)Q⑤(*,*,34)Q⑥⑦(*,24)Q(*,*,31)⑧(*,*,32)(*,*,*,41)Q⑨(*,*,*,42)Q⑩(*,*,*,43)Q⑾(*,*,*,44)Q⑿⒀(*,*,*,33)⒁(*,*,*,34)⒂⒃⒄(12)Q(*,21)⒅(*,22)⒆(*,23)⒇(*,24)(*,*,31)(*,*,*,41)(21)(*,*,*,42)(22)(*,*,*,43)四皇后问题的固定排序搜索树

思考：当规则序列以R11、R21、R31、R41、R12、R22、R32、…、R44这种“先列后行”固定排序方式调用BACKTRACK函数时，画出四皇后问题的搜索树，并标出所有回溯的先后顺序。与例题的搜索过程有何异同？这2种方法存在什么问题？思路：

利用问题有关信息对规则进行动态排序方法：定义一个对角线函数Maxdiag（i，j）。该函数计算棋盘上ij单元的最长对角线长度，通过比较不同单元的函数值来决定每行（列）Rij的排序例如，若Maxdiag（i，k）小于Maxdiag（i，j），则规则顺序为（Rik，Rij），即对角线短的单元，相应的规则排在前头，若相同，则维持原顺序排序结果：按此知识排列的序列为R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44（3、3、4、4……）四皇后问题的改进：

()(12)R12(12,21)R21①QQ(12,24)R24(12,24,31)(12,24,31,42)(12,24,31,43)②R31R42R43QQQQ

四皇后问题的动态排序搜索树顺序:R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44BACKTRACK(DATA)算法存在的问题:重复状态引起的死循环搜索深度无限改进策略：用状态链路变量DATALIST代替原状态变量DATA;设置出现重复状态的回溯点设置深度范围限制的回溯点BACKTRACK1(DATALIST):

1

DATAFIRST(DATALIST)参数:初始到当前状态的逆序表2ifMEMBER(DATA,TAIL(DATALIST),returnFAIL回老路3

ifTERM(DATA),returnNIL到达目标，成功返回4ifDEADEND(DATA),returnFAIL到达不合理状态，退回5

ifLENGTH(DATALIST)>BOUND,returnFAIL到深度限制6

RULESAPPRULES(DATA)得出可应用的规则集7

LOOP:ifNULL(RULES),returnFAIL进入死胡同，退回8

RFIRST(RULES)取出第一条可应用规则9

RULESTAIL(RULES)10RDATAGEN（R，DATA)运用规则，生成新状态11RDATALISTCONS(RDATA,DATALIST)12PATHBACKTRACK1(RDATALIST)递归13ifPATH=FAIL,goLOOP14returnCONS(R,PATH)如果当前状态S未达到目标，就对它的第一个子状态Schild1递归调用回溯过程。如果在以Schild1

为根的子图中未找到目标，就对它的兄弟子状态Schild2再递归调用回溯过程;像这样重复进行直到某个子状态的后裔是目的状态或者所有的子状态都搜索完为止。而且，如果S的子状态中没有一个能达到目标，便回溯到S的父状态，算法开始对S的兄弟状态进行搜索;算法以这种方式搜索直到找到目的状态或遍历了所有的状态空间为止.回溯过程总结：A1B2C8D11E3F6G9H10I4J5K7①②③④⑤⑥⑦⑧⑨⑩一个状态空间中应用回溯搜索的示意图优点：节省空间；缺点：回溯掉的部分无法复用.

3图搜索策略

一般的图搜索算法：1.

G:=G0(G0=s)，Open:=(s)；G表示图，s为初始节点，设置Open表，放待扩展的节点，最初只含s.2.

Closed:=()；设置Closed表,放已扩展完的节点，起始为空表.3.

LOOP:IFOpen:=()，THENEXIT(FAIL);4.

n:=FIRST(Open)，REMOVE(n,Open)，ADD(n,Closed);称n为当前节点.5.

IFGOAL(n)，THENEXIT(SUCCESS)；由n返回到s的路径上的指针,可给出解路径.如果控制系统保留了所有的规则应用后生成并连接起来的状态记录图，则称控制系统使用了图搜索策略.6.

EXPAND(n)→(mi),G:=ADD(mi,G)；（为实现无环路,子节点集{mi}中应不包含n的先辈节点.）7.

标记和修改指针（当出现多路径的情况，根据路径耗散值选择最好的解路,此时子节点分3种情况考虑{mi}={mj}∪{mk}∪{ml}）ADD(mj，Open),并标记mj连接到n的指针;若子节点（mj)为Open和Closed中未出现过的.计算是否要修改mk、ml到n的指针；若子节点已出现过，1）mk表示已出现在Open中的子节点，2）ml表示已出现在Closed中的子节点.计算是否要修改ml到其后继节点的指针；8．对Open中的节点按某种原则重新排序；9．GOLOOP；

学习重点：{mi}节点类型说明mjmkml12345已扩展过的节点(Closed)待扩展的节点(Open)，状态的排列次序就是搜索的次序s????扩展节点6得到的搜索图

具体示例（mk）：

实心圆点：Closed中节点空心圆点：Open中节点假设每段为单位耗散现在要扩展节点6，设生成两个子节点，其中节点4(mk)已在Open中;原路径（s→3→2→4）耗散值为5，新路径（s→6→4）耗散值为4，所以节点4的解路指针应修正（2→6），如图所示。

如果下一循环要扩展节点1，若节点1只生成一个子节点2(ml);

比较耗散值，显然要修改节点2的指针（3→1）;

由此又会引起节点4指针的修改（６→２），如图（b）所示。扩展节点1得到的搜索图

具体示例（续）：4盲目的图搜索过程

1)宽度优先搜索

搜索次序：一层一层地扩展下去，直到搜索到目的状态（如果目的状态存在）。√√√√√√√√√√√宽度优先搜索过程

Procedurebreadth_first_searchBegin

Open:=[start];closed:=[]*初始化

Whileopen≠[]do

Begin从Open表中删除第一个状态n,并放入closed中;

ifn=目的状态thenreturn(success);

else生成n的所有子状态;从中删除已在Open或closed中出现的状态;

*避免循环搜索;将其余子状态,按生成次序加入到Open表后端.

End;

End.23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654

八数码宽度优先搜索91011121314151617小结：宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法2)深度优先搜索

搜索沿一个方向一直扩展下去，直到达到一定的深度，如未找到目的状态或无法再扩展下去，便回溯到另一条路径继续搜索，若还没有找到目的状态或无法再扩展时，再回溯到另一条路径搜索……..。深度优先搜索法中的搜索次序√√√√√√√√√√√√√√Proceduredepth_first_searchBeginOpen:=[start];closed:=[]；d=深度限制值*初始化

WhileOpen≠[]doBegin

从Open表中删除第一个状态,并放入closed表中;ifn=目的状态thenreturn(success);elseifn的深度>dthencontinue;*回溯

else生成n的所有子状态;

从中删除已在Open或closed表中出现的状态;*避免循环搜索;

将其余状态,按生成的次序加入到Open表的前端.End;End.深度优先搜索过程：231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标八数码深度优先搜索12378466efd=3小结：深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法5启发式图搜索过程*

核心思想：利用所处理问题的启发信息引导搜索目的：减少搜索范围，降低问题复杂度.1)启发式图搜索算法A基本思路：定义一个评价函数f，对当前待搜索状态进行评估（既考虑从起始节点到节点n的花费，又考虑从节点n到达目标节点的费用），然后找出一个最有希望的节点来扩展.函数形式为：f(n)=g(n)+h(n).n为被评价的节点。用此函数值来排列OPEN表中节点顺序的图搜索算法称为A算法.

函数符号说明：g*(n)、h*(n)：表示各部分实际最短路径的耗散值.f*(n)=g*(n)+h*(n)：表示从S出发，通过节点n到目标节点g的最短路径的耗散值.f(n)、g(n)和h(n)为相应路径耗散值的估计值，是一种预测。A算法就是利用这种预测，来达到有效搜索的目的.g（n）可根据搜索历史情况对g*（n）作出估计，显然有g（n）>=g*（n）.h（n）则依赖于启发信息，通常称为启发函数，是要对未来扩展的方向作出估计.1.OPEN:=(s)，f(s):=g(s)+h(s);

2.LOOP:IFOPEN=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.

REMOVE(n,OPEN),ADD(n,CLOSED);

6.EXPAND(n)→(mi)，把mi作为n的后继节点添入G，并计算f(n-mi)=g(n-mi)+h(mi)；

ADD(mj,OPEN)，

IFf(n-mk)<f(mk)THENf(mk):=f(n-mk)，

IFf(n-ml)<f(ml)THENf(ml):=f(n-ml)，

ADD(ml,OPEN);7.OPEN中的节点按f值从小到大排序;8.

GOLOOP;算法的说明：A算法由一般的图搜索算法改变而成.控制策略:

按照f（n）值递增的顺序对OPEN中的元素进行排序，f（n）值小的节点排在前面，大的放在OPEN表的后面.效果:

每次扩展节点时，优先选择当前f（n）值最小的节点来扩展.结论:算法A是一个好的优先搜索策略.扩展n后新生成的子节点m1({mj})、m2({mk})、m3({ml})分别计算其评价函数值：

f(m1)=g(m1)+h(m1)f(n,m2)=g(n,m2)+h(m2)f(n,m3)=g(n,m3)+h(m3)按第6步比较不同路径的耗散值并进行相应的指针修正.snf(n)m2m3m31m32f(m3)m1f(m1)f(m2)f(m31)f(m32)搜索示意图八数码问题具体事例

：设评价函数f（n）形式如下：

f（n）=d（n）+W（n），其中,d（n）代表节点的深度，即取g（n）=d（n），表示讨论单位耗散的情况；而取h（n）=W（n）表示以“不在位”的将牌个数作为启发函数的度量；

f（n）可估计出通向目标节点的希望程度.2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456OPEN表：初始化（s（4））（B（4）A（6）C（6））（D（5）E（5）A（6）C（6）F（6））（E（5）A（6）C（6）F（6）G（6）H（7））（I（5）A（6）C（6）F（6）G（6）H（7）J（7））（K（5）A（6）C（6）F（6）G（6）H（7）J（7））（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循环结束在第4步成功退出CLOSED表：（）（s（4））（s（4）B（4））（s（4）B（4）D（5））（s（4）B（4）D（5）E（5））（s（4）B（4）D（5）E（5）I（5））（s（4）B（4）D（5）E（5）I（5）K（5））2)爬山法

过程：Hill-climbing1）n：=s；s为初始节点2）LOOP：IFGOAL（n）THENEXIT（SUCCESS）3）EXPAND（n）→{mi}，计算h（mi），

next_n：=m（minh（mi）的节点）；4）IFh（n）<h(next_n)THENEXIT(FAIL);5）n:=next_n；6）GOLOOP；显然如果将山顶作为目标，f（n）=h（n）就表示山顶与当前位置的高度之差，则算法总是力图登向山顶，在单峰的情况下，必能到达山峰.3)分支限界法

思想：从路径表中，优先扩展当前具有最小耗散值分支路径的叶节点n，评价函数为f（n）=g（n）.过程Branch-Bound1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，计算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路径g值最小者排在前面；7）GOLOOP；例：八城市地图网

最短路径问题的求解SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613分支限界法的搜索树

初始（s（0））1A（3）D（4）2D（4）B（7）D（8）3E（6）

B（7）D（8）A（9）4B（7）D（8）A（9）F（10）B（11）5D（8）A（9）F（10）B（11）C（11）E（12）6A（9）F（10）E（10）

B（11）C（11）E（12）7F（10）E（10）B（11）C（11）E（12）B（13）8E（10）B（11）C（11）E（12）t（13)B（13）9B（11）C（11）E（12）t（13）B（13）F（14）B（15）10C（11）E（12）t（13）B（13）F（14）B（15）A（15)C（15）11E（12）t（13）B（13）F（14）B（15）A（15）C（15）12t（13）B（13）F（14）D（14）B（15）A（15）C（15）F（16）13）结束.

4)动态规划法

分支限界的缺点：第2循环扩展A（3）后生成的D（8）节点（D（4）已在QUEUE上）和第3循环扩展D（4）之后生成的A（9）节点（A（3）已在QUEUE上）都是多余的分支。因为由s-D(或s-A)到达目标的路径显然要比s-A-D(或s-D-A)到达目标的路径要好.改进思路：如果能够删去类似s-A-D或s-D-A这样一些多余的路径，将会大大提高搜索效率.动态规划原理：求s→t的最佳路径时，对某个中间节点I，只要考虑s到I中具有最小耗散值这一条局部路径就可以，其余s到I的路径是多余的.

具有动态规划原理的分支限界算法过程Dynamic-Programming1）QUEUE：=（s-s），g（s）=0；

2）LOOP：IFQUEUE：=（）THENEXIT（FAIL）；

3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；

4）IFGOAL（n）THENEXIT（SUCCESS）；

5）EXPAND（n）→{mi}，计算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；

6）QUEUE中有多条到达某一公共节点的路径，则只保留耗散值最小的那条路径，其余删去，并重新排序，g值最小者排在前面；

7）GOLOOP；SAD1g=0g=3g=42BDg=7g=8×3AEg=9g=6×4BFg=11g=10×5ECg=11g=12×6tg=13动态规划原理的搜索树

785)最佳图搜索算法A*

在算法A中，当h（n）≤h*（n）时，称其为A*算法.A*算法具有如下的性质：完备性：如果问题有解，则算法一定能找到解.(定理1.1、1.2)可采纳性：如果问题有解，则算法一定能找到最佳解。即算法总能找到一条从S到目标节点的最佳路径.(定理1.3)最优性：设A1和A2为某问题求解的两个A*算法，若对所有非目标节点均有h1（n）〈h2（n）≤h*（n）则算法A1展开的节点数目至少和A2一样多。（启发函数和A*算法的关系）(定理1.4)5)最佳图搜索算法A*(续)

通过对这几条性质的证明(定理）可得到几个有助于理解A*算法的结论：A*算法结束前，OPEN表中必存在f（n）≤f*（S）的节点（n是在最佳路径上的节点）(引理1.2)OPEN表上任一具有f（n）≤f*（S）的节点n，最终都将被A*选作扩展的节点.(推论1.1)A*选作扩展的任一节点，有f（n）≤f*（S）.(推论1.2)最优性的示例说明:A*中启发信息的作用.

例、比较给定各节点h2（n）值的A*算法与h1（n）≡0的A*算法，所求得最佳路径时扩展的节点数大小

启发函数h（n）的效果比较√f=0√f=4√f=5√f=6√f=7√f=7√f=7√f=7√f=7√f=7√f=7√f=7√f=8√f=8f=9f=9f=10f=9h=7h=5h=4h=2h=3h=3h=3h=3h=3h=1h=2h1（n）≡

0时OPEN和CLOSED表的元素排列如下：S(0)A(4),B(5),C(6)B(5),C(6),D(7),E(7),F(7)C(6),D(7),E(7),F(7),H(7),I(7)D(7),E(7),F(7),H(7),I(7),J(7),K(7)E(7),F(7),H(7),I(7),J(7),K(7),t1(11),t2(11)F(7),H(7),I(7),J(7),K(7),t1(11),t2(11),t3(11)H(7),I(7),J(7),K(7),t1(11),t2(11),t3(11),t4(11)I(7),J(7),K(7),t1(11),t2(11),t3(11),t4(11),t5(11)J(7),K(7),t1(11),t2(11),t3(11),t4(11),t5(11),t6(11)K(7),t7(8),t6(9),t1(11),t2(11),t3(11),t4(11),t5(11)t7(8),t6(9),t8(10),t1(11),t2(11),t3(11),t4(11),t5(11)()S(0)S(0),A(4)S(0),A(4),B(5)S(0),A(4),B(5),C(6)S(0),A(4),B(5),C(6),D(7)S(0),A(4),B(5),C(6),D(7),E(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7),J(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7),J(7),K(7)h2（n）不为0时，OPEN和CLOSED表的元素排列如下：S(7)C(8),A(9),B(9)J(8),A(9),B(9),K(9),I(10)t7(8),A(9),B(9),K(9),t6(9),I(10)()S(7)S(7),C(8)S(7),C(8),J(8)存在的问题:如果用扩展节点数作为评价搜索效率的准则，那么可以发现A算法第6步中，对CLOSED表中ml类节点要重新放回OPEN表中的操作，将引起多次扩展同一节点的可能.不良结果:即使问题所包含的节点数少，但重复扩展某些节点，也将导致搜索效率下降.

A*的不足及其改进:A*算法多次扩展同一节点的搜索图例子OPEN表CLOSED表0.s(20)()1.A(12)B(13)C(14)D(15)s(20)2.B(13)C(14)D(15)t(29)s(20)A(12)3.A(11)C(14)D(15)t(29)s(20)B(13)4.C(14)D(15)t(28)s(20)B(13)A(11)

5.A(10)B(11)D(15)t(28)s(20)C(14)6.B(11)D(15)t(27)s(20)C(14)A(10)

7.A(9)D(15)t(27)s(20)C(14)B(11)8.D(15)t(26)s(20)C(14)

B(11)

A(9)9.A(8)B(9)C(10)

t(26)s(20)D(15)10.B(9)C(10)

t(25)s(20)D(15)

A(8)11.A(7)C(10)

t(25)s(20)D(15)B(9)12.C(10)

t(24)s(20)D(15)

B(9)

A(7)13.A(6)B(7)t(24)s(20)D(15)C(10)14.B(7)t(23)15.A(5)t(23)s(20)D(15)

C(10)

A(6)s(20)D(15)

C(10)

B(7)16.t(22)s(20)D(15)C(10)

B(7)

A(5)17.成功结束

问题:从CLOSED表看出，在修改ml类节点指针的过程中，节点A、B、C被重复扩展，次数分别为8、4、2，共扩展16次节点（步）.

原因:在前面的扩展中，并没有找到从初始节点到当前节点的最短路径.

解决的途径:(1)对h加以限制:使得第一次扩展一个节点时，就找到了从s到该节点的最短路径.(2)对算法加以改进:避免或减少节点的多次扩展.定义:一个启发函数，如果对所有节点ni和nj（nj是ni的子节点），都有:h(ni)-h(nj)C(ni，nj)(节点间的估计值实际值）且h(ti)=0

或

h(ni)C(ni，nj)+h(nj)且，

h(ti)=0则称启发函数h满足单调限制条件.

h(ni)ninjh(nj)c(ni,nj)(1)对h加以限制ti定理5若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径.

即：当A*选n扩展时，有g(n)=g*(n).定理6若h(n)是单调的，则由A*所扩展的节点序列,其f值是非递减的,即f(ni)≤f(nj)。效果:由于扩展节点后，即是最佳路径，因此不必进行指针纠正操作，故改善了A*效率.h单调的性质(2)对算法加以改进改进的理论基础及应用思路：推论1.1OPEN表上任一具有f(n)<f*(s)的节点定会被扩展.1)按f*(s)值可将OPEN表中的节点分为两部分:一部分节点必须扩展(NEST={n|f(n)<f*(s)}).2)为避免重复节点的扩展,需保证h的单调性,而h≡0是单调的,故在NEST中可按f(n)=g(n)对节点进行扩展.推论1.2A*扩展的任一节点，定有f(n)≤f*(s).

尽管f*(s)未知,但通过近似(在扩展过的节点中找最大的f(n)→f*(s),找了一个下界)可得到NEST的一个子集.改进思路的图示OPEN=(…………)f*(s)f<f*(s)的节点(NEST子集)f>=f*(s)的节点1)f*(s)?fm：到目前为止已扩展节点的最大

f值，用fm代替f*(s)2)NEST中的节点:按f(n)=g(n)进行排序具有修正过程的A*算法：OPEN:=(s)，f(s):=g(s)+h(s)=h(s)，fm:=0;LOOP：IFOPEN=（）THENEXIT（FAIL）；NEST：={ni|f（ni）＜fm}；*NEST给出了OPEN表中满足f＜fm的节点集合。fm为处理过的节点中最大的f值*.(划分OPEN表)

IFNEST≠

（）THENn：=ni（min（gi））ELSEn:=FIRST(OPEN)，fm=f（n）；*NEST不空时，取其中g(n)的最小者作为当前要扩展的节点，否则取OPEN的第一个为当前要扩展的节点*(保证搜索效率)4.~8.同过程A。OPEN表CLOSED表0.s(0+20)()1.A(11+1)B(9+4)C(6+8)D(1+14)s(0+20)2.A(7+1)B(5+4)C(2+8)s(0+20)D(1+14)3.A(5+1)B(3+4)s(0+20)D(1+14)C(2+8)

4.A(4+1)5.t(22+0)fm

成功结束02020202020s(0+20)D(1+14)C(2+8)B(3+4)

s(0+20)D(1+14)C(2+8)B(3+4)

A(4+1)

★★★★★★226)A*算法应用举例：1.八数码问题1）如果定义评价函数为f(n)=d(n)+w(n)，h(n)=w(n)定义为“不在位”的将牌个数;是否为A*算法？条件的判断:尽管我们不能确切知道h*(n)，但根据“不在位”将牌个数的估计，就能得出至少需要移动w(n)步才能达到目标，显然有h(n)=w(n)h*(n).28316475S（4）；g=0；h=428316475283147652831647528314765231847652831476528371465832147652318476523184765123847651238476512378465A（6）；g=1；h=5B（4）；g=1；h=3C（6）；g=1；h=5D（5）；g=2；h=3E（5）；g=2；h=3F（6）；g=2；h=4G（6）；g=3；h=3H（7）；g=3；h=4I（5）；g=3；h=2J（7）；g=3；h=4K（5）；g=4；h=1L（5）；g=5；h=0M（7）；g=5；h=22）定义f(n)=d(n)+p(n)，p(n)定义为每个将牌与其目标位置之间最短距离的总和.条件判断:同样,由于至少需要p(n)步才能达到目标，因此，也满足h(n)h*(n).下图给出了h(n)=p(n)的搜索图，并标出了相应的启发函数值。由解路可给出g*（n）和h*（n）的值，在最佳路径上的节点有f*=g*+h*=5.28316475S（5）；W=4；p=52831647528314765283164752831476523184765283147652318476523184765123847651238476512378465A（7）；w=5；p=6B（5）；w=3；p=4C（7）；w=5；p=6D（7）；w=3；p=5E（5）；w=3；p=3F（7）；w=4；p=5G（5）；w=2；p=2H（7）；w=4；p=4I（5）；w=1；p=1J（5）；w=0；p=0K（7）；w=2；p=2

对比小结:

上表为应用不同启发函数，求最佳解时的情况.实验现象:函数p（n）的搜索效果最好,w（n）次之,h(n)=0最差.结论:启发式函数选取的好坏，直接影响搜索效果.2.M-C问题

（missionaryandcannibal）问题:有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供k人乘渡，问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士数目（当传教士和野人共存时）.约束条件:在传教士和野人从左岸全部摆渡到右岸的过程中，1)在共存的任何时候均满足M≥C，2)在摆渡过程中,M+C≤k.设N=5，k=3，则该问题可用上图表示，图中L和R表示左岸和右岸，B=1或0分别表示有船或无船。约束条件是：两岸或船上M≥C，且船的容量M+C≤3。综合数据库：用三元组表示，即（ML，CL，BL），其中，0≤ML，CL≤5，BL=0or1，问题被简化为（5，5，1）→（0，0，0）规则集合：由两种摆渡操作组成：Pmc（从左岸到右岸）和qmc（从右岸到左岸），每次摆渡操作，船上合理人数的组合数乘以2，就是规则数.形式如：

if（ML，CL，BL=1）then（ML-1，CL，BL-1）；（P10）

if（ML，CL，BL=1）then（ML，CL-1，BL-1）；（P01）

if（ML，CL，BL=1）then（ML-1，CL-1，BL-1）；（P11）

if（ML，CL，BL=1）then（ML-2，CL，BL-1）；（P20）

…

…

（P30，P21，P02，P03）

if（ML，CL，BL=0）then（ML+1，CL，BL+1）；（q10）

if（ML，CL，BL=0）then（ML，CL+1，BL+1）；（q01）

if（ML，CL，BL=0）then（ML+1，CL+1，BL+1）；（q11）

if（ML，CL，BL=0）then（ML+2，CL，BL+1）；（q20）

…

…（q30，q21，q02，q03）控制策略：建立系统描述后，就要确定规则选取策略，以完成对状态空间的搜索，求得一个摆渡操作序列。思路:利用M和C的线性组合，以及有船与否来作为启发函数的基本分量。方法:1)h（n）=0;2)h（n）=M+C;3)h（n）=M+C-2B.图3-21给出了三种启发函数的搜索图（假定为单位耗散）,下表为各自的搜索情况.h（n）=0的搜索图即为该问题的状态空间图；h（n）=M+C不满足h（n）≤h*（n）；h（n）=M+C-2B可满足