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