人工智能基础及应用 课件 第4章 搜索策略

人工智能第四章搜索策略

4.1

状态空间搜索方法国家级一流本科线上线下混合式课程“人工智能”搜索的基本概念状态空间表示法状态空间搜索法的一般过程主要内容

搜索的基本概念2831

4765例如：八数码游戏问题初始状态目标状态12384765什么是搜索？根据问题的实际情况，不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。搜索的分类4盲目搜索：搜索过程中控制策略不变。启发式搜索：搜索过程中其控制策略依据所获得启发信息做出相应的改变以使问题朝着最有希望得解的方向搜索。如在八数码问题中，空格始终按照上下左右一种顺序移动到目标状态出现。搜索的本质问题求解5搜索2831

476512384765八数码游戏问题过河问题怎样把问题表示出来？状态空间表示法状态空间由问题的全部状态及一切可用算符所构成的集合，一般用三元组表示：（S,F,G）2831

47652318476528316475283

1476528314

76512384765算符F：使问题由一个状态变为另一个状态的操作状态：用于描述问题求解过程中不同时刻的状况初始状态中间状态目标状态SGF

问题的解就是：由初始状态到目标状态所用算符的序列。2831

47652318476528316475283

1476528314

76512384765初始状态S中间状态目标状态G用状态空间表示法进行问题求解—举例二阶梵塔问题：有编号为1、2、3的三个柱子和标识为A、B的尺寸依次为小、大的有中心孔的圆盘；初始状态下盘子按A、B顺序堆放在1号柱子上，目标状态下盘子以同样次序顺序堆放在3号柱子上，盘子的移动规则：每次只能移动一个盘子，且大盘子不能压放在小盘子上。

123AB123AB初始状态目标状态S=(1,1)

A(i,j)：把圆盘A从第i号柱子移到第j号柱子B(i,j)：把圆盘B从第i号柱子移到第j号柱子算符FG=(3,3)二元组（x,y）表示问题的状态9

全部可能的状态：（1,1）（1,2）（1,3）（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）S=（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）G=（3,3）

全部算符：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)状态空间图A（1,2）B（1,3）A（2,3）A（1,3）同一状态作用于不同的算符得到不同的后继状态弧代表状态的变迁节点代表状态弧上的标签则指示导致状态变迁的操作算符问题的最优解10①先定义状态的描述形式和算符F；

②给出初始状态S集和目标状态G集的描述；

③进行问题求解：从初始状态开始不断地使用算符改变问题的状态直到获得目标状态时为止；

④问题的解：使问题从初始状态变化到目标状态的算符序列；⑤解不唯一：存在多个解，算符最少的解为最优解。用状态空间表示法进行问题求解小结11（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）状态空间图A（1,2）B（1,3）A（2,3）A（1,3）由2阶梵塔变为64阶梵塔时，将有364个不同的状态12首先，将问题的初始状态当做当前状态，选择一个适当的算符作用于当前状态，生成一组后继状态（或称后继节点），然后检查这组状态中是否有目标状态。

如果有，则搜索成功，从初始状态到目标状态的

一系列算符即是问题的解；

若没有，则按照某种控制策略从已生成的状态中再选择一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。搜索法求解问题的基本思想状态空间搜索方法的一般过程扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：已经求出了其后继节点的节点。未扩展节点：尚未求出后继节点的节点。OPENCLOSEDOPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点状态空间搜索方法的一般过程在搜索过程中生成了一个图G，它是问题状态空间图的一部分，称为搜索图G若不是目标节点，则扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中若后继节点未在G中出现，设置一个指向父节点n的指针；若后继节点已在G中出现，确定是否需要修改指向父节点的指针；对于已在G中出现并已在CLOSED表中后继节点，确定是否需要修改通向他们后继节点的指针。YYNN*总结

状态空间表示法基于状态空间搜索法的一般过程作业：

利用状态空间搜索法求解“修道士与野人过河问题”算符状态状态空间图具有通用性提高解题效率节省存储空间人工智能第四章搜索策略

4.2

宽度优先搜索方法宽度优先搜索方法的基本思想宽度优先搜索方法的算法流程宽度优先搜索方法的案例分析主要内容18宽度优先搜索方法的基本思想从初始节点S0开始逐层对节点进行扩展考察被扩展节点是否为目标节点？在第n层的节点没有被全部扩展之前，不能对第n+1层的节点进行扩展在搜索过程中,未扩展的节点在OPEN表中的排序准则是：新生成节点排放在OPEN表的末端。ABEDJGCIHF宽度优先搜索过程示意图状态节点父节点

宽度优先搜索方法的流程YYNN*NYOPENCLOSEDABEDCS0编号状态节点父节点

S0NULLAB1S0S0

八数码游戏问题

用宽度优先搜索方法进行问题求解—案例八数码游戏问题：在一个3x3的方格棋盘上，分别放置标有数字为1,2,3,4,5,6,7,8的八张数码牌，有一个方格为空，如图。其初始状态为S0，要求通过数码在方格棋盘内的上下左右移动，寻找从初始状态S0达到目标状态Sg的路径。初始状态S0目标状态Sg

UP：空格上移DOWN：空格下移LEFT：空格左移RIGHT：空格右移算符F3x3的二维表格或矩阵表示其状态

2831476512384765用宽度优先搜索方法进行问题求解—案例初始状态S0目标状态Sg283147651238476523184765283147652831476528316475283164752831647528314576281437652318476523184765283714

658321476528316754283

64175283145762814376523418765123847652837146583214765123784

651238476528371465283746158132476583214765gahijkledbcnmfsrqpouvwxyztOPENCLOSED状态节点

父节点

编号

状态节点

父节点

S0NULL1bS0aS0228314765gcdefS03gh编号1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16状态节点

S0,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o父节点

nullS0aabbccddefg状态节点

pqrstuvwxyz父节点

hijklmmnnooOPENCLOSED

解的路径为：S0->b->g->o->y(Sg)用宽度优先搜索方法进行问题求解—案例初始状态S0目标状态Sg283147651238476523184765283147652831476528316475283164752831647528314576281437652318476523184765283714

658321476528316754283

64175283145762814376523418765123847652837146583214765123784

651238476528371465283746158132476583214765gahijkledbcnmfsrqpouvwxyzt总结

宽度优先搜索过程---层次化搜索宽度优先搜索方法特点作业：

优点：只要有解，

一定能找到最优解缺点：盲目性大，搜索效率低请大家思考，算法如何设计可以免去对opqratuvw等节点扩展，即使算法在目标节点出现的时候，程序就结束？人工智能第四章搜索策略

4.3

深度优先搜索方法深度优先搜索方法的基本思想深度优先搜索方法的算法流程深度优先搜索方法的案例分析主要内容27深度优先搜索方法的基本思想从初始节点S0开始在其新生成的后继节点中选择一个节点扩展考察被扩展节点是否为目标节点？若其不是目标节点，则对该节点进行扩展，并再从其新生成后继节点中选择一个节点进行考察。

在搜索过程中,新生成的节点在OPEN表中的排序规则是：排放在OPEN表的首部。深度优先搜索过程示意图*每次扩展最新生成的节点*ABEDJGCIHF状态节点父节点

深度优先搜索方法的流程YYNN*NYOPENCLOSEDABDECS0编号状态节点父节点

S0NULLAB1S0S0

案例分析系列八数码游戏问题之深度优先搜索

用深度优先搜索方法进行问题求解—案例初始状态S0目标状态Sg28314765123847652318476528314765283147652831647528316475283164752831675428163754aifedbcfhgOPENCLOSED状态节点

父节点

编号

状态节点

父节点

S0NULL1cS0dS0228314765gbad3gfed428316754j28163754…深度优先搜索是

不完备的

深度优先搜索求得的解

不一定是路径最短的解总结

深度优先搜索过程---纵向搜索与宽度优先搜索方法的区别是：

*新生成的节点放入到OPEN表的首部*深度优先搜索方法作业：

盲目性，不完备性求得的解不一定是最优解请大家思考，算法如何改进可以避免搜索无限循环的产生？人工智能第四章搜索策略

4.4

有界深度优先搜索方法有界深度优先搜索方法的基本思想有界深度优先搜索方法的算法流程有界深度优先搜索方法的案例分析主要内容34有界深度优先搜索方法的基本思想有界深度优先搜索过程示意图*引入搜索深度的限制dm*首先设搜索树中初始节点的深度为0，d(S0)=0；任何其他节点的深度等于其父节点的深度加1，

即d(n+1)=d(n)+1(n为父节点，n+1为n的子节点)；当被搜索的节点的深度达到了深度界限

dm，而

未出现目标节点，就认为其没有后继节点；结束对该分支的搜索，换另一分支进行搜索。dm=2ABEDJGCIHFd(S0)=0d(A)=1d(B)=1d(C)=d(D)=2d(E)=d(F)=2有界深度优先搜索方法的流程YYNN*NYOPENCLOSEDNY状态节点

父节点

编号

状态节点

父节点

S0NULLABEDJGCIHFd(S0)=0d(A)=1d(B)=1d(C)=d(D)=2d(E)=d(F)=2ABS012345…EBBFdm=2

案例分析系列八数码游戏问题之有界深度优先搜索

用有界深度优先搜索方法进行问题求解—案例初始状态S0目标状态Sg283147651238476523184765283147652831476528316475283164752831647528314576281437652318476523184765283157462831457628316754283

6417528314576281437652341876512384765123784

651238476528364175

832641

7528163754283167542112213145616423171015182326891112272872831457619123784

652023418765242341857625Sgdm=4d=1d=3d=2d=4人工智能第四章搜索策略

4.5

代价树搜索方法代价树搜索方法的基本概念代价树搜索方法的基本思想与算法流程代价树搜索方法的应用举例主要内容41代价树的基本概念代价树：是代价搜索树的简称，是指有向边

上标有代价（或费用）的搜索树。：在代价树中把从节点i到其后继节点j

的代价记为；

：把从初始节点S0到任意节点x的路径

代价记为，则从初始节点S0到节

点i的代价，那么从初始节点S0

到节点j的代价就为。*通常设初始节点S0的代价为。ABiDeGCjH346229783代价树42代价树宽度优先搜索方法的基本思想从初始节点S0开始每次从OPEN表中选择一个代价最小的节点移入到CLOSED表中进行判断与搜索在对节点进行扩展之后，要计算其所有后继节点的代价将它们与OPEN表中未扩展节点按代价值进行从小到大的排序，代价最小的点，排在OPEN表的最前面。cs02状态节点

父节点

代价ge

c4代价树宽度优先搜索方法的流程YYNN*NYOPENCLOSEDacegbhdf34622683编号

状态节点

父节点

代价gS0NULL01abs0s0362as033fbc

s056状态节点

父节点

代价gfc5代价树深度优先搜索方法的流程YYNN*NYOPENCLOSEDacegbhdf34622683编号

状态节点

父节点

代价gS0NULL0cs021abs0s0362ec43扩展节点i，对每个后继节点计算其代价，并对新生成的后继节点按其代价从小到大排序，放入到OPEN表的首部

案例分析系列推销员旅行问题之代价树宽度优先搜索

用代价树搜索方法进行问题求解—案例推销员旅行问题描述为：有五个城市A、B、C、D和E，其交通路线图，如图所示。图中每条边上的数字为代表两城市之间的交通费用（代价）。推销员要从A城市出发到达E城市，问走怎样的路线费用最省？即求从A到E的最小费用的交通路线。ADBEC768756C1A7状态节点

父节点

代价gOPENB16576编号

状态节点

父节点

代价g用代价树宽度优先搜索方法进行问题求解—案例ADBEC768756CLOSEDAC1E1D1E2C2D2B2E377865ANULL01B1A62D1B1113D2C114E1C1154E2C2D1D117185B2C2D2D219206代价树总结

代价树

作业：

特点：只要有解，

一定能找到最优解特点：得到的解不一定是最优的

存在不完备性深度优先搜索：只对新生成的节点进行排序宽度优先搜索：对所有未扩展的节点排序请大家思考怎样解决代价树的深度优先搜索方法存在的问题？并完成推销员旅行问题的深度优先搜索过程。人工智能第四章搜索策略

第六讲

启发式搜索方法启发性信息与估价函数的基本内容启发式搜索方法的算法流程启发式搜索方法的应用举例主要内容51深度优先搜索过程ABEDJGCIHFABEDJGCIHF宽度优先搜索过程有界深度优先搜索过程dm=2ABEDJGCIHFacegbhdf34622683代价树宽度搜索过程52启发式搜索方法的基本思想*启发式搜索方法：利用问题本身的某些特性信息，考查节点在解的路径上的可能性（重要性），指导搜索向最有利于问题求解的方向进行。即选择那些在解的路径上的可能性（重要性）大的节点，这样就会缩小搜索空间，提高效率。

为从节点x到目标节点Sg的最优路径的估计代价为从初始节点S0到节点x已经实际付出的代价ABEDSgGCHx从初始节点S0经过节点x到达目标节点Sg的最优路径的代价估计值---启发性信息可用于：决定要扩展的下一个节点；决定要扩展哪一个或那几个后继节点；

决定从搜索树中抛弃或修剪哪些节点。---启发性信息与估价函数启发性信息：是可用于指导搜索过程，与具

体问题求解有关的控制性信息。估计函数：用于估价节点重要性的函数，其一

般形式为:53启发式搜索方法的基本思想

当一个节点被扩展以后按估价函数对每个子节点计算估价值，并选择估价值最小者作为下一个要考察的节点。由于它每次只是在子节点的范围内选择下一个要考察的节点，所以称为局部最佳优先搜索方法。又因为其按照估价值对节点进行排序，所以是启发式搜索方法。*局部最佳优先搜索方法*局部最佳优先搜索方法流程图

在OPEN表中的全部节点中选择一个估价函数值最小的节点，作为下一个被考察的节点。因为其选择的范围是OPEN表中的全部节点所以称全局最佳优先搜索方法。启发式搜索方法的基本思想54*全局最佳优先搜索方法*全局最佳优先搜索方法流程图局部最佳优先搜索方法流程图*不同之处*

案例分析系列八数码游戏问题之全局最佳优先搜索

用全局最佳优先搜索方法进行问题求解—案例初始状态S0目标状态Sg2831476512384765---依据问题定义估价函数为表示节点x的深度（即节点x所在的层次，规定初始节点S0,所在的层次为0)为从节点x的棋牌格局与目标节点Sg的棋牌格局，不相同的牌数。

状态节点

父节点

估价值fbs0

4cds0s055用全局最佳优先搜索方法进行问题求解—案例初始状态S0目标状态Sg2831476512384765231847652831476528314765283164752318476523184765283714

658321476512384765123784

6512384765haiedbcfjkL28314765g

解的路径为：S0->b->h->j->k(Sg)hb4OPENCLOSED编号

状态节点

父节点

估价值fS0NULL31efa

a562as043ib64jh45kj4Lj66

Sg总结启发式搜索方法关键问题是：估价函数的构造

它与问题本身的特性是密切相关的，

不同问题，构造的估价函数不同，

同一问题也可构造不同的估价函数。注意问题是：估价函数定义不当，可能会使问题找不到解，

或者，即使找到解，