《第6章-搜索策略概要优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第6章-搜索策略概要优秀PPT.ppt（89页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学问工程Knowledge Engineering主讲：杨利英主讲：杨利英西安电子科技高校计算机学院西安电子科技高校计算机学院E_mail：yangliying1208163 第六章第六章 搜寻策略搜寻策略6.1 基本概念基本概念6.2 状态空间的搜寻策略状态空间的搜寻策略6.3 与与/或树的搜寻策略或树的搜寻策略6.4 搜寻的完备性与效率搜寻的完备性与效率6.1 基本概念 接受某种策略，在学问库中找寻可利用的学问，从而构造一条代价较小的推理路途，使问题得到解决的过程称为搜寻。6.1.1 什么是搜寻什么是搜寻6.1.1 什么是搜寻搜寻分为盲目搜寻和启发式搜寻。盲目搜寻是依据预定的限制策略进行搜
2、寻，在搜寻过程中获得的中间信息不用来改进限制策略。启发式搜寻是在搜寻中加入了与问题有关的启启发式搜寻是在搜寻中加入了与问题有关的启发性信息，用以指导搜寻朝着最有希望的方向发性信息，用以指导搜寻朝着最有希望的方向前进，加速问题的求解过程并找到最优解。前进，加速问题的求解过程并找到最优解。6.1.2 状态空间表示法状态空间用状态空间用“状态状态”和和“算符算符”来表示问题。来表示问题。状态状态 状态用以描述问题在求解过程中不同时刻的状态，状态用以描述问题在求解过程中不同时刻的状态，一般用向量表示一般用向量表示算符算符使问题从一个状态转变为另一个状态的操作称为算使问题从一个状态转变为另一个状态的操作
3、称为算符。符。状态空间状态空间由全部可能出现的状态及一切可用算符所构成的集合由全部可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。称为问题的状态空间。回顾回顾状态空间示例：十五数码难题119151341275861321014119415131275861321014119151341275861321014119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顾回顾6.1.3 与/或树表示法对于一个困难问题，干脆求解往往比较
4、困对于一个困难问题，干脆求解往往比较困难。此时可通过下述方法进行简化：难。此时可通过下述方法进行简化：（1）分解）分解 （2）等价变换）等价变换回顾回顾6.1.3 与/或树表示法（1）分解把一个困难问题分解为若干个较为简洁的子问题，每个子问题又可接着分解。重复此过程，直到不须要再分解或者不能再分解为止。如此形成“与”树。（2）等价变换利用同构或同态的等价变换，把原问题变换为若干个较为简洁求解的新问题。如此形成“或”树。回顾回顾与/或树分解与等价变换可以结合起来运用，这样形成的图称为分解与等价变换可以结合起来运用，这样形成的图称为“与与/或树或树”回顾回顾由可解节点所构成，并且由这些可解节点可推
5、出初始节点由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树为可解节点的子树称为解树(t(t表示终止节点表示终止节点)。解树中确定。解树中确定包含初始节点。（它对应于原始问题）包含初始节点。（它对应于原始问题）解树解树回顾回顾6.2 状态空间的搜寻策略6.2 状态空间的搜寻策略盲目搜寻盲目搜寻搜寻按规定的路途进行，不运用与问题有关搜寻按规定的路途进行，不运用与问题有关的启发性信息；的启发性信息；适用于其状态空间图是树状结构的一类问题。适用于其状态空间图是树状结构的一类问题。启发式搜寻启发式搜寻 运用与问题有关的启发性信息，并以这些运用与问题有关的启发性信息，并以这些启发
6、性信息指导搜寻过程，可以高效地求解启发性信息指导搜寻过程，可以高效地求解结构困难的问题。结构困难的问题。搜寻的原则广度优先搜寻依据广度优先搜寻依据“先扩展出的节点先被考察先扩展出的节点先被考察”的原则进行搜寻；的原则进行搜寻；深度优先搜寻依据深度优先搜寻依据“后扩展出的节点先被考察后扩展出的节点先被考察”的原则进行搜寻；的原则进行搜寻；有界深度优先搜寻的原则与深度优先搜寻相同，有界深度优先搜寻的原则与深度优先搜寻相同，但是它规定了深度限界，使搜寻不得无限制地但是它规定了深度限界，使搜寻不得无限制地向纵深方向发展；向纵深方向发展；代价树的广度优先搜寻依据代价树的广度优先搜寻依据“哪个节点到根节哪
7、个节点到根节点的代价小就先考察哪个节点点的代价小就先考察哪个节点”的原则进行搜的原则进行搜寻；寻；代价树的深度优先搜寻依据代价树的深度优先搜寻依据“当前节点的哪个当前节点的哪个子节点到其父节点的代价小就先考察哪个子节子节点到其父节点的代价小就先考察哪个子节点点”的原则进行搜寻；的原则进行搜寻；局部择优搜寻依据局部择优搜寻依据“当前节点的哪个子节点到当前节点的哪个子节点到目标节点的估计代价小就先考察哪个子节点目标节点的估计代价小就先考察哪个子节点”的原则进行搜寻；的原则进行搜寻；全局择优搜寻依据全局择优搜寻依据“哪个节点到目标节点的估哪个节点到目标节点的估计代价小就先考察哪个节点计代价小就先考察
8、哪个节点”的原则进行搜寻；的原则进行搜寻；搜寻的原则6.2.1 状态空间的一般搜寻过程一个困难问题的状态空间一般都是特别浩大的。如一个困难问题的状态空间一般都是特别浩大的。如64阶梵塔问题共有阶梵塔问题共有3的的64次方个不同的状态。次方个不同的状态。把问题的全部状态空间都进行存储有时候是不行能的。把问题的全部状态空间都进行存储有时候是不行能的。把问题的全部状态空间都进行存储也是不必要的。因把问题的全部状态空间都进行存储也是不必要的。因为与解题有关的状态空间往往只是整个状态空间的一为与解题有关的状态空间往往只是整个状态空间的一部分，只要能生产并存储这部分状态空间就可以求出部分，只要能生产并存储
9、这部分状态空间就可以求出问题的解。问题的解。6.2.1 状态空间的一般搜寻过程如何产生问题须要的状态空间从而实现对问题的求解呢？如何产生问题须要的状态空间从而实现对问题的求解呢？答案就是搜寻技术。答案就是搜寻技术。搜寻技术基本思想：把问题的初始状态作为当前状态，选搜寻技术基本思想：把问题的初始状态作为当前状态，选择适用的算符对其操作，生产一组子状态，然后检查目标择适用的算符对其操作，生产一组子状态，然后检查目标状态是否在其中出现。若出现，则搜寻成功，找到了问题状态是否在其中出现。若出现，则搜寻成功，找到了问题的解，否则按某种搜寻策略从已生成的状态中再选择一个的解，否则按某种搜寻策略从已生成的状
10、态中再选择一个作为当前状态。重复上述过程，直到目标状态出现或者不作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符为止。再有可供操作的状态及算符为止。6.2.1 状态空间的一般搜寻过程OPEN表和表和CLOSE表表OPEN表用于存放刚生成的节点。对于不同的搜寻策略，节表用于存放刚生成的节点。对于不同的搜寻策略，节点在点在OPEN表中的排列依次是不同的。表中的排列依次是不同的。CLOSE表用于存放将要扩展的节点。对一个节点的扩展是表用于存放将要扩展的节点。对一个节点的扩展是指：用全部可适用的算符对该节点进行操作，生成一组子节指：用全部可适用的算符对该节点进行操作，生成一组
11、子节点点 OPEN表表状态节点父节点编号 状态节点 父节点CLOSE表搜寻的一般过程搜寻的一般过程1.把初始节点把初始节点S0放入放入OPEN表，并建立目前只包含表，并建立目前只包含S0的图，的图，记为记为G；2.检查检查OPEN表是否为空，若为空则问题无解，退出；表是否为空，若为空则问题无解，退出；3.把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSE表，并计该节表，并计该节点为点为n；4.考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出；退出；5.扩展节点扩展节点n，生成一组子节点。把其中不是节点，生成一组子节点。把其中
12、不是节点n先辈的先辈的那些子节点记做集合那些子节点记做集合M，并把这些子节点作为节点，并把这些子节点作为节点n的的子节点加入子节点加入G中；中；6.针对针对M中子节点的不同状况，分别进行如下处理：中子节点的不同状况，分别进行如下处理：7.对于那些未曾在对于那些未曾在G中出现过的中出现过的M成员设置一个指向父节成员设置一个指向父节点（即节点点（即节点n）的指针，并把它们放入）的指针，并把它们放入OPEN表；（不表；（不在在OPEN表）表）8.对于那些从前已经在对于那些从前已经在G中出现过的中出现过的M成员，确定是否须成员，确定是否须要修改它指向父节点的指针；（在要修改它指向父节点的指针；（在OP
13、EN表中）表中）9.对于那些从前已在对于那些从前已在G中出现并且已经扩展了的中出现并且已经扩展了的M成员，成员，确定是否须要修改其后继节点指向父节点的指针；（在确定是否须要修改其后继节点指向父节点的指针；（在CLOSE表中）表中）10.按某种搜寻策略对按某种搜寻策略对OPEN表中的节点进行排序；表中的节点进行排序；11.转第转第2步。步。搜寻的一般过程搜寻的一般过程对一般搜寻过程的一些说明对一般搜寻过程的一些说明w一个节点经一个算符操作后一般只生成一个子节一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时点。但适用于一个节点的算符可能有多个，此时就会生成一组子
14、节点。这些子节点中可能有些是就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。把这些先辈节点作为当前扩展节点的子节点。对一般搜寻过程的一些说明对一般搜寻过程的一些说明w一个新生成的节点，它可能是第一次被生成的一个新生成的节点，它可能是第一次被生成的节点，也可能是从前已作为其它节点的子节点节点，也可能是从前已作为其它节点的子节点被生成过，当前又作为另一个节点的子节点被被生成过，当前又作为另一个节点的子节点被再次生成。此时，它原委应选择哪个节点作为再次生成。此时，它原委应选择哪个节点
15、作为父节点？一般由原始节点到该节点的代价来确父节点？一般由原始节点到该节点的代价来确定，处于代价小的路途上的那个节点就作为该定，处于代价小的路途上的那个节点就作为该节点的父节点。节点的父节点。对一般搜寻过程的一些说明w在搜寻过程中，一旦某个被考察的节点是目标在搜寻过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。该目标节点路径上的算符构成。w假如在搜寻中始终找不到目标节点，而且假如在搜寻中始终找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜寻失表中不再有可供扩展的节点，则搜寻失败。败。对一般搜
16、寻过程的一些说明通过搜寻得到的图称为搜寻图，搜寻图是状态通过搜寻得到的图称为搜寻图，搜寻图是状态空间图的一个子集。由搜寻图中的全部节点及空间图的一个子集。由搜寻图中的全部节点及反向指针所构成的集合是一棵树，称为搜寻树。反向指针所构成的集合是一棵树，称为搜寻树。依据搜寻树可给出问题的解。依据搜寻树可给出问题的解。6.2.2 广度（宽度）优先搜寻基本思想：基本思想：从初始节点从初始节点S0起先，逐层地对节点进行扩起先，逐层地对节点进行扩展并考察它是否为目标节点。在第展并考察它是否为目标节点。在第n层的节点没层的节点没有全部扩展并考察之前，不对第有全部扩展并考察之前，不对第n1层的节点层的节点进行扩
17、展。进行扩展。OPEN表中节点总是按进入的先后依次排列，先表中节点总是按进入的先后依次排列，先进入的节点排在前面，后进入的排在后面。进入的节点排在前面，后进入的排在后面。广度优先搜寻过程1.把初始节点把初始节点S0放入放入OPEN表。表。2.假如假如OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSE表。表。4.考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。5.若节点若节点n不行扩展，则转第不行扩展，则转第2步。步。6.扩展节点
18、扩展节点n，将其子节点放入，将其子节点放入OPEN表的尾部，并为每一表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第个子节点都配置指向父节点的指针，然后转第2步。步。重排九宫的广度优先搜寻重排九宫的广度优先搜寻操作符：空格左移、上移、右移、下操作符：空格左移、上移、右移、下移移小插曲关于九宫问题射雕英雄传射雕英雄传 瑛姑的问题：将一至九这九个数字排成瑛姑的问题：将一至九这九个数字排成三列，不论纵横斜角，每三字相加都是三列，不论纵横斜角，每三字相加都是十五，如何排法？十五，如何排法？黄蓉的回答：九宫之义，法以灵龟，二黄蓉的回答：九宫之义，法以灵龟，二四为肩，六八为足，左三右七，戴九履四
19、为肩，六八为足，左三右七，戴九履一，五居中心。一，五居中心。幻方问题幻方问题中国人首先发觉了幻方中国人首先发觉了幻方 洛水神龟献奇图洛水神龟献奇图关于三阶幻方的奇异关于三阶幻方的奇异南宋杨辉 探讨幻方第一人 幻方问题幻方问题在我国古代称为“纵横图”，又叫“九宫算图”。南宋大数学家杨辉在1275年所著的续古摘奇算法续古摘奇算法两卷中，除了给出洛书中3阶幻方的构造方法外，还给出了4阶至10阶的幻方。杨辉对杨辉对3 3阶幻方的说明阶幻方的说明29435761816594211714310615138121三阶幻方(15)四阶幻方(34)欧美的幻方热德国画家和文艺理论家丢勒在德国画家和文艺理论家丢勒在
20、1514年创年创作的一幅铜版雕刻画悲伤中就有一作的一幅铜版雕刻画悲伤中就有一个个4阶幻方。阶幻方。名画悲伤现在珍藏于名画悲伤现在珍藏于大英博物馆。大英博物馆。富兰克林也投入了很大精力探讨幻方。富兰克林也投入了很大精力探讨幻方。名画悲伤名画悲伤广度优先算法中须要留意的问题1、对于随意一个可扩展的节点，总是依据固定的、对于随意一个可扩展的节点，总是依据固定的操作符的依次对其进行扩展（如前面重排九宫例操作符的依次对其进行扩展（如前面重排九宫例子中的空格左移、上移、右移、下移）。子中的空格左移、上移、右移、下移）。2、在对任一节点进行扩展的时候，假如所得的某、在对任一节点进行扩展的时候，假如所得的某个
21、子节点（状态）前面已经出现过，则马上将其个子节点（状态）前面已经出现过，则马上将其放弃，不再重复画出（不送入放弃，不再重复画出（不送入OPEN表）。表）。因此，广度优先搜寻的本质是：以初始节点为根节因此，广度优先搜寻的本质是：以初始节点为根节点，在状态空间图中依据广度优先的原则，生成点，在状态空间图中依据广度优先的原则，生成一棵搜寻树。一棵搜寻树。广度优先搜寻的特点优点：优点：只要问题有解，用广度优先搜寻总可以得到解，只要问题有解，用广度优先搜寻总可以得到解，而且得到的是路径最短的解。而且得到的是路径最短的解。缺点：缺点：广度优先搜寻盲目性较大，当目标节点距初始广度优先搜寻盲目性较大，当目标节
22、点距初始节点较远时将会产生很多无用节点，搜寻效率低。节点较远时将会产生很多无用节点，搜寻效率低。6.2.3 深度优先搜寻基本思想：从初始节点起先，在其子节点中选择一个节基本思想：从初始节点起先，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点进行考察，若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，始终如此向下搜寻。当到点中选择一个节点进行考察，始终如此向下搜寻。当到达某个子节点，且该子节点既不是目标节点又不能接着达某个子节点，且该子节点既不是目标节点又不能接着扩展时，才选择其兄弟节点进行考察。扩展时，才选择其兄弟节点进行考察。深度优先搜寻与广度优先搜寻的
23、唯一区分：广度优先搜深度优先搜寻与广度优先搜寻的唯一区分：广度优先搜寻是将节点寻是将节点n的子节点放入到的子节点放入到OPEN表的尾部，而深度优表的尾部，而深度优先搜寻是把节点先搜寻是把节点n的子节点放入到的子节点放入到OPEN表的首部。表的首部。深度优先搜寻过程1.把初始节点把初始节点S0放入放入OPEN表。表。2.假如假如OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSE表。表。4.考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。
24、退出。5.若节点若节点n不行扩展，则转第不行扩展，则转第2步。步。6.扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的首部，并为每表的首部，并为每一个子节点都配置指向父节点的指针，然后转第一个子节点都配置指向父节点的指针，然后转第2步。步。重排九宫的深度优先搜寻操作符：空格左移、上移、右移、下移深度优先搜寻的特点在深度优先搜寻中，搜寻一旦进入某个分支，就将沿着该在深度优先搜寻中，搜寻一旦进入某个分支，就将沿着该分支始终向下搜寻。假如目标节点恰好在此分支上，则可分支始终向下搜寻。假如目标节点恰好在此分支上，则可较快地得到解。但是，假如目标节点不在此分支上，而该较快地得到解。但是，假
25、如目标节点不在此分支上，而该分支又是一个无穷分支，则就不行能得到解。所以深度优分支又是一个无穷分支，则就不行能得到解。所以深度优先搜寻是不完备的，即使问题有解，它也不确定能求得解。先搜寻是不完备的，即使问题有解，它也不确定能求得解。用深度优先求得的解，不确定是路径最短的解。用深度优先求得的解，不确定是路径最短的解。本质：以初始节点为根节点，在状态空间图中依据深度优本质：以初始节点为根节点，在状态空间图中依据深度优先的原则，生成一棵搜寻树。先的原则，生成一棵搜寻树。6.2.4 有界深度优先搜寻 基本思想：基本思想：对深度优先搜寻引入搜寻深度界限（设为对深度优先搜寻引入搜寻深度界限（设为dm），当
26、搜），当搜寻深度达到了深度界限，而仍未出现目标节点时，寻深度达到了深度界限，而仍未出现目标节点时，就换一个分支进行搜寻。就换一个分支进行搜寻。“有界有界”是为了解决深度优先搜寻不完备的问题，避开陷是为了解决深度优先搜寻不完备的问题，避开陷入无穷分支的死循环。入无穷分支的死循环。有界深度优先搜寻过程把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n的深度d(n)=dm，则转第2步（此季节点n位于CLOSE表，但并未进行扩展）。
27、若节点n不行扩展，则转第2步。扩展节点n，将其子节点放入OPEN表的首部，为每一个子节点都配置指向父节点的指针，将每一个子节点的深度设置为d(n)+1，然后转第2步。对有界深度优先搜寻的说明假如问题有解，且其路径长度假如问题有解，且其路径长度dmdm，则上，则上述搜寻过程确定能求得解。但是，若解的述搜寻过程确定能求得解。但是，若解的路径长度路径长度dm,dm,则上述搜寻过程就得不到解。则上述搜寻过程就得不到解。这说明在有界深度优先搜寻中，深度界限这说明在有界深度优先搜寻中，深度界限的选择是很重要的。的选择是很重要的。要恰当地给出要恰当地给出dmdm的值是比较困难的。即使的值是比较困难的。即使能
28、求出解，它也不确定是最优解。能求出解，它也不确定是最优解。有界深度优先搜寻的改进1.先随意设定一个较小的数作为先随意设定一个较小的数作为dm，然后进行上，然后进行上述的有界深度优先搜寻，当搜寻达到了指定的述的有界深度优先搜寻，当搜寻达到了指定的深度界限深度界限dm仍未发觉目标节点，并且仍未发觉目标节点，并且CLOSE表表中仍有待扩展节点时，就将这些节点送回中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限表，同时增大深度界限dm，接着向下搜寻。如，接着向下搜寻。如此不断地增大此不断地增大dm，只要问题有解，就确定可以，只要问题有解，就确定可以找到它。但此时找到的解不确定是最优解。
29、找到它。但此时找到的解不确定是最优解。有界深度优先搜寻的改进2.为了找到最优解，可增设一个表为了找到最优解，可增设一个表R，每找到目，每找到目标节点标节点Sg后，就把它放入到后，就把它放入到R的前面，并令的前面，并令dm等于该目标节点所对应的路径长度，然后等于该目标节点所对应的路径长度，然后接着搜寻。由于后求得的解的路径长度不会接着搜寻。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以最终求得超过先求得的解的路径长度，所以最终求得的解确定是最优解。的解确定是最优解。重排九宫的有界深度优先搜寻设深度界限dm46.2.5 代价树的广度优先搜寻边上标有代价边上标有代价(或费用或费用)的树称
30、为的树称为代价树代价树。用用g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价，的代价，用用c(x1,x2)表示从父节点表示从父节点x1到子节点到子节点x2的的代价，则有：代价，则有：g(x2)=g(x1)+c(x1,x2)6.2.5 代价树的广度优先搜寻每次从每次从OPENOPEN表中选择节点往表中选择节点往CLOSECLOSE表传送时，总是表传送时，总是选择其中代价最小的节点。也就是说，选择其中代价最小的节点。也就是说，OPENOPEN表中的表中的节点在任一时刻都是按其代价从小到大排序的。代节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面。价小
31、的节点排在前面，代价大的节点排在后面。假如问题有解，代价树的广度优先搜寻确定可以求假如问题有解，代价树的广度优先搜寻确定可以求得解，并且求出的是最优解。得解，并且求出的是最优解。该算法应用的条件该算法应用的条件:该算法是针对代价树的算法。该算法是针对代价树的算法。为了接受该算法对图进行搜寻，必需先将图转换为为了接受该算法对图进行搜寻，必需先将图转换为代价树。代价树。代价树广度优先搜寻过程1.把初始节点把初始节点S0放入放入OPEN表，令表，令g(S0)=0。2.假如假如OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n
32、）取出放入）取出放入CLOSE表。表。4.考察节点考察节点n是否为目标节点。若是，则求得了问题的解，退是否为目标节点。若是，则求得了问题的解，退出。出。5.若节点若节点n不行扩展，则转第不行扩展，则转第2步。步。6.扩展节点扩展节点n，为每一个子节点都配置指向父节点的指针，并，为每一个子节点都配置指向父节点的指针，并将各子节点放入将各子节点放入OPEN表中；计算各子节点的代价，按各节表中；计算各子节点的代价，按各节点的代价对点的代价对OPEN表中的全部节点进行排序表中的全部节点进行排序(按从小到大的按从小到大的依次依次)，然后转第，然后转第2步。步。代价树示例（王永庆 教材P271 例6.7）
33、图到代价树的转换求A到E的最小费用交通路途代价树的广度优先搜寻6.2.6 代价树的深度优先搜寻在代价树的广度优先搜寻中，每次都是从在代价树的广度优先搜寻中，每次都是从OPEN表的全体节点中选择一个代价最小的节表的全体节点中选择一个代价最小的节点送入点送入CLOSE表进行考察表进行考察在代价树的深度优先搜寻中，是从刚扩展出的在代价树的深度优先搜寻中，是从刚扩展出的子节点中选择一个代价最小的节点送入子节点中选择一个代价最小的节点送入CLOSE表进行考察表进行考察代价树的深度优先搜寻过程把初始节点S0放入OPEN表，令g(S0)=0。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记
34、为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不行扩展，则转第2步。扩展节点n，将其子节点按“边”代价从小到大的依次放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。代价树的深度优先搜寻是不完备的。总 结 1、上述各种搜寻方法的本质是，以初始节点为根节点，依据既定的策略对状态空间图进行遍历，并希望能够尽早发觉目标节点。2、由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜寻方法。6.2.7 启发式搜寻盲目搜寻具有较大的盲目性，产生的无用盲目搜寻具有较大的盲目性，产生的无用节点较多，效率不高。节点较多，效率不
35、高。启发式搜寻接受问题自身的特性信息，以启发式搜寻接受问题自身的特性信息，以指导搜寻朝着最有希望的方向前进。这种指导搜寻朝着最有希望的方向前进。这种搜寻针对性较强，因而效率较高。搜寻针对性较强，因而效率较高。1.启发性信息与估价函数可用于指导搜寻过程，且与具体问题有关的信息称为可用于指导搜寻过程，且与具体问题有关的信息称为启发性信息。启发性信息。用于评估节点重要性的函数称为估价函数。其一般形用于评估节点重要性的函数称为估价函数。其一般形式为：式为：f(x)=g(x)+h(x)其中其中g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；h(x)是是从节点从节点x到目标节点到目标
36、节点Sg的最优路径的代价的估计，它的最优路径的代价的估计，它体现了问题的启发性信息，称为启发函数。体现了问题的启发性信息，称为启发函数。f(x)确确定节点在定节点在OPEN表中的次序。表中的次序。1.启发性信息与估价函数g(x)指出了搜寻的横向趋势，有利于搜寻的完备指出了搜寻的横向趋势，有利于搜寻的完备性，但影响搜寻的效率。性，但影响搜寻的效率。h(x)指出了搜寻的纵向趋势，有利于提高搜寻的指出了搜寻的纵向趋势，有利于提高搜寻的效率，但影响搜寻的完备性。效率，但影响搜寻的完备性。确定确定f(x)时要使时要使g(x)+h(x)各占适当比重。各占适当比重。启发函数示例设有如下结构的移动将牌游戏：设
37、有如下结构的移动将牌游戏：游戏规则：游戏规则：当一个牌移入相邻的空位置时，费用为一个单位。当一个牌移入相邻的空位置时，费用为一个单位。一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加1。要求：把全部的要求：把全部的B都移至都移至W的右边，请设计启发函数的右边，请设计启发函数h(x)。解：依据要求可知，解：依据要求可知，W左边的左边的B越少越接近目标，因此可用越少越接近目标，因此可用W左边左边B的的个数作为个数作为h(x),即即h(x)=3(每个每个W左边左边B的个数的总和的个数的总和)这里乘以系数这里乘以系数3是为了扩大是为了扩大
38、h(x)在在f(x)中的比重。中的比重。BBBWWWEBEBW W BW例如下面这一状态：h(x)=3(2+2+3)=212.局部择优搜寻局部择优搜寻是一种启发式搜寻方法，局部择优搜寻是一种启发式搜寻方法，是对深度优先搜寻方法的一种改进。是对深度优先搜寻方法的一种改进。基本思想：当一个节点被扩展以后，按基本思想：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点。择最小者作为下一个要考察的节点。局部择优搜寻过程把初始节点S0放入OPEN表，计算f(S0)。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为
39、节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不行扩展，则转第2步。扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的依次放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。2.局部择优搜寻w在局部择优搜寻中，若令在局部择优搜寻中，若令f(x)=g(x)，则局部择，则局部择优搜寻就成为代价树的深度优先搜寻。优搜寻就成为代价树的深度优先搜寻。w在局部择优搜寻中，若令在局部择优搜寻中，若令f(x)=d(x)，这里，这里d(x)表示节点表示节点x的深度，则局部择优搜寻就成为深的深度，则局部择优搜寻就成为
40、深度优先搜寻。度优先搜寻。w因此：深度优先搜寻、代价树的深度优先搜寻因此：深度优先搜寻、代价树的深度优先搜寻均为局部择优搜寻的特例。均为局部择优搜寻的特例。3.全局择优搜寻每当要选择下一个节点进行考察时，局部择优每当要选择下一个节点进行考察时，局部择优搜寻只是从刚生成的子节点中选择一个估价值搜寻只是从刚生成的子节点中选择一个估价值最小的节点。其选择范围比较窄。最小的节点。其选择范围比较窄。每当要选择下一个节点进行考察时，全局择优每当要选择下一个节点进行考察时，全局择优搜寻每次总是从搜寻每次总是从OPEN表的全体节点中选择一表的全体节点中选择一个估价值最小的节点。个估价值最小的节点。全局择优搜寻
41、过程把初始节点S0放入OPEN表，计算f(S0)。假如OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不行扩展，则转第2步。扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的依次进行排序，然后转第2步。3.全局择优搜寻w在全局择优搜寻中，若令在全局择优搜寻中，若令f(x)=g(x)，则它就成，则它就成为代价树的广度优先搜寻。为代价树的广度优先搜寻。w在全局择优搜寻中
42、，若令在全局择优搜寻中，若令f(x)=d(x)，这里，这里d(x)表表示节点示节点x的深度，则它就成为广度优先搜寻。的深度，则它就成为广度优先搜寻。w因此：广度优先搜寻、代价树的广度优先搜寻是因此：广度优先搜寻、代价树的广度优先搜寻是全局择优搜寻的两个特例。全局择优搜寻的两个特例。重排九宫问题的全局择优搜寻树设估价函数为 f(x)=d(x)+h(x)，其中，d(x)表示节点x的深度，h(x)表示节点x的格局与目标节点格局不相同的牌数。6.3 与/或树的搜寻策略6.3.1 与与/或树的一般搜寻过程或树的一般搜寻过程6.3.2 博弈树的启发式搜寻博弈树的启发式搜寻6.3.3 剪枝技术剪枝技术6.3
43、 与/或树的搜寻策略6.3 与/或树的搜寻策略 用与用与/或树方法求解问题时，首先要定义问题的描述方法及或树方法求解问题时，首先要定义问题的描述方法及分解和变换问题的算符，然后就可以用它们通过搜寻生成与分解和变换问题的算符，然后就可以用它们通过搜寻生成与/或树，从而求得原始问题的解。或树，从而求得原始问题的解。在与在与/或树中，由可解子节点来确定其父节点、祖父节点等或树中，由可解子节点来确定其父节点、祖父节点等为可解节点的过程称为可解标示过程；由不行解子节点来确为可解节点的过程称为可解标示过程；由不行解子节点来确定其父节点、祖父节点等为不行解节点的过程称为不行解标定其父节点、祖父节点等为不行解
44、节点的过程称为不行解标示过程；示过程；在与在与/或树搜寻过程中，将反复运用可解和不行解标示过程，或树搜寻过程中，将反复运用可解和不行解标示过程，直到初始节点被标示为可解或不行解节点为止。直到初始节点被标示为可解或不行解节点为止。6.3.1 与/或树的一般搜寻过程1.把原始问题作为初始节点把原始问题作为初始节点S0，并把，并把S0作为当前作为当前节点；节点；2.应用分解或等价算法对当前节点进行扩展；应用分解或等价算法对当前节点进行扩展；3.为每个子节点设置指向父节点的指针；为每个子节点设置指向父节点的指针；4.选择合适的子节点作为当前节点，反复执行第选择合适的子节点作为当前节点，反复执行第2和第
45、和第3步，期间将反复运用可解和不行解标示过步，期间将反复运用可解和不行解标示过程，直到初始节点被标示为可解或不行解节点为程，直到初始节点被标示为可解或不行解节点为止。止。5.由这个搜寻过程形成的节点和指针结构称为搜寻由这个搜寻过程形成的节点和指针结构称为搜寻树。树。与与/或树的广度优先搜寻或树的广度优先搜寻1.把初始节点把初始节点S0放入放入OPEN表。表。2.把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSE表。表。3.若节点若节点n可扩展，则做如下工作。可扩展，则做如下工作。4.扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的尾部，并
46、为每个子节点配置指向表的尾部，并为每个子节点配置指向父节点的指针，以备标示过程运用。父节点的指针，以备标示过程运用。5.考察这些子节点中是否有终止节点。如有，则标示这些终止节点为可解节考察这些子节点中是否有终止节点。如有，则标示这些终止节点为可解节点，并用可解标示过程对其先辈节点中的可解节点进行标示。假如初始节点，并用可解标示过程对其先辈节点中的可解节点进行标示。假如初始节点点S0也被标示为可解节点，则得到了解树，搜寻成功，退出；假如不能也被标示为可解节点，则得到了解树，搜寻成功，退出；假如不能确定确定S0为可解节点，则从为可解节点，则从OPEN表中删去具有可解先辈的节点。表中删去具有可解先辈
47、的节点。6.转第转第2步。步。7.若节点若节点n不行扩展，则做如下工作。不行扩展，则做如下工作。8.标示节点标示节点n为不行解节点。为不行解节点。9.用不行解标示过程对用不行解标示过程对n的先辈节点中的不行解节点进行标示。假如初始节的先辈节点中的不行解节点进行标示。假如初始节点点S0也被标示为不行解节点，则搜寻失败，退出；假如不能确定也被标示为不行解节点，则搜寻失败，退出；假如不能确定S0为不为不行解节点，则从行解节点，则从OPEN表中删去具有不行解先辈的节点。表中删去具有不行解先辈的节点。10.转第转第2步。步。与与/或树的（有界）深度优先搜寻或树的（有界）深度优先搜寻1.把初始节点把初始节
48、点S0放入放入OPEN表。表。2.把把OPEN表的第个节一点（记为节点表的第个节一点（记为节点n）取出放入）取出放入CLOSE表。表。3.若节点若节点n的深度大于等于深度界限，则转第的深度大于等于深度界限，则转第5步中的第步中的第。4.若节点若节点n可扩展，则做如下工作。可扩展，则做如下工作。5.扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的首部，并为每个子节点配置指向父节点的表的首部，并为每个子节点配置指向父节点的指针，以备标示过程运用。指针，以备标示过程运用。6.考察这些子节点中是否有终止节点。如有，则标示这些终止节点为可解节点，并考察这些子节点中是否有终止节点。如有，则标
49、示这些终止节点为可解节点，并用可解标示过程对其先辈节点中的可解节点进行标示。假如初始节点用可解标示过程对其先辈节点中的可解节点进行标示。假如初始节点S0也被标示也被标示为可解节点，则得到了解树，搜寻成功，退出；假如不能确定为可解节点，则得到了解树，搜寻成功，退出；假如不能确定S0为可解节点，则为可解节点，则从从OPEN表中删去具有可解先辈的节点。表中删去具有可解先辈的节点。7.转第转第2步。步。8.若节点若节点n不行扩展，则做如下工作。不行扩展，则做如下工作。9.标示节点标示节点n为不行解节点。为不行解节点。10.用不行解标示过程对用不行解标示过程对n的先辈节点中的不行解节点进行标示。假如初始
50、节点的先辈节点中的不行解节点进行标示。假如初始节点S0也也被标示为不行解节点，则搜寻失败，退出；假如不能确定被标示为不行解节点，则搜寻失败，退出；假如不能确定S0为不行解节点，则从为不行解节点，则从OPEN表中删去具有不行解先辈的节点。表中删去具有不行解先辈的节点。11.转第转第2步。步。与/或树的广度和深度优先搜寻举例1t2t1t4t3A54B32A,B为不行解的端节点为不行解的端节点t1,t2,t3,t4为终止节点为终止节点6.3.2 博弈树的启发式搜寻博弈树的启发式搜寻1.博弈树的基本概念博弈树的基本概念博弈：诸如下棋、打牌、斗争等一类竞争性博弈：诸如下棋、打牌、斗争等一类竞争性智能活动