第一章搜索问题

第一章搜索问题

搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。

1内容： 状态空间的搜索问题搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。2基本概念1.什么是搜索？

根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的求解路线，使问题得到圆满解决的过程称为搜索。2.盲目搜索盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。3基本概念

启发式搜索是在搜索中加入了与问题有关的启发式信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。

3.启发式搜索

由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索优于盲目搜索。但由于启发式搜索需要具有与问题本身特性有关的信息，而这并非对每一类问题都可方便地抽取出来,因此盲目搜索仍不失为一种应用较多的搜索策略。

41.1状态空间表示法

状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中“状态”用以描述问题求解过程中不同时刻的状况；“算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换为另一种状态。当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。

51.状态

状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量或多维数组Sk=(Sk0,Sk1,…,Skn)表示，当给每个分量以确定的值时，就得到了一个具体的状态。2.算符

引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。操作可以是一个机械的步骤、过程、规则或算子，指出了状态之间的关系。63.状态空间

由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：（S,F,G）其中S是问题求解过程中所有可达的合法状态构成的集合；F是算符的集合；G是目标状态的集合。问题的状态空间可以用一个赋值有向图来表示，称为状态空间图。其中，节点表示状态；有向边（弧）表示算符。

7传教士与野人问题

例：设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵循两个约束：（1）船上的人数不得超过载重限量，设为K个人；（2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士数目。应如何规划渡河方案？为便于理解状态空间表示法，可简化该问题到一个特例：N=3，K=2。8解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态S=(m,c,b)其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。右岸的状态可由下式确定：右岸修道士数m'=3-m右岸野人数c'=3-c右岸船数b'=1-b在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32种状态。9

这32种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了这些状态，还需要考虑可进行的操作。

操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。每个操作都应当满足如下条件：

一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；二是每次操作船上人数不得超过2个；三是操作应保证不产生非法状态。因此，操作应由条件部分和动作部分：条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。

10操作的表示：

用符号Pij表示从左岸到右岸的运人操作用符号Qij表示从右岸到左岸的操作其中：i表示船上的修道士人数j表示船上的野人数操作集本问题有10种操作可供选择：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01为例来说明这些操作的条件和动作。操作符号条件动作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1

11

于是，从初始状态出发，可画出该问题的状态空间有向图，见图1.1。

o(220)(110)oo(021)111020110102(331)o01o(320)o(321)o(311)o(221)(031)o02o(010)(011)o01o(000)0201020120011011o(310)o(300)o(020)o(111)

图1.1传教士与野人问题的状态空间图

12二阶梵塔问题设用Sk=(Sk0,Sk1)表示问题的状态，Sk0表示金片A所在钢针号，Sk1表示金片B所在钢针号，全部可能的状态有九种：S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)13

ABABAB123123123二阶梵塔问题的初始状态和目标状态问题的初始状态集合为S={S0}目标状态集合为G={S4,S5}

初始状态S0和目标状态S4、S8如图所示

S0=(1,1)S4=(2,2)S8=(3,3)14操作分别用A(i,j)和B(i,j)表示A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它们分别是：A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2)B(1,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。15(3,3)(1,3)(1,2)(2,2)二阶梵塔的状态空间图从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从(1,1)开始，通过使用操作A(1,3)、B(1,2)及A(3,2)，可到达(3,3)。A(1,2)B(1,3)A(2,3)(1,1)(3,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)16状态空间表示法的几点说明

用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还要定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。

17

算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算符序列都可使问题从初始状态变到目标状态，这就得到了多个解。把其中使用算符最少的解称为最优解。例如在上例中，问题有无数条解答路径(因为划船操作可逆),但只有4个最优解，都包含了11个操作算子。这只是从解中算符的个数来评价解的优劣，今后将会看到评价解的优劣不仅要看使用算符的数量，还要看使用算符时所付出的耗散值，只有总耗散值最小的解才是最优解。18

对任何一个状态，可使用的算符可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算符生成更进一步的状态时，首先应对哪个状态进行扩展呢？这取决于搜索策略，不同的搜索策略的扩展顺序是不同的，这正是本章要讨论的问题。

除了少数像“传教士与野人”这样的简单的问题外，描述状态空间的图一般都很大，无法直观地画出，只能将其视为隐含图，在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。状态空间、搜索图和解答路径之间的关系，可以用下图表示。19状态空间、搜索图和解答路径的关系图

S0Sg问题全部状态空间搜索空间解路径20搜索问题（续）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。211.2回溯策略

回溯策略是一种试探性策略，属于盲目搜索的一种。它首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一状态设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。22回溯策略的实现方法

回溯策略有多种实现的方法，其中递归法是一种最直接的实现方法。

下面定义一个递归过程BACKTRCK，实现回溯策略。其功能是：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径；如果从当前状态到目标状态没有路径存在，则返回FAIL。23递归的思想从前有座山……从前有座山……

从前有座山……24回溯搜索算法 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。25回溯搜索算法的符号说明

DATA:变量，表示当前状态；TERM():谓词函数，当状态变量DATA满足结束条件时，TERM(DATA)取真。DEADEND():谓词函数，当状态变量DATA为非法状态时，DEADEND(DATA)取真.APPRULES():函数，计算出适用于DATA的规则集，并依据某种原则(任意排列或按启发式准则)排列后赋给RULES(规则集序列表)。26FIRST(RULES):函数，取出规则列表RULES中的第一条规则。TAIL(RULES):函数，删去RULES中的第一条规则。GEN(R,DATA):函数，调用规则R作用于当前状态DATA，生成一个新的状态RDATA。CONS(R,PATH):函数，构造新表，把规则R加到当前解路径表的前头。NIL:常量,表示空表；LOOP:常量,循环标号；FAIL:常量，回溯点标记；27回溯搜索算法递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);28递归的思想（图）当前状态n目标状态gm1m2…mkmir1r2rkri29递归的思想(续)递归过程BACKTRACK是将循环与递归结合在一起的。求从当前状态n到目标状态g的路径，一是要探索n的i个子状态m1,m2,…,mi中，通过哪一个子状态可以到达目标状态g。这一点是通过循环实现的，每次从n的可应用规则中，选一个规则rk(k=1,2,

…,i)作用于n，生成子状态mk，体现的是“横向”探索。二是“纵向”探索。为了探索n的某一个子状态mk是否可以到达目标状态g，算法通过递归来完成，即把mk又当成当前状态，探索mk的子状态到g是否有路径存在，如此进行下去。30例：在一个4×4的国际象棋棋盘上，一次一个地摆放4枚皇后棋子，摆好后要满足：每行、每列和对角线上只允许出现一枚棋子。问如何摆放？四皇后问题不合法状态合法状态31

每个状态由1至4个元素的集合构成，每个元素可表示为一对数ij，1≤i，j≤4，表示在第i行第j列的一个棋子。例如上图的两个布局可表示为(11233144)和(12243143)。问题的初始状态表示为()，问题的目标状态应满足问题的要求。

规则集:if1≤i≤4且Length(DATA)=i－1thenAPPEND(DATA(ij))(1≤j≤4)共有16条规则，每条规则Rij表示满足前提条件下，在ij处放一棋子。规则按先行后列从小到大排列。32()33()Q((1,1))34()QQ((1,1))((1,1)(2,3))35()Q((1,1))((1,1)(2,3))36()QQ((1,1))((1,1)(2,3))((1,1)(2,4))37()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))38()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))39()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))40()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))41()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))42()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))43()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))44()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))45存在问题及解决办法

解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态

问题：深度问题死循环问题46存在的问题深度问题:某些问题的某个(或某些)分支具有无穷个状态，算法可能会落入某一个“深渊”，久远也回溯不回来，这样，就不可能找到问题的解。死循环问题:某些问题在某一个分支上具有环路，搜索会在这个环路中一直进行下去，同样也回溯不出来，从而找不到问题的解。在前面的回溯算法BACKTRACK中，设置了两个回溯点，一个是当遇到非法状态时回溯，一个是当试探了一个状态的所有子状态后，仍然找不到解时回溯。47解决的办法

为了解决这两个问题，下面将给出回溯算法BACKTRACK1将增加两个回溯点：一个是用一个常量BOUND来限制算法所能够搜索的最大深度，当当前状态的深度达到了限制深度时，算法将进行回溯，从而可以避免可以落入“深渊”；另一个是将过程的参数用从初始状态到当前状态的表来替代原来的当前状态，当新的状态产生时，查看是否已经在该表中出现了。如果出现过，则表明有环路存在，算法将进行回溯，从而解决了环路问题。48回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。49回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMEMBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);50回溯搜索算法1（续）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);51一些深入的问题失败原因分析、多步回溯QQ52一些深入问题（续）

回溯搜索中知识的利用

基本思想(以皇后问题为例):充分利用问题的信息对RULES中的操作排序，可获得更高的效率。例如使用函数diag(i,j)，其定义是通过位置{ij}的最长的对角线的长度。如果diag(i,j)<diag(m,n)，则将Rij排在Rmn的前面，尽可能选取划去对角线上位置数最少的，这时搜索过程只回溯了2次就找到了目标状态。QQQQ322353练习：八皇后问题541.3图搜索策略问题的引出回溯搜索与图搜索的区别是：

回溯搜索:只保留从初始状态到当前状态的一条路径。

图搜索:保留所有已经搜索过的路径。55一般的图搜索思想

首先把问题的初始状态（即初始节点）作为当前状态，选择适用的算符对其进行操作，生成一组子节点，然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的子节点中再选一个作为当前状态。重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。56使用到的表OPEN表状态节点父节点CLOSED表编号状态节点父节点57一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+1012358一些基本概念（续1）

路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。

路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。59一些基本概念（续2）

扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。60一般图搜索算法的符号说明

s---指示初始状态节点；G---指示搜索图；

OPEN---用于存放待扩展节点的表；

CLOSE---用于存放已扩展节点的表；

FIRST(OPEN)---指示取OPEN表首的节点作为当前要被扩展的节点n；REMOVE(n,OPEN)---将节点n从OPEN表中删去；ADD(n,CLOSE)---把节点n加入到CLOSE表中；

EXPAND(n)---扩展节点n。

61一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);62一般的图搜索算法（续）7,标记和修改指针： ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；63节点类型说明…...…...…...…...…...mjmkmln

全新节点，mj；

已出现于OPEN表的节点，如mk；

已出现于CLOSE表的节点，如ml；

64修改指针举例123456s65123456修改指针举例（续）s661.4无信息图搜索过程

深度优先搜索

宽度优先搜索67一、深度优先搜索过程1，把初始节点s放入OPEN表；2，若OPEN表为空，则问题无解，退出；3，把OPEN表的第一个节点(记为节点n)取出放入CLOSE表；4，考察节点n是否为目标节点。若是，则求得了问题的解，退出；5，若节点n不可扩展，则转第2步；6，扩展节点n，将其子节点放入到OPEN表的首部，并为每个子节点配置指向父节点的指针，然后转第2步。6869有界深度优先搜索算法1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目标在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;70重排九宫问题23184765

123847657123184765

23184765283147652318476528314765283164752831476528316475283164

7528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标72有界深度优先搜索的性质

一般不能保证找到最优解；

当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；

最坏情况时，搜索空间等同于穷举；与回溯法的差别：图搜索是一个通用的、与问题无关的方法；73二、宽度优先搜索过程

1，把初始节点s放入OPEN表；2，若OPEN表为空，则问题无解，退出；3，把OPEN表的第一个节点(记为节点n)取出放入CLOSE表；4，考察节点n是否为目标节点。若是，则求得了问题的解，退出；5，若节点n不可扩展，则转第2步；6，扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点配置指向父节点的指针，然后转第2步。74宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();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},G:=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),

并标记mj到n的指针;9,GOLOOP;75重排九宫问题23184765

123847657623184765

231847652831476523184765283147652831647528314765283164752831647528371465

832147652814376528314576123784651238476512567312384765目标823418765477宽度优先搜索的性质

当问题有解时，一定能找到解。

当问题为单位耗散值，且问题有解时，一定能找到最优解。

方法与问题无关，具有通用性。

效率较低。

属于图搜索方法。78在3×3的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。可以使用的操作有空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应用宽度优先和深度优先搜索策略寻找从初始状态到目标状态的解路径。

831476512384765S0Sg练习79283147652831476523184765283147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg宽度优先802831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八数码问题的深度优先搜索如右图一种改进的深度优先算法是有界深度优先搜索算法，深度限制为dm深度优先81渐进式深度优先搜索方法

目的

解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。

思想

首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所有的分支为止。821.5启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。

启发信息的强度

强：降低搜索工作量，但可能导致找不到最优解

弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解83希望引入启发知识，在保证找到最优解的情况下，尽可能减少搜索范围，提高搜索效率。84基本思想

定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。85定义评价函数的参考原则一个结点处在最佳路径上的概率；求出任意一个结点与目标结点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分861启发式搜索算法A（A算法）A算法的思想：定义一个评价函数f，对当前状态进行评估，找出一个最有希望的结点来扩展。

评价函数的格式:f(n)=g(n)+h(n)

f(n):评价函数

h(n):启发函数87符号的意义

g*(n):从初始结点s到结点n的最短路径的耗散值；

h*(n):从结点n到目标结点g的最短路径的耗散值；

f*(n)=g*(n)+h*(n):从初始结点s经过结点n到目标结点g的最短路径的耗散值；

g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值。88A算法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},

计算f(n,mi):=g(n,mi)+h(mi); 89A算法（续）

ADD(mj,OPEN),标记mj到n的指针；

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),标记mk到n的指针；

IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；90…...…...…...…...…...mjmkmlnab91Closed表Open表92一个A算法的例子2831647512384765评价函数： f(n)=d(n)+W(n) d(n)为节点深度，取单位耗散值； W(n)为当前节点“不在位”的牌数。 93w计算举例 w(n)=42

831

64751234576

8w(n)=“不在位”的将牌数。942831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目标123456f(n)=d(n)+w(n)952最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：h(n)≤h*(n)则A算法称为A*算法。96A*条件举例2

831

6475

1234576

8将牌1：1将牌2：1将牌6：1将牌8：2

8数码问题h1(n)=w(n)=“不在位”的将牌数；h2(n)=p(n)=将牌“不在位”的距离和。97283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465s(5)A(7)B(5)C(7)D(6)E(5)F(7)I(5)J(7)K(5)L(5)M(7)目标12345f(n)=d(n)+p(n)98不同启发函数下扩展的结点数启发函数h(n)=0h(n)=w(n)h(n)=p(n)扩展结点数2665生成结点数46131199A*算法的性质

几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。

A*算法的假设

设ni、nj是任意两个节点，有：C(ni,nj)>其中为大于0的常数100A*算法的性质（续1）定理1.1: 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。101证明：首先证明算法必定会结束由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束102然后证明算法一定会成功结束由于至少存在一条由初始节点到目标节点的路径，设此路径为s=n0，n1

，…，nk=t算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中因此，算法必定会成功结束103A*算法的性质（续2）引理1.1: 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。104A*算法的性质（续3）引理1.2: A*结束前，OPEN表中必存在f(n)≤f*(s)。存在一个节点n，n在最佳路径上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)105A*算法的性质（续4）定理1.2: 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1:

A*如果不结束，则OPEN中所有的n有f(n)>f*(s)引理1.2:

在A*结束前，必存在节点n，使得f(n)≤f*(s)所以，如果A*不结束，将导致矛盾。106A*算法的性质（续5）推论1.1： OPEN表上任一具有f(n)<f*(s)的节点n，最终都将被A*选作扩展的节点。由定理1.2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被扩展。得证。107A*算法的性质（续6）定理1.3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。108可采纳性的证明由定理1.1、1.2知A*一定找到一条路径结束设找到的路径s→t不是最佳的（t为目标）则：f(t)=g(t)>f*(s)由引理1.2知结束前OPEN中存在f(n)≤f*(s)的节点n，所以f(n)≤f*(s)<f(t)因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。注意：A*的结束条件109A*算法的性质（续7）推论1.2： A*选作扩展的任一节点n，有f(n)≤f*(s)。由引理2.2知在A*结束前，OPEN中存在节点n’，f(n’)≤f*(s)设此时A*选择n扩展。如果n＝n’，则f(n)≤f*(s)，得证。如果n≠n’，由于A*选择n扩展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得证。110A*算法的性质（续8）定理1.4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n)(目标节点除外)，则A1扩展的节点数≥A2扩展的节点数111A*算法的性质（续9）注意：

在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。112定理1.4的证明使用数学归纳法，对节点的深度进行归纳（1）当d(n)＝0时，即只有一个节点，显然定理成立。（2）设d(n)≤k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k＋1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。113定理1.4的证明（续1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2扩展了n，有f2(n)≤f*(s)即：h2(n)≤f*(s)–g2(n)(A)由于d(n)=k时，A2扩展的节点A1一定扩展，有g1(n)≤g2(n)(因为A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比较A、B两式，有h1(n)≥h2(n)，与定理条件矛盾。故定理得证。114对h的评价方法平均分叉树 设共扩展了d层节点，共搜索了N个节点，则:

其中，b*称为平均分叉树。b*越小，说明h效果越好。实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。115对h的评价举例例：8数码问题，随机产生若干初始状态。使用h1： d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2： d=14,N=113, b*=1.23; d=20,N=676, b*=1.27116A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：

abs(h(n)-h*(n))≤O(log(h*(n)))

A*的算法复杂性才是非指数型的，但是通常情况下，h与h*的差别至少是和离目标的距离成正比的。1173，A*算法的改进问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。118s(10)A(1)B(5)C(8)G目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)119出现多次扩展节点的原因s(10)A(1)B(5)C(8)G目标631118

在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。120解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。121改进的条件

可采纳性不变

不多扩展节点

不增加算法的复杂性122对h加以限制h(ni)ninjh(nj)c(ni,nj)定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足 h(ni)-h(nj)≤c(ni,nj) h(t)=0或h(ni)≤c(ni,nj)+h(nj) h(t)=0则称h是单调的。123h单调的性质

定理1.5：

若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，有g(n)=g*(n)。124定理1.5的证明设n是A*扩展的任一节点。当n＝s时，定理显然成立。下面考察n≠s的情况。设P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路径P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。125定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有：h(ni)≤C(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路径上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)带入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)126定理1.5的证明（续2）重写上式：f(nj+1)≤g*(n)+h(n)另一方面，A*选n扩展，必有：f(n)=g(n)+h(n)≤f(nj+1)比较两式，有：

g(n)≤g*(n)但已知g*(n)是最佳路径的耗散值，所以只有：g(n)=g*(n)。得证。127h单调的性质（续）定理1.6：

若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni)≤f(nj)。128定理1.6的证明由单调限制条件，有：h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)

f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)

f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)

≤C(ni,nj)

f(ni)-f(nj)

≤0，得证。129h单调的例子

8数码问题：h为“不在位”的将牌数1 h(ni)-h(nj)=0 (nj为ni的后继节点)-1 h(t)=0 c(ni,nj)=1满足单调的条件130对算法加以改进一些结论：OPEN表上任以具有f(n)<f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)≤f*(s)。131改进的出发点OPEN=(…………)f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点

fm:

到目前为止已扩展节点的最大f值，用fm代替f*(s)132修正过程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g最小的节点 ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同过程A。133s(10)A(1)B(5)C(8)G目标631118OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)前面的例子134h的单调化方法如果令： f(n)=max(f(n的父节点),g(n)+h(n))则容易证明，这样处理后的h是单调的。135IDA*算法(IterativeDeepeningA*)基本思想：回溯与A*的结合算法简介（非严格地）1，设初始值f0；2，集合S＝NULL；3，用回溯法求解问题，如果节点n的f值大于f0，则将该节点放入集合S中，并回溯；4，如果在3中找到了解，则结束； 5，如果3以失败结束，则f0＝S中节点的最小f值；6，返回到2。136A*算法应用举例P40八数码问题传教士和野人问题1374其他的搜索算法

爬山法（局部搜索算法）

分支界限法动态规划法138爬山法（图示）139爬山法

在g(n)0的情况下，若限制只用评价函数f(n)=h(n)去排序新扩展出来的子节点，即局部排序，就可实现较为简单的搜索策略：爬山法。爬山法适用于能逐步求精的问题，对于单一及值问题十分有效，但对于具有多及值的问题就无能为力了。爬山法是实现启发式搜索的最简单方法,不需设置OPEN表和CLOSE表，因为没有必要保存任何待扩展节点，仅从当前状态节点扩展出的子节点中将h(n)最小的子节点作为下一次考察的节点，其余的节点全部丢弃。140爬山法(hill-climbing)—就是向值增加的方向持续移动—登高过程/如果相邻状态中没有比它更高的值，则算法结束于顶峰爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法141爬山算法Hill-climbing1,n=s;//s为初始节点2,LOOP:IFGOAL(n)THENEXIT(SUCCESS);3,EXPAND(n){mi},计算h(mi),nextn:=m(minh(mi)的节点);4,IFh(n)<h(nextn)THENEXIT(FAIL);5,n:=nextn;6,GOLOOP;142分支界限法（思想）

分支界限法是优先扩展当前具有最小耗散值分支路径的端节点n(没有子节点的节点)，其评价函数为f(n)=g(n)。该算法的基本思想很简单，实际上是建立一个局部路径（或分支）的队列表，每次都选择耗散值最小的那个分支上的端节点进行扩展，直到生成含有目标节点的路径为止。143分支界限算法

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-mi,QUEUE);6,QUEUE中局部路径g值最小者排在前面；7,GOLOOP;144分支界限法例子sDAEBFtC432455434八城市交通图例:求解右图从城市s到城市t的最短路径。145分支界限搜索树sADBAFE1g=0g=3425g=73D6g=8C11g=11E12g=12EBg=47g=9g=6g=13B10g=11F9g=1