第三章第三章 状态空间搜索策略状态空间搜索策略 第三章第三章 状态空间搜索策略状态空间搜索策略 3.1 3.1 搜索的概念及种类搜索的概念及种类3.2 3.2 盲目搜索策略盲目搜索策略3.3 3.3 启发式搜索策略启发式搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例1 1 走迷宫是人们熟悉的一种游戏，如图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示。我们通过例子引入状态空间搜索状态空间搜索的概念。第三章第三章 状态空间搜索策略状态空间搜索策略 迷宫的有向图表示走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。第三章第三章 状态空间搜索策略状态空间搜索策略 例例2 2 在一个33的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的初始棋局和目标棋局(如图)，给出数码的移动序列。该问题称为八数码难题或重排九宫问题。2831476581324765初始棋局目标棋局第三章第三章 状态空间搜索策略状态空间搜索策略 状态空间（图）是一类问题的抽象表示，有许多智力问题(如Hanoi塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在状态空间(图)中寻找目标或路径的问题。因此，研究状态空间搜索具有普遍意义。第三章第三章 状态空间搜索策略状态空间搜索策略 3.1 3.1 搜索的概念及种类搜索的概念及种类现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。搜索：是一种求解问题的方法，是寻找从问题初始事实到最终答案的推理路线的一种过程。搜索包含两层含义：一是根据问题的实际情况，按照一定的策略，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线；另一是找到的这条路线是时空复杂度最小的求解路线。3.1.1 3.1.1 搜索的概念搜索的概念第三章第三章 状态空间搜索策略状态空间搜索策略 盲目搜索：又称无信息搜索。即在搜索过程中，只按预先规定的搜索控制策略进行搜索。问题本身的特性对搜索控制策略没有任何影响，搜索带有盲目性，效率不高，只用于解决比较简单的问题。启发式搜索：又称有信息搜索。指在搜索求解过程中，根据问题本身的特性来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。搜索求解的效率高，易于求解复杂的问题，但抽取出问题的相关特性和信息难。3.1.2 3.1.2 搜索的种类搜索的种类搜索分为盲目搜索和启发式搜索两种。第三章第三章 状态空间搜索策略状态空间搜索策略 状态空间表示法：是一种用状态和算符表示问题的方法。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。状态空间图：状态空间的图示表示问题形式。状态空间图是一个有向图，节点表示状态，有向边（弧）表示算符。3.2 3.2 盲目搜索策略盲目搜索策略3.2.1 3.2.1 状态空间图的搜索策略状态空间图的搜索策略状态空间图对问题的求解就相当于在有向图上寻找一条从某一节点(初始状态节点)到另一节点(目标状态节点)的路径。第三章第三章 状态空间搜索策略状态空间搜索策略 搜索法求解问题的基本思想：首先将问题的初始状态(初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。第三章第三章 状态空间搜索策略状态空间搜索策略 节点扩展节点扩展 概念概念扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点。未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点。第三章第三章 状态空间搜索策略状态空间搜索策略 在对状态空间图搜索求解时，将未扩展的节点存于一个名为OPENOPEN的表中，而将已扩展的节点存于一个名为CLOSEDCLOSED的表中。状态空间图的一般搜索策略：状态空间图的一般搜索策略：第三章第三章 状态空间搜索策略状态空间搜索策略 搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点（已扩展的节点）。CLOSED表中存储的是一棵不断成长的搜索树。另一方面，还得不断地把待考查的节点（未扩展的节点）组织在一起，并做某种排列，以便控制搜索的方向和顺序。我们采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。第三章第三章 状态空间搜索策略状态空间搜索策略(1)(1)建立一个只含有初始节点建立一个只含有初始节点S S0 0的搜索图的搜索图G G，把把S S0 0放人放人OPENOPEN表中。表中。(2)(2)建立建立CLOSEDCLOSED表，且置为空表。表，且置为空表。(3)(3)判断判断OPENOPEN表是否为空表，若为空，则问表是否为空表，若为空，则问题无解，退出。题无解，退出。(4)(4)若若OPENOPEN表非空，选择表非空，选择OPENOPEN表中的第一个表中的第一个节点，把它从节点，把它从OPENOPEN表移出，并放人表移出，并放人CLOSEDCLOSED表中，将此节点记为节点表中，将此节点记为节点n n。(5)(5)考察节点考察节点n n是否为目标节点，若是，则问是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从题有解，并成功退出。问题的解即可从图图G G中沿着指针从中沿着指针从n n到到S S0 0的这条路径得到。的这条路径得到。(6)(6)扩展节点扩展节点n n生成一组不是生成一组不是n n的祖先的后继的祖先的后继节点，并将它们记为集合节点，并将它们记为集合M M，将，将M M中的这中的这些节点作为些节点作为n n的后继节点加入图的后继节点加入图G G中。中。(7)(7)对那些对那些未曾在未曾在G G中出现过中出现过的的M M中的节中的节点，设置一个指向父节点点，设置一个指向父节点(即节点即节点n n)的指针，并把这些节点加入的指针，并把这些节点加入OPENOPEN表中；对于表中；对于已在已在G G中出现过中出现过的的M M中的中的那些节点，确定是否需要修改指向那些节点，确定是否需要修改指向父节点父节点(n n节点节点)的指针；对于那些的指针；对于那些先前已在先前已在G G中出现中出现并且已在并且已在CLOSEDCLOSED表中的那些表中的那些M M中的节点，确定是否中的节点，确定是否需要修改通向它们后继节点的指针。需要修改通向它们后继节点的指针。(8)(8)按某一任意方式或按某种策略重排按某一任意方式或按某种策略重排OPENOPEN表中节点的顺序表中节点的顺序。(9)(9)转第转第(3)(3)步。步。算法算法3.13.1 状态空间图的一般搜索算法状态空间图的一般搜索算法第三章第三章 状态空间搜索策略状态空间搜索策略 第三章第三章 状态空间搜索策略状态空间搜索策略 在搜索过程中，生成了一个图G，它是问题状态空间图的一部分，称为搜索图。由搜索图G中的所有节点及设置的指向父节点的反向指针，所构成的集合T，称为搜索树。在搜索过程中，问题的解就是从初始节点So到目标节点路径上的算符所构成的序列。路径是通过目标节点按设置的指针指向初始节点So回溯而得到的。第三章第三章 状态空间搜索策略状态空间搜索策略 3.2.2 3.2.2 宽度优先搜索策略宽度优先搜索策略宽度优先搜索又称为广度优先搜索。基本思想：是从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点。在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“先入先出”，即先进入的节点排在前面，后进入的节点排在后面。第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.23.2 状态空间图的宽度优先搜索算法状态空间图的宽度优先搜索算法(1)(1)把初始节点把初始节点S S0 0放人放人OPENOPEN表中。表中。(2)(2)如果如果OPENOPEN表是空表，则没有解，失败退出；否则继续。表是空表，则没有解，失败退出；否则继续。(3)(3)把把OPENOPEN表中的第一个节点表中的第一个节点(记为节点记为节点n n)移出，并放人移出，并放人CLOSEDCLOSED表中。表中。(4)(4)判断节点判断节点n n是否为目标节点，若是，则求解结束，并用是否为目标节点，若是，则求解结束，并用回溯法找出解的路径，退出；否则继续执行回溯法找出解的路径，退出；否则继续执行(5)(5)。(5)(5)若节点若节点n n不可扩展，转第不可扩展，转第(2)(2)步；否则继续执行步；否则继续执行(6)(6)步。步。(6)(6)对节点对节点n n进行扩展，将它的所有后继节点放人进行扩展，将它的所有后继节点放人OPENOPEN表的表的末端，并为这些后继节点设置指向父节点末端，并为这些后继节点设置指向父节点n n的指针，然的指针，然后转第后转第(2)(2)步。步。第三章第三章 状态空间搜索策略状态空间搜索策略 第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.13.1 八数码难题：设在33的一个方格棋盘上，摆放着8个数码1、2、3、4、5、6、7、8，有一个方格是空格，其初始状态如下图(a)所示，要求对空格执行下列的操作(或算符)：左移，上移，右移，下移。使8个数据最终按下图(b)的格式摆放，图(b)称为目标状态Sg。要求寻找从初始状态到目标状态的路径。2831476512384765S0(a)初始状态Sg(b)目标状态第三章第三章 状态空间搜索策略状态空间搜索策略 解的路径为解的路径为:S So o3 38162781627SgSg第三章第三章 状态空间搜索策略状态空间搜索策略 宽度优先搜索的特点：宽度优先搜索的特点：搜索盲目性较大，效率低。当目标节点距离初始节点较远时，将会产生大量的无用节点。搜索策略是完备的。只要问题有解，宽度优先搜索总可以找到它的解，而且是搜索树中，从初始节点到目标节点的路径最短的解。第三章第三章 状态空间搜索策略状态空间搜索策略 基本思想：首先扩展最新产生的(即最深的)节点。即从初始节点So开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依次类推，一直搜索下去。当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“后入先出”，即后进入的节点排在前面，先进入的节点排在后面。3.2.3 3.2.3 深度优先搜索深度优先搜索第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.33.3 状态空间图的深度优先搜索算法状态空间图的深度优先搜索算法(1)把初始节点S0放人OPEN表；(2)如果OPEN表为空，则问题无解，退出；(3)从OPEN表中将其第一个节点(节点n)移出，放入已扩展节点表CLOSED中；(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解的路径，退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其后继节点放到OPEN表的前端，并为其设置指向节点n的指针，然后转第(2)步。第三章第三章 状态空间搜索策略状态空间搜索策