第三章_搜索策略-1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Computer Science&Technology,*,*,2026/4/10 周五,1,第,3,章 搜索策略,问题求解系统划分为两大类,知识贫乏系统,依靠,搜索技术,解决问题,知识贫乏、缺乏针对性,效率低,知识丰富系统,依靠,推理技术,解决问题,基于丰富知识的推理技术，直截了当,效率高,2026/4/10 周五,2,第,3,章 搜索策略,两大类,搜索,技术,:,1,、一般图搜索、启发式搜索,2,、基于问题归约的与或图搜索,两种典型的,推理技术,:,1,、基于归结的演绎推理,归结反演,2,、基于规则的演绎推理,正向演绎推理,逆向演绎推理,2026/4/10 周五,3,3.1,引言,对于给定的问题，智能系统的行为一般是,找到能够达到所希望目标的动作序列,，并使其所付出的,代价最小、性能最好,。,基于给定的问题，问题求解的第一步是目标的表示。,搜索就是找到智能系统的,动作序列的过程,。,2026/4/10 周五,4,搜索算法的输入是,给定的问题,，输出时表示为,动作序列的方案,。,一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）,因此，求解问题包括：,目标表示,搜索,执行,2026/4/10 周五,5,（,1,）初始状态集合：定义了初始的环境。,（,2,）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。,（,3,）目标检测函数：用来确定一个状态是不是目标。,（,4,）路径费用函数：对每条路径赋予一定费用的函数。,其中，初始状态集合和操作符集合定义了问题的搜索空间。,一般给定问题就是确定该问题的一些基本信息，一个问题由,4,部分组成,:,2026/4/10 周五,6,和通常的搜索空间不同，人工智能中大多数问题的,状态空间在问题求解之前不是全部知道的,。,在人工智能中，搜索问题一般包括两个重要的问题：,搜索什么,搜索什么通常指的就是目标。,在哪里搜索,在哪里搜索就是,“,搜索空间,”,。搜索空间通常是指一系列状态的汇集，因此称为,状态空间,。,2026/4/10 周五,7,所以，人工智能中的搜索可以分成两个阶段：,状态空间的生成阶段,在该状态空间中对所求问题状态的搜索,搜索可以根据是否使用,启发式信息,分为,盲目搜索,启发式搜索,2026/4/10 周五,8,盲目搜索,只是可以区分出哪个是目标状态。,一般是,按预定的搜索策略进行搜索,。,没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。,启发式搜索,是在搜索过程中加入了,与问题有关的启发式信息,，用于指导搜索,朝着最有希望的方向前进，加速问题的求解并找到最优解,。,2026/4/10 周五,9,根据问题的表示方式分为,状态空间搜索,与或图搜索,状态空间搜索是用状态空间法来求解问题所进行的搜索,与,/,或图搜索是指用问题规约方法来求解问题时所进行的搜索。,2026/4/10 周五,10,考虑一个问题的状态空间为一棵树的形式。,宽度优先搜索,深度优先搜索,如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。,在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。,2026/4/10 周五,11,无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为,“,确定性,”,的，也就是,盲目搜索,。,对于启发式搜索，在计算每个节点的参数之前,无法确定先选择哪个节点扩展,，这种搜索一般也称为,非确定,的。,2026/4/10 周五,12,完备性：,如果存在一个解答，该策略是否保证能够找到？,时间复杂性：,需要多长时间可以找到解答？,空间复杂性：,执行搜索需要多少存储空间？,最优性：,如果存在不同的几个解答，该策略是否可以发现最高质量的解答？,搜索策略评价标准,:,2026/4/10 周五,13,有许多智力问题,(,如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等,),和实际问题（如路径规划、机器人行动规划等）都可以归结为,状态空间搜索,。,用,状态空间搜索,来求解问题的系统均定义一个,状态空间,，并通过适当的,搜索算法,在,状态空间,中搜索,解答路径,。,3.2,基于状态空间的搜索技术,2026/4/10 周五,14,状态空间搜索,1.,状态空间及其搜索的表示,(1),状态空间的表示,状态空间记为,SP,，可表示为二元组：,SP=(S,O),S,问题求解（即搜索）过程中所有,可能到达,的,合法状态,构成的集合；,O,操作算子,的集合，,操作算子的执行会导致问题状态的变迁,；,状态,用于记载问题求解（即搜索）过程中,某一时刻问题现状的快照,；,抽象为矢量形式,Q=q,0,q,1,q,n,T,每个元素,q,i,称为,状态分量,给定每个,状态分量,q,i,的值就得到一个具体的状态,Q,k,=q,0k,q,1k,q,nk,T,2026/4/10 周五,15,状态,表示状态的变迁,操作算子,问题的状态空间,是一个表示该问题的全部可能状态及其变迁的,有向图,。,节点,状态,有向弧,状态的变迁,弧上的标签,导致状态变迁的,操作算子,用,状态空间搜索,来求解问题的系统均定义一个,状态空间,，并通过适当的,搜索算法,在,状态空间,中搜索,解答路径,。,2026/4/10 周五,16,例,1,：,走迷宫,是人们熟悉的一种游戏。,状态空间搜索,2026/4/10 周五,17,格子、入口和出口,节点,状态,通道,有向弧,操作算子,迷宫可以由一个,有向图,表示,2026/4/10 周五,18,例,2:,在一个,33,的方格棋盘上放置着,1,2,3,4,5,6,7,8,八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。,现在的,问题,是：对于指定的,初始棋局,和,目标棋局,，给出,数码的移动序列,。该问题称为,八数码问题,。,5,6,7,4,1,3,8,2,初始棋局,5,6,7,4,8,3,2,1,目标棋局,移动数码,2026/4/10 周五,19,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,8 4,7 6 5,2026/4/10 周五,20,2026/4/10 周五,21,例,3:,钱币翻转问题。设有,3,个钱币，其初始状态为,(,正、反、正,),欲得的目标状态为,(,正、正、正,),或,(,反、反、反,),。问题是允许每次只能且必须翻转一个钱币，连翻三次。问能否达到目标状态。,分析：通过引入一个,三维变量,将问题表示出来。设三维变量为：,Q=q,1,q,2,q,3,，式中,q,i,(i=1,2,3)=1,表示钱币为正面，,q,i,(i=1,2,3)=0,表示钱币为反面。,则三个钱币可能出现的状态有,8,种组合：,Q,0,=(0,0,0),Q,1,=(0,0,1),Q,2,=(0,1,0),Q,3,=(0,1,1),Q,4,=(1,0,0),Q,5,=(1,0,1),Q,6,=(1,1,0),Q,7,=(1,1,1),。,即初始状态为,Q,5,，,目标状态为,Q,0,或,Q,7,，,要求步数为,3,。,2026/4/10 周五,22,钱币问题的状态空间图,2026/4/10 周五,23,状态空间搜索,1.,状态空间及其搜索的表示,(2),状态空间表示的经典例子“传教士和野人问题”,问题的描述,：,N,个传教士带领,N,个野人划船过河；,3,个安全约束条件：,1),船上人数不得超过载重限量，设为,K,个人；,2),任何时刻（包括两岸、船上）野人数目不得超过传教士；,3),允许在河的某一岸或者在船上只有野人而没有传教士；,2026/4/10 周五,24,状态空间搜索,1.,状态空间及其搜索的表示,(2),状态空间表示的经典例子“传教士和野人问题”,特例：,N=3,，,K=2,状态分量,m,传教士在左岸的实际人数,状态分量,c,野人在左岸的实际人数,状态分量,b,指示船是否在左岸,(1,、,0),3,个安全约束条件,m c(,左岸安全,),且,N-m N-c(,右岸安全,);(,想一想，为什么不考虑船安全？,),m=0,且,0c N(,左岸没有传道士，右岸一定安全,);,N-m=0,且,0N-cN(,右岸没有传道士，左岸一定安全,);,2026/4/10 周五,25,设,初始状态,下传教士、野人和船都在左岸，,目标状态,下这三者均在右岸，,问题状态,以,（,m,c,b,）,表示,。,问题的求解任务可描述为：,(3,3,1),(0,0,0),该简单问题,可能到达,的,合法状态,：,可能状态,总数,：,4,4,2=32,根据条件得出,合法状态,：,20,m c,且,N-m N-c,(,左岸安全且右岸安全,),m=1,c=1,；,m=2,c=2,m=0,且,0c N(,左岸没有传道士,),m=0,c=0,1,2,3,N-m=0,且,0N-cN(,右岸没有传道士,),m=3,c=0,1,2,3,不可能到达的合法状态,：,(0,0,1),(0,3,0),(3,0,1),(3,3,0),可能到达,的,合法状态,共,16,个,2026/4/10 周五,26,状态空间搜索,1.,状态空间及其搜索的表示,(2),状态空间表示的经典例子“传教士和野人问题”,定义,2,类,操作算子,：,L(x,y),指示从,左岸,到,右岸,的划船操作,R(x,y),指示从,右岸,到,左岸,的划船操作,x+y K=2(,船的载重限制,),；,x,和,y,取值的可能组合只有,5,个,10,，,20,，,11,，,01,，,02,(,允许在船上只有野人而没有传教士,),共有,10,个操作算子,2026/4/10 周五,27,渡河问题的状态空间有向图,2026/4/10 周五,28,状态空间搜索,1.,状态空间及其搜索的表示,总结状态空间表示方法：,用状态空间方法表示问题时，首先必须,定义状态的描述形式,，通过使用这种描述形式可把问题的,一切状态都表示出来,。另外，还要,定义一组操作,，通过使用这些操作可把问题,由一种状态转变为另一种状态,。,问题的求解过程是一个,不断把操作作用于状态的过程,。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是从,初始状态到目标状态所用操作构成的序列,。,2026/4/10 周五,29,状态空间搜索,1.,状态空间及其搜索的表示,总结状态空间表示方法：,要使问题由一种状态转变到另一种状态时，就必须使用一次操作。这样，在从初始状态转变到目标状态时，就可能存在多个操作序列,(,即得到多个解,),。那么，其中,使用操作最少或较少的解才为最优解,(,因为只有在使用操作时所付出的代价为最小的解才是最优解,),。,对其中的某一个状态，可能存在多个操作使该状态变到几个不同的后继状态那么到底用哪个操作进行搜索呢,?,这就有赖于,搜索策略了,不同的搜索策略有不同的顺序,，这就是本章后面要讨论的问题。,2026/4/10 周五,30,课堂练习,有一农夫带一只狐狸、一只小羊和一篮菜过河（从左岸到右岸）。假设船太小，农夫每次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那篮菜也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。,2026/4/10 周五,31,解析,以变量,m,、,f,、,s,、,v,分别指示农夫、狐狸、小羊、菜,且每个变量只可取值,1(,表示在左岸,),或,0(,表示在右岸,),。问题状态可以四元组,(m,、,f,、,s,、,v),描述,设初始状态下均在左岸,目标状态下都到达右岸。从而,问题求解任务可描述为,(1,1,1,1)-(0,0,0,0),思考：为什么不把船的状态放到状态空间中去？,由于问题简单,状态空间中可能的状态总数为,2,2,2,2=16,由于要遵从安全限制,合法的状态只有,(,除初、目状态外,):,1110,，,1101,，,1011,，,1010,，,0101,，,0001,，,0010,，,0100,；不合法状态有,:0111,1000,1100,0011,0110,1001,设计二类操作算子,:Lx,、,Rx,x,为,m,、,f,、,s,、,v,时分别指示农夫独自,带狐狸,带小羊,带菜过河；状态空间图如下所示,.,由于,Lx,和,Rx,是互逆操作,故而解答路径可有无数条,但最近的只有二条,;,都是,7,个操作步,.,2026/4/10 周五,32,解析,:,四元组,(m,、,f,、,s,、,v),代表（农夫、狐狸、小羊、菜）,2026/4/10 周五,33,状态空间搜索,1.,状态空间及其搜索的表示,(3),状态空间的搜索,状态空间的搜索记为,SE,，可表示为五元组：,SE,=(,S,O,E,I,G,),；,E,搜索引擎；,I,问题的初始状态，,I,S,；,G,问题的目标状态集合，,G,S,。,搜索引擎,E,可以设计为,实现任何搜索算法,的控制系统。,基本思想,通过搜索引擎,E,寻找一个,操作算子的调用序列,，使问题从初始状态,I,变迁到目标状态,G,之一。,解答路径,初,-,目变迁过程中,的,状态序列,或相应的,操作算子调用序列,。,2026/4/10 周五,34,状态空间搜索,1.,状态空间及其搜索的表示,或图（一般图）,一个状态,可以,有多个可供选择,的操作算子；,操作算子间的选择是一种,“,或,”,的关系,;,这样的有向图称为,或图。,2026/4/10 周五,35,状态空间搜索,1.,状态空间及其搜索的表示,(3),状态空间的搜索,或图（一般图）,一个状态可以有多个可供选择的操作算子；,操作算子间的选择是一种,“,或,”,的关系，,这样的有向图称为,或图。,状态空间,一般都表示为,或图（一般图）,搜索图,在,搜索解答路径,的过程中画出搜索时涉及到的节点和弧线，构成所谓的,搜索图,。,状态空间搜索,一般图搜索,2026/4/10 周五,36,状态空间搜索,1.,状态空间及其搜索的表示,(3),状态空间的搜索,状态空间,、,搜索图,和,解答路径,之间的关系,S0,Sg,2026/4/10 周五,37,状态空间搜索,1.,状态空间及其搜索的表示,(4),一般图搜索例子,八数码游戏,求解的问题：,给定初始布局,(,即,初始状态,),和目标布局,(,即,目标状态,),，,如何移动数码才能从初始布局到达目标布局？,解答,就是一个合法的,棋牌走步序列,。,初始布局,目标布局,移动数码,2026/4/10 周五,38,状态空间搜索,1.,状态空间及其搜索的表示,(4),一般图搜索例子,八数码游戏,用一般图搜索方法解决该问题的步骤：,1,、为,问题状态,的表示建立数据结构,2,、制定,操作算子,集合,3,、设计,搜索引擎,第一步：为问题状态的表示建立数据结构,33,的一个矩阵,S,矩阵元素,Sij0,1,2,3,4,5,6,7,8,其中,1i,j3,数字,0,表示空格,数字,1-8,表示相应的棋牌,八数码问题就可表示为：,2026/4/10 周五,39,状态空间搜索,1.,状态空间及其搜索的表示,初始布局,目标布局,移动数码,(4),一般图搜索例子,八数码游戏,2026/4/10 周五,40,状态空间搜索,1.,状态空间及其搜索的表示,(4),一般图搜索例子,八数码游戏,第二步：制定操作算子集,直观方法,为每个棋牌制定一套可能的走步：左、上、右、下四种移动。,需要,32,个操作算子,简易方法,仅为空格制定这,4,种走步。,仅需,4,个操作算子,第三步：设计搜索引擎,问题状态空间的大小,与,问题涉及的元素,个数是程,指数级爆炸式增长,（即，,组合爆炸问题,）,如，棋盘布局（问题状态）总共有,9!=362880,个,研究焦点,是,解决组合爆炸问题,，,通过压缩搜索空间,，,提高搜索效率,。,2026/4/10 周五,41,状态空间搜索,1.,状态空间及其搜索的表示,状态空间,、,搜索图,和,解答路径,之间的关系,S0,Sg,2026/4/10 周五,42,状态空间搜索,2.,一般图搜索策略,（,1,）搜索术语,1,、节点深度,根节点,指示,初始状态,，令其深度为,0,；,搜索图中的其他节点的,深度,d,n,就可以递归地定义为其,父节点深度,d,n-1,加,1,：,d,n,=d,n-1,+1,。,根节点深度,=0,第,n-1,层节点,d,n-1,第,n,层节点,d,n,=,d,n-1,+1,搜索图,2026/4/10 周五,43,状态空间搜索,2.,一般图搜索策略,（,1,）搜索术语,2,、节点扩展,应用,操作算子,将,上一状态,（节点,n,i,）变迁到,下一状态,（节点,n,j,）,节点,n,i,称为,被扩展节点,（父节点）,节点,n,j,称为,n,i,的,子节点,节点,n,i,节点,n,j,2026/4/10 周五,44,（,1,）搜索术语,3,、路径,节点,n,i,到,n,j,的路径是由相邻节点间的,弧线构成的折线,要求路径是无环的,4,、路径代价,相邻节点,n,i,和,n,i+1,间的,路径代价,记为,C(n,i,n,i+1,),通常令,任意相邻节点间的路径代价相同,，并以路径长度,1,指示。,即,C(n,i,n,i+1,)=1,。,状态空间搜索,2.,一般图搜索策略,节点,n,i,节点,n,i+1,节点,n,j,2026/4/10 周五,45,状态空间搜索,2.,一般图搜索策略,（,1,）搜索术语,4,、路径代价,目标状态节点,n,g,节点,n,i,节点,n,k,C(n,k,n,g,),C(n,i,n,k,),C(n,i,n,g,),2026/4/10 周五,46,状态空间搜索,2.,一般图搜索策略,（,2,）一般图搜索算法,符号说明：,s,-,初始状态节点,G,-,搜索图,OPEN,-,存放,待扩展节点,的表,CLOSE,-,存放,已被扩展的节点,的表,MOVE-FIRST(OPEN)-,取,OPEN,表首的节点,作为,当前要被扩展的节点,n,，同时,将节点,n,移至,CLOSE,表,一般图搜索算法划分为二个阶段：,1,、初始化,2,、搜索循环,2026/4/10 周五,47,状态空间搜索,2.,一般图搜索策略,（,2,）一般图搜索算法,算法划分为二个阶段：,1,、初始化,建立,只包含初始状态节点,s,的搜索图,G:=s,OPEN,:=s,CLOSE,:=,2,、搜索循环,MOVE-FIRST(OPEN)-,取出,OPEN,表首的节点,n,作为扩展的节点，同时将其移到,close,表,扩展出,n,的子节点,插入,搜索图,G,和,OPEN,表,适当的标记和修改指针,排序,OPEN,表,通过循环地执行该算法，,搜索图,G,会因不断有新节点加入而逐步长大，直到搜索到目标节点。,2026/4/10 周五,48,以下面的八数码为例，看一般图的搜索算法,初始布局,目标布局,移动数码,状态空间搜索,2.,一般图搜索策略,2026/4/10 周五,49,2026/4/10 周五,50,2026/4/10 周五,51,2026/4/10 周五,52,2026/4/10 周五,53,2026/4/10 周五,54,2026/4/10 周五,55,2026/4/10 周五,56,2026/4/10 周五,57,2026/4/10 周五,58,2026/4/10 周五,59,2026/4/10 周五,60,2026/4/10 周五,61,2026/4/10 周五,62,2026/4/10 周五,63,2026/4/10 周五,64,2026/4/10 周五,65,2026/4/10 周五,66,2026/4/10 周五,67,2026/4/10 周五,68,状态空间搜索,2.,一般图搜索策略,（,2,）一般图搜索算法,搜索过程中的指针修改,节点,n,扩展后,的子节点分为,3,类,：,(i),全新节点,(ii),已出现在,OPEN,表,中的节点,(iii),已出现的,CLOSE,表,中的节点,指针标记和修改的方法：,(i),类节点：加入,OPEN,表，建立从子节点到父节点,n,的指针,(ii),类节点、,(iii),类节点,比较,经由,老父节点,、,新父节点,n,到达,初始状态节点,的,路径代价,经由节点,n,的代价比较小，则移动子节点指向老父节点的指针，改为指向新父节点,n,(iii),类节点还得从,CLOSE,表中移出，重新加入,OPEN,表,。,2026/4/10 周五,69,状态空间搜索,2.,一般图搜索策略,S,n4,ni,nj,n1,n2,n3,n31,n32,节点,ni,是当前扩展的节点；,扩展出,4,个后续节点；,n1,、,n2,是新节点,，,只需建立指向父节点的指针，并加入,OPEN,表,；,2026/4/10 周五,70,状态空间搜索,2.,一般图搜索策略,S,n4,ni,nj,n1,n2,n3,n31,n32,n4,已经存在于,OPEN,表，并且已有父节点,nj,n4,经,nj,的路径代价大,取消,n4,指向,nj,的指针,改为建立,n4,指向新父节点,ni,的指针,n3,已经存在于,CLOSE,表，并且已有父节点,nj,需要做和,n4,同样的比较和指针修改工作。并且要重新加入,open,表。,2026/4/10 周五,71,3.3,盲目搜索,提高搜索效率的关键,优化,OPEN,表中节点的排序方式,。,简单的排序策略,按预先确定的顺序或随机地排序新加入到,OPEN,表中的节点。,常用的简单方式：,宽度优先,扩展当前节点后生成的子节点总是置于,OPEN,表的后端，即,OPEN,表作为,队列,使用，,先进先出,，使搜索优先向,横广,方向发展。,深度优先,扩展当前节点后生成的子节点总是置于,OPEN,表的前端，即,OPEN,表作为,栈,使用，,后进先出,，使搜索优先向,纵深,方向发展。,2026/4/10 周五,72,宽度优先,宽度优先,扩展当前节点后生成的子节点总是,置于,OPEN,表的后端,，即,OPEN,表,作为,队列,，,先进先出,，使,搜索优先向横向方向发展,。,过程：指从初始节点,S,0,开始，向下逐层搜索，在,n,层节点未搜索完之前，不进入,n+1,层搜索。,同层节点的搜索次序可以任意,。即先按生成规则生成第一层节点，在该层全部节点中沿宽,(,广,),度进行横向扫描，检查目标节点,Sg,是否在这些子节点中。若没有,则再将所有笫一层节点逐一扩展，得到第二层节点。并逐一检查第二层节点中是否包含有,S,g,，如此依次按照先生成、先检查、先扩展的原则进行下去，直到发现,S,g,为止,2026/4/10 周五,73,宽度优先实例,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,9,10,11,12,13,14,15,16,17,2026/4/10 周五,74,宽度优先搜索,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做,宽度优先搜索。,这种搜索是逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。,“先产生的节点先扩展”,2026/4/10 周五,75,(1),把初始节点,S,0,，放入,OPEN,表。,(2),如果,OPEN,表为空。则问题无解，失败并退出。,(3),把,OPEN,表中的第一个节点取出放入,CLOSE,表中，并按顺序冠以编号,n,；,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，成功并退出。,(5),若节点,n,不可扩展，则转第,(2),步；,(6),扩展节点,n,，将其子节点放到,OPEN,表的,尾部,，并为每一个子节点都配置指向父节点的指针，然后转第,(2),步。,采用队列结构，宽度优先算法可以表示如下：,2026/4/10 周五,76,例,通过挪动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。积木,A,在顶部，积木,B,在顶中间，积木,C,在底部。请画出按照宽度优先搜索策略所产生的搜索树。,这个问题的唯一操作算子为,MOVE(X,Y),，即积木,X,搬到,Y,（积木或桌面）上面。如,“,挪动积木,A,到桌面上表示为,MOVE(A,Table),。该操作算子可运用的先决条件是：,（,1,）被挪动积木的顶部必须为空。,（,2,）如,Y,是积木（不是桌面），则积木,Y,的顶部也必须为空。,（,3,）同一状态下，运用操作算子的次数不得多于一次。,2026/4/10 周五,77,积木问题的宽度优先搜索树,2026/4/10 周五,78,宽度优先搜索的性质,当问题有解时，,一定,能找到解,(,完备性,),当问题为单位代价时，且问题有解时，,一定能找到最优解（最优性）,方法与问题无关，具有通用性,效率较低,属于图搜索方法,2026/4/10 周五,79,宽度优先搜索,是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低。,宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的问题。,宽度优先搜索优点：,目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且,是最小（即最短路径）的节点。,宽度优先搜索的优点和缺点,2026/4/10 周五,80,深度优先,深度优先,扩展当前节点后生成的子节点总是,置于,OPEN,表的前端,，即,OPEN,表,作为,栈,，,后进先出,，使,搜索优先向纵深方向发展,。,过程：从初始节点,S,0,开始，按生成规则生成下一级各子节点，检查是否出现目标节点,S,g,；若未出现，则按“最晚生成的子节点优先扩展”的原则，再用生成规则生成再下一级的子节点，再检查是否出现,S,g,；若仍未出现，则再扩展最晚生成的子节点。如此下去，沿着最晚生成的子节点分枝，逐级“纵向”深入搜索。,2026/4/10 周五,81,深度优先实例,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,6,8,9,11,13,14,16,18,19,1 2 3,8 4,7 6 5,目标,5,7,10,12,15,17,20,21,2026/4/10 周五,82,深度优先搜索,在深度优先搜索中，首先扩展最新产生的,(,最深的,),节点，深度 相等的节点可以任意排列。,“,最晚产生的节点最先扩展,”,起始节点深度为,0,任何其他节点的深度等于其父辈节点深度加上,1,:,d,n,=d,n-1,+1,2026/4/10 周五,83,深度优先搜索,很明显这样做，,不一定,找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿着一条路线无限制地扩展下去，这当然是不允许的。,为保证找到解，应选择适当的,深度界限,，或者采取不断加大深度界限的办法，反复搜索，直到找到解。这种改进的方法叫做,迭代加深搜索,。,2026/4/10 周五,84,(1),把初始节点,S,0,放入,OPEN,表；,(2),如果,OPEN,表为空，则问题无解，失败并退出。,(3),把,OPEN,表中的第一个节点取出放入,CLOSE,表中，并按顺序冠以编号,n,；,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，成功并退出。,(5),若节点,n,不可扩展，则转第,(2),步；,(6),扩展节点,n,，将其子节点放到,OPEN,表的,首部,，并为其配置指向父节点的指针，然后转第,(2),步。,基于栈实现的深度优先搜索算法：,2026/4/10 周五,85,例,卒子穿阵问题,:,要求一卒子从顶部通过图所示的列阵到达底部。要求卒子行进中不可进入到代表敌兵驻守的区域内（标注,1,），并不准后退。,假定限制值为,5,。请画出按照深度优先搜索策略所产生的搜索树,2026/4/10 周五,86,卒子穿阵的深度优先搜索树,2026/4/10 周五,87,深度优先搜索的性质,一般不能保证找到最优解,当深度限制不合理时，,可能找不到解,，可以将算法改为,可变深度限制,最坏情况时，搜索空间等同于穷举,是一个通用的与问题无关的方法,2026/4/10 周五,88,深度优先搜索,的,优点,是,比宽度优先搜索算法需要较少的空间,，该算法只需要保存搜索树的一部分，它由,当前正在搜索的路径和该路径上还没有完全展开的节点标志所组成,。,深度优先搜索的存储器要求是深度约束的线性函数。,深度优先搜索的优点,2026/4/10 周五,89,深度优先搜索的缺点,既不是完备的，也不是最优的。,主要问题是可能,搜索到了错误的路径上,。很多问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，则深度优先搜索会一直搜索下去，而不会回到正确的路径上。这样一来对于这些问题，深度优先搜索要么陷入无限的循环而不能给出一个答案，要么最后找到一个答案，但路径很长而且不是最优的答案。,2026/4/10 周五,90,比较,适用场合,深度优先,当一个问题有多个解答或多条解答路径，且只须找到其中一个时；,往往应对搜索深度加以限制,。,宽度优先,确保搜索到,最短的解答路径,。,共同优缺点：,可直接应用一般图搜索算法实现，不需要设计特别的节点排序方法，从而简单易行，适合于许多复杂度不高的问题求解任务。,节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解答，所以也称为,盲目搜索,。,2026/4/10 周五,91,有界深度搜索和迭代加深搜索,有界深度优先搜索,过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深度限制,dm,，当深度达到了,dm,的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。,2026/4/10 周五,92,(1),把初始节点,S,0,放入,OPEN,表中，置,S,0,的深度,d(S,0,)=0,。,(2),如果,OPEN,表为空，则问题无解，失败并退出。,(3),把,OPEN,表中的第一个节点取出放入,CLOSE,表中。并按顺序冠以编号,n,。,(4),考察节点,n,是否为目标节点。若是，则求得了问题的解，成功并退出。,(5),如果节点,n,的深度,d(n)=dm,，则转第,(2),步,。,(6),如果节点,n,不可扩展，则转第,(2),步。,(7),扩展节点,n,。将其子节点放入,OPEN,表的,首部,，并为其配置指向父节点的指针。然后转第,(2),步。,有界深度搜索算法,2026/4/10 周五,93,策略说明,:,（,1,）,深度限制,dm,很重要,。,当问题有解，且解的路径长度小于或等于,dm,时，则搜索过程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。,但是当,dm,取得太小，解的路径长度大于,dm,时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。,2026/4/10 周五,94,（,2,）,深度限制,dm,不能太大,。当,dm,太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。,（,3,）有界深度搜索的主要问题是,深度限制值,dm,的选取,。,2026/4/10 周五,95,改进方法,：（迭代加深搜索）,先任意给定一个较小的数作为,dm,，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制,dm,，继续搜索。,2026/4/10 周五,96,迭代加深搜索,，试图尝试所有可能的深度限制：,首先深度为,0,，,然后深度为,1,，,然后为,2,，等等。,如果初始深度为,0,，则该算法只生成根节点，并检测它。,如果根节点不是目标，则深度加,1,，通过典型的深度优先算法，生成深度为,1,的树。,当深度限制为,m,时，树的深度为,m,。,2026/4/10 周五,97,迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。,然而对于很多问题，,这种多次的扩展负担实际上很小,，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。,2026/4/10 周五,98,Procedure Iterative-deepening,Begin,(1),设置当前深度限制,=1;,(2),把初始节点压入栈,并设置栈顶指针,;,(3)While,栈不空并且深度在给定的深度限制之内,do,Begin,弹出栈顶元素；,If,栈顶元素,=goal,返回并结束,;,Else,以任意的顺序把栈顶元素的子女压入栈中,;,End,End whild,(4),深度限制加,1,并返回,2;,End.,迭代加深搜索算法,2026/4/10 周五,99,总结,宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法。,宽度优先搜索,需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。,2026/4/10 周五,100,迭代加深搜索,对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先搜索的优点。,和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样是适中的。,2026/4/10 周五,101,搜索最优策略的比较,表注：,b,是分支系数，,d,是解答的深度，,m,是搜索树的最大深度，,l,是深度限制。,2026/4/10 周五,102,3.4,启发式搜索,一般图搜索算法,常用的简单方式：,深度优先,宽度优先,【,缺点：节点排序的盲目性,】,在白白,搜索了大量无关的状态节点,后才碰到解答，,效率低,提高,一般图搜索,效率,的关键,优化,OPEN,表中节点的排序方式,盲目搜索,2026/4/10 周五,103,1,2,5,6,3,4,最理想情况：,每次排序后,OPEN,表,表首元素,n,总在解答路径上,20