《7 人工智能与专家系统(GIS).ppt》由会员分享，可在线阅读，更多相关《7 人工智能与专家系统(GIS).ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 问题求解策略问题求解策略5.1 5.1 搜索基本原理搜索基本原理5.2 5.2 图搜索策略图搜索策略5.3 5.3 盲目搜索盲目搜索5.4 5.4 启发式搜索启发式搜索1搜索与问题求解l问题求解过程是搜索答案问题求解过程是搜索答案(目标目标)的过程的过程/所以所以问题求解技术也叫搜索技术问题求解技术也叫搜索技术通过对状态空间通过对状态空间的搜索而求解问题的技术的搜索而求解问题的技术问题求解智能体是一种基于目标的智能体在寻找到达目标的过程中，当智能体面对多个未知的选项时，首先检验各个不同的导致已知评价的状态的可能行动序列，然后选择最佳序列这个过程就是搜索2问题与问题的解l问题可以形
2、式化地定义为4个组成部分智能体的初始状态(即搜索的开始)后继函数智能体采取的可能行动的描述，通常为/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列目标测试检查给定的状态是不是目标路径耗散函数每条路径都有一个数值化的耗散值，反映了性能度量/求解问题的代价3问题的解l问题的解就是初始状态到目标状态的路径解的优劣由路径耗散函数量度(代价)最优解就是路径耗散函数值最小的路径l上述解题过程把解决一个问题的过程描述出来，称之为解题知识的过程性表示过程性知识与陈述性知识相对l搜索过程解题的特点没有直接的方法(公式)可以求解，而是一步一步的探索4状态空间
3、状态空间l数数据据基基：代代表表了了所所要要解解决决的的问问题题，有有初初始始状状态态，可能有目标状态也可能没有可能有目标状态也可能没有l状状态态空空间间：在在解解题题过过程程中中的的每每一一时时刻刻，数数据据基基都都处处于于一一定定的的状状态态，数数据据基基所所有有可可能能状状态态的的集集合称为状态空间合称为状态空间l有有向向图图：若若把把每每个个状状态态看看成成一一个个节节点点，则则整整个个状状态态空空间间是是一一个个有有向向图图/该该图图不不一一定定全全连连通通，即从某些状态不一定能到达另外一些状态即从某些状态不一定能到达另外一些状态5问题的可解性l可解的：在每个连通部分，每个弧代表一个
4、运算符，将状态改变/如果从代表初始状态的节点出发，有一条路径通向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的l搜索空间：在解题过程中达到过的所有状态的集合，称为搜索空间不同于状态空间，搜索空间只是其中一部分状态空间和搜索空间都属于过程性知识表示6问题实例l玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界l现实问题旅行商问题超大规模集成电路的布局自动装配排序/蛋白质设计互联网搜索7八数码游戏l八数码游戏：八数码游戏：1-8数字数字(棋子棋子)/9个方格个方格(棋盘格棋盘格)/1个空格个空格l可用如下形式的规则来表示数字通过空格进行移动：可用如下形式的规则来表示数字通过空
5、格进行移动：l共共24条规则条规则=4角角*2+4边边*3+1中间中间*4l搜索顺序举例：搜索顺序举例：(1)优先移动行数小的棋子优先移动行数小的棋子(数字数字)(2)同一行中优先移动列数大的棋子同一行中优先移动列数大的棋子l约束规则：不使离开既定位置的数字数增加约束规则：不使离开既定位置的数字数增加8八数码游戏的搜索树既定位置=终态9八数码问题形式化l初始状态初始状态向量规定向量中各分量对应的位置，各位置上的初始数字l后继函数移动规则按照某条规则移动数字，将得到的新向量l目标测试新向量是否是目标状态(也是向量形式)l路径耗散函数每次移动代价为1105.1 搜索基本原理 问题求解的基本方法有：
6、搜索法、归约问题求解的基本方法有：搜索法、归约法、归结法、推理法和产生式等。法、归结法、推理法和产生式等。搜索技术是人工智能的核心技术之一。搜索技术是人工智能的核心技术之一。对于无成熟方法可用的问题求解，对于无成熟方法可用的问题求解，只能只能利用已有的知识利用已有的知识一步步地摸索求解，这种一步步地摸索求解，这种问题求解过程就是搜索。问题求解过程就是搜索。11 搜索过程是否一定能找到解；搜索过程是否一定能找到解；搜索过程是否终止运行或是否会陷入死循环；搜索过程是否终止运行或是否会陷入死循环；当搜索过程找到一个解时，是否为最佳解；当搜索过程找到一个解时，是否为最佳解；搜索过程的时间与空间复杂性如
7、何。搜索过程的时间与空间复杂性如何。搜索的基本问题搜索的基本问题12 搜索的主要过程搜索的主要过程（1）从初始或目的状态出发，并将它作为当前状态；）从初始或目的状态出发，并将它作为当前状态；（2）扫描操作算子集，运用操作算子得到新的状态，）扫描操作算子集，运用操作算子得到新的状态，并建立指向其父节点的指针；并建立指向其父节点的指针；（3）检查新状态是否满足结束状态，如果满足，则得）检查新状态是否满足结束状态，如果满足，则得到解，给出解答路径；否则将新状态作为当前状态，到解，给出解答路径；否则将新状态作为当前状态，返回第（返回第（2）步再进行搜索。）步再进行搜索。13 搜索方向搜索方向 从初始状
8、态出发的正向搜索，也称为数据驱动；从初始状态出发的正向搜索，也称为数据驱动；从目的状态出发的逆向搜索，也称为目的驱动；从目的状态出发的逆向搜索，也称为目的驱动；从初始状态出发作正向搜索，同时又从目的状态出从初始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合发作逆向搜索，直到两条路径在中间的某处汇合为止，这称为双向搜索；为止，这称为双向搜索；在不具有对特定问题的任何有关信息的条件下，按在不具有对特定问题的任何有关信息的条件下，按固定的步骤进行搜索，这是盲目搜索。固定的步骤进行搜索，这是盲目搜索。14l有限搜索还是无限搜索？有限搜索还是无限搜索？若搜索空间有限，则
9、任何一种穷举算法均能完若搜索空间有限，则任何一种穷举算法均能完成任务。成任务。l搜索空间是静态的还是动态生成的？搜索空间是静态的还是动态生成的？在人工智能中，搜索的对象在人工智能中，搜索的对象(常称状态常称状态)是在搜是在搜索过程中逐步生成的，需将搜索对象的生成和索过程中逐步生成的，需将搜索对象的生成和评估的代价计算在内。对于一般搜索，搜索空评估的代价计算在内。对于一般搜索，搜索空间基本是静态的，或表或数组或数据库。间基本是静态的，或表或数组或数据库。l已知目标还是未知目标？已知目标还是未知目标？l只要目标还是也要路径？路径是解题过程中应只要目标还是也要路径？路径是解题过程中应用的操作序列。用
10、的操作序列。研究和选用搜索算法的原则研究和选用搜索算法的原则15l状态空间搜索还是问题空间搜索？状态空间搜索还是问题空间搜索？在解题过程中的每一时刻，所要解决的问题均在解题过程中的每一时刻，所要解决的问题均处于一定的状态，搜索过程只是将一个状态变处于一定的状态，搜索过程只是将一个状态变成另一个状态成另一个状态(如，一盘棋局变成另一盘棋局如，一盘棋局变成另一盘棋局)，则称为状态空间搜索。，则称为状态空间搜索。若搜索的对象是问题，搜索的原则是把一个复若搜索的对象是问题，搜索的原则是把一个复杂的问题化为一组比较简单的子问题杂的问题化为一组比较简单的子问题(如把一个如把一个复杂的下棋策略分为几个子策略
11、复杂的下棋策略分为几个子策略)，则称为问题，则称为问题空间搜索。空间搜索。注：问题空间搜索常常比状态空间搜索有效，但注：问题空间搜索常常比状态空间搜索有效，但算法要复杂些。算法要复杂些。研究和选用搜索算法的原则研究和选用搜索算法的原则16l有约束还是无约束？有约束还是无约束？问题空间搜索时，若子问题间互相无约束关系，问题空间搜索时，若子问题间互相无约束关系，则比较简单，否则需要回溯，即放弃已解决的子则比较简单，否则需要回溯，即放弃已解决的子问题，走回头路，寻找新的解法。问题，走回头路，寻找新的解法。l数据驱动还是目标驱动？数据驱动还是目标驱动？数据驱动是向前搜索，目标驱动是向后搜索。数据驱动是
12、向前搜索，目标驱动是向后搜索。l单向搜索还是双向搜索？单向搜索还是双向搜索？l盲目搜索还是启发式搜索？盲目搜索还是启发式搜索？按照预定的控制策略实行搜索，在搜索过程中按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。搜索，反之，称为启发式搜索。研究和选用搜索算法的原则研究和选用搜索算法的原则17一般搜索方法分类一般搜索方法分类盲盲目目搜搜索索是是按按预预定定的的控控制制策策略略进进行行，在在搜搜索索的的过过程程中中所所获获得得的的信信息息不不用用来来改改进进控控制制策略的一种搜索。策略的一种搜
13、索。启启发发式式搜搜索索是是在在搜搜索索中中加加入入了了与与问问题题有有关关的的启启发发式式信信息息，用用来来指指导导搜搜索索朝朝着着最最有有希希望望的的方方向向前前进进，加加速速问问题题的的求求解解过过程程，并并找到最优解。找到最优解。18一般搜索方法分类一般搜索方法分类 盲目搜索盲目搜索 1)无变量的盲目搜索无变量的盲目搜索l 状态空间、问题空间的盲目搜索状态空间、问题空间的盲目搜索l 深度优先、广度优先、代价优先、混合深度优先、广度优先、代价优先、混合l 向前、向后、双向向前、向后、双向 2)有变量的盲目搜索有变量的盲目搜索 通代通代 启发式搜索启发式搜索 195.2 5.2 图搜索策略
14、图搜索策略l图搜索策略可以看成是一种在图中寻找图搜索策略可以看成是一种在图中寻找路径的方法。初始结点和目标结点分别路径的方法。初始结点和目标结点分别代表初始数据库和满足终止条件的数据代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一个数库。求得把一个数据库变换为另一个数据库规则序列问题就等于求得图中的一据库规则序列问题就等于求得图中的一条路径问题。条路径问题。20图图搜搜索索过过程程框框图图 21l一般图搜索算法中，提高搜索效率的关键一般图搜索算法中，提高搜索效率的关键在于优化在于优化OPEN表中节点的排序方式，若表中节点的排序方式，若每次排在表首的节点都在最终搜索到的解每次排在
15、表首的节点都在最终搜索到的解答路径上，则算法不会扩展任何多余的节答路径上，则算法不会扩展任何多余的节点就可快速结束搜索。所以排序方式成为点就可快速结束搜索。所以排序方式成为研究搜索算法的焦点，并由此形成了多种研究搜索算法的焦点，并由此形成了多种搜索策略。搜索策略。22l盲目搜索又叫做无信息搜索，一般只适用于求解比盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。较简单的问题。l宽度优先搜索和深度优先搜索，均属于盲目搜索方宽度优先搜索和深度优先搜索，均属于盲目搜索方法。法。l其共同缺点是节点排序的盲目性，由于不采用领域其共同缺点是节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会
16、搜索了大量无关的状专门知识去指导排序，往往会搜索了大量无关的状态节点后才碰到解答，所以称为盲目搜索。态节点后才碰到解答，所以称为盲目搜索。5.3 5.3 盲目搜索盲目搜索23 宽度优先搜索宽度优先搜索 l宽度优先搜索（宽度优先搜索（breadth-first search）的）的定义：如果搜索是以接近起始节点的程度定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽依次扩展节点的，那么这种搜索就叫做宽度优先搜索（度优先搜索（breadth-first search）。）。l特点：这种搜索是逐层进行的；在对下一特点：这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须
17、搜索完层的任一节点进行搜索之前，必须搜索完本层的所有节点。本层的所有节点。24宽度优先搜索示意图宽度优先搜索示意图 25宽度优先搜索算法宽度优先搜索算法（1）把起始节点放到把起始节点放到OPEN表中（如果该起始节点为一表中（如果该起始节点为一目标节点，则求得一个解答）。目标节点，则求得一个解答）。（2）如果如果OPEN是个空表，则没有解，失败退出；否则是个空表，则没有解，失败退出；否则继续。继续。（3）把第一个节点（节点）把第一个节点（节点 n）从）从OPEN表移出，并把它表移出，并把它放入放入CLOSED扩展节点表中。扩展节点表中。（4）扩展节点）扩展节点n。若没有后继节点，则转向上述第（。
18、若没有后继节点，则转向上述第（2）步。步。（5）把把n 的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供表的末端，并提供从这些后继节点回到从这些后继节点回到n的指针。的指针。（6）如果如果n 的任一个后继节点是个目标节点，则找到一的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（个解答，成功退出；否则转向第（2）步。）步。26宽宽度度优优先先算算法法框框图图27宽度优先搜索方法分析宽度优先搜索方法分析 l宽度优先搜索方法能够保证在搜索树中找到一条宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所通向目标节点的最短途径；这棵搜索树提
19、供了所有存在的路径（如果没有路径存在，那么对有限有存在的路径（如果没有路径存在，那么对有限图来说，我们图来说，我们 就说该法就说该法 失败失败 退出；对于退出；对于 无限无限图来说，则永远不会终止）。图来说，则永远不会终止）。l例：把宽度优先搜索应用于八数码难题时所生成例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如图的搜索树，这个问题就是要把初始棋局变为如图所示的目标棋局问题。所示的目标棋局问题。28八数码难题的宽度八数码难题的宽度优先搜索树优先搜索树 29宽度优先搜索宽度优先搜索l搜索树上的所有节点都标记它们所对应的搜索树上的所有节点都标记它们所对应的状态
20、描述，每个节点旁边的数字表示节点状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格）。扩展的顺序（按顺时针方向移动空格）。图中最后一个节点是目标节点。图中最后一个节点是目标节点。30 深度优先搜索深度优先搜索(depth-first search)31 深度优先搜索深度优先搜索l分析深度优先搜索示意图可看出，在深度优先搜分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的（即最深的）节索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。点。深度相等的节点可以任意排列。l定义节点的深度如下：定义节点的深度如下：（1）起始节点（即根节点）的
21、深度为起始节点（即根节点）的深度为0。（2）任何其它节点的深度等于其父辈节点深度加任何其它节点的深度等于其父辈节点深度加上上1。32l首先，扩展最深的节点的结果使得搜索沿着状态首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后的路径不同之处仅仅在于改变最后n步，而且保步，而且保持持n尽可能小。尽可能小。33深度界限深度界限l
22、对于许多问题，其状态空间搜索树的深度可能为对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的列的已知深度上限还要深。为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展下去），路径（防止搜索过程沿着无益的路径扩展下去），往往给出一个节点扩展的最大深度往往给出一个节点扩展的最大深度深度界限。深度界限。任何节点如果达到了深度界限，那么都将把它们任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使作为没有后继节点处理。值得说明的是，即使 应用了深度界限
23、的应用了深度界限的 规定，所求得的解答路径并规定，所求得的解答路径并不一定就是最短的路径。不一定就是最短的路径。34含有深度界限的深度优先搜索算法含有深度界限的深度优先搜索算法（1）把起始节点放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。（2）如果OPEN为一空表，则失败退出。（3）把第一个节点（节点n）从OPEN表移到CLOSED表。（4）如果节点n的深度等于最大深度，则转向（2）。（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）。（6）如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向（2）。35有有界界深深度
24、度优优先先搜搜索索算算法法图图 36按深度优先搜索生成的八数码按深度优先搜索生成的八数码难题搜索树，深度界限为难题搜索树，深度界限为5。37 状状态态空空间间表表示示法法是是用用“状状态态”和和“算算符符”来来表表示问题的一种方法。示问题的一种方法。状状态态：状状态态是是描描述述问问题题求求解解过过程程中中任任一一时时刻刻状况的数据结构。状况的数据结构。算算符符：引引起起状状态态的的某某些些分分量量变变化化，从从而而使使问问题从一个状态变为另一个状态的操作称为算符。题从一个状态变为另一个状态的操作称为算符。状状态态空空间间：问问题题的的全全部部状状态态和和一一切切算算符符所所构构成的集合成为状
25、态空间。成的集合成为状态空间。状态空间表示法：状态空间表示法：38例如例如 二阶梵塔问题二阶梵塔问题解：设立柱 1、2和3以及两个圆盘A和B。用Sk=(Sk0,Sk1)表示问题状态，Sk0表示圆盘A所在的立柱，Sk1表示圆盘B所在的立柱，全部可能状态共有九种：S0=(1，1)，S1=(1，2)，S2=(1，3)S3=(2，1)，S4=(2，2)，S5=(2，3)S6=(3，1)，S7=(3，2)，S8=(3，3)问题的初始状态集合是S=S0，目标状态集合是G=S4，S8。39S S0 0=（1 1，1 1）S S1 1=（1 1，2 2）S S2 2=（1 1，3 3）S S3 3=（2 2，
26、1 1）S S4 4=（2 2，2 2）S S5 5=（2 2，3 3）S S6 6=（3 3，1 1）S S7 7=（3 3，2 2）S S8 8=（3 3，3 3）二阶梵塔问题状态表示二阶梵塔问题状态表示二阶梵塔问题状态表示二阶梵塔问题状态表示40 与/或树表示法：对于一个复杂的问题，可以通过“分解”和“等价变换”两种手段相结合使用，得到一个图，这个图就是与/或图。等价变换：是一种同构或同态的变换。本原问题：不能再分解或变换，而且直接可以求解的子问题，称为本原问题。终端节点与终止节点：在一棵与/或树中，没有子节点的节点称为终端节点；本原问题所对应的节点称为终止节点。可解节点：在与/或树中，
27、满足下列条件之一者就称为可解节点：它是一个终止节点它是一个“或”节点，且其子节点中至少有一个是可解节点它是一个“与”节点，且其子节点全部是可解节点 不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。解树：由可解节点构成，且由这些可解节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。41 状态空间搜索状态空间搜索 状态空间搜索的一般过程状态空间搜索的一般过程 OPEN表表和和CLOSED表表：OPENOPEN表表是是用用于于存存放放刚刚生生成成的的节节点点；CLOSED表表用用于存放将要扩展的节点。于存放将要扩展的节点。搜索的一般过程搜索的一般过程 广广度度优优先先
28、搜搜索索：从从初初始始节节点点S0开开始始，逐逐层层地地对对节节点点进进行行扩扩展展并并考考查查它它是是否否为为目目标标节节点点。在在第第n层层的的节节点点没没有有全全部部扩扩展展并并考考查查之之前前，不不对对第第 n+1层层节节点点进进行行扩扩展展。OPEN表表中中的的节节点点总总是是按按进进入入的的先先后后顺顺序序排排列列，先先进进入入的的节节点点排排在在前前面面，后后进入的节点在后。进入的节点在后。深深度度优优先先搜搜索索：从从初初始始节节点点S0开开始始，在在其其子子节节点点中中选选择择一一个个子子节节点点进进行行考考查查，若若不不是是目目标标节节点点，则则再再在在该该子子节节点点中中
29、选选择择一一个个子子节节点点进进行行考考查查，一一直直如如此此向向下下搜搜索索。当当到到达达某某个个子子节节点点，且且该该子子节节点点既既不不是是目目标标节节点点又又不不能能继继续续扩扩展展时时，才才选选择择其兄弟节点进行考察。其兄弟节点进行考察。与与广广度度优优先先搜搜索索不不同同，深深度度优优先先搜搜索索是是把把节节点点n的的子子节节点点放放入入OPEN表表的的首部。首部。42 有有界界的的深深度度优优先先：对对深深度度优优先先搜搜索索引引入入搜搜索索深深度度的的界界限限，当当搜搜索索深深度度达达到到了了深深度度界界限限，而而尚尚未未出出现现目目标标节节点点，就换一个分支进行搜索。就换一个
30、分支进行搜索。代代价价树树的的广广度度优优先先搜搜索索：与与/或或树树中中，边边上上有有代代价价（或或费用）的树称为代价树。费用）的树称为代价树。代代价价树树的的广广度度优优先先搜搜索索的的基基本本思思想想是是每每次次从从OPEN表表中中选选择择节节点点往往CLOSED表表中中传传送送时时，总总是是选选择择其其代代价价最最小小的的节点。节点。代代价价树树的的深深度度优优先先搜搜索索：基基本本思思想想是是从从刚刚扩扩展展的的子子节节点中选择一个代价最小的节点送入点中选择一个代价最小的节点送入CLOSED表进行考查。表进行考查。43 启发式搜索：启发式搜索是利用问题本身的某些启发信息，以制导搜索朝
31、着最有希望的方向前进。估价函数：用于估价节点重要性的函数称为估价函数。它的一般形式为 局部择优搜索：当一个节点被扩展后，按f(x)对每个子节点计算估价值，并选择最小者作为下一个要考查的节点。由于它每次都只是在子节点的范围中选择要考查的子节点，所以称为局部择优搜索。全局择优搜索：每次都是从OPEN表的全体节点中选择一个估价值最小的节点进行扩展。44 把要求解的问题的具体领域的知识加进搜索把要求解的问题的具体领域的知识加进搜索算法中，控制搜索过程，以提高算法效率的搜索算法中，控制搜索过程，以提高算法效率的搜索方法，称为启发式搜索。方法，称为启发式搜索。注：注：1）这里搜索的对象）这里搜索的对象(常
32、称状态常称状态)往往是边往往是边搜索边生成，因此在考虑这种搜索的复杂性时，搜索边生成，因此在考虑这种搜索的复杂性时，必须将搜索对象的生成和评估的代价计算在内。必须将搜索对象的生成和评估的代价计算在内。5.4 启发式搜索启发式搜索45注：注：2)根据启发性信息根据启发性信息(特定领域的知识信息特定领域的知识信息)，在生成搜索树时可考虑种种可能的选择：在生成搜索树时可考虑种种可能的选择：a)下一步展开哪个节点？下一步展开哪个节点？b)是部分展开还是全部展开？是部分展开还是全部展开？c)使用哪个规则使用哪个规则(算子算子)？d)怎样决定舍弃还是保留新生成的节点？怎样决定舍弃还是保留新生成的节点？e)
33、怎样决定舍弃还是保留一棵子树？怎样决定舍弃还是保留一棵子树？f)怎样决定停止或继续搜索？怎样决定停止或继续搜索？g)如何定义启发函数如何定义启发函数(估值函数估值函数)？h)如何决定搜索方向？如何决定搜索方向？启发式搜索启发式搜索465.4 启发式搜索 启发性信息启发性信息按按其其用用途途划划分分,启启发发性性信信息息可可分分为为以以下下三三类类：(1)(1)用用于于扩扩展展节节点点的的选选择择,即即用用于于决决定定应应先先扩扩展哪一个节点展哪一个节点,以免盲目扩展。以免盲目扩展。(2)(2)用用于于生生成成节节点点的的选选择择,即即用用于于决决定定应应生生成成哪些后续节点哪些后续节点,以免盲
34、目地生成过多无用节点。以免盲目地生成过多无用节点。(3)(3)用用于于删删除除节节点点的的选选择择,即即用用于于决决定定应应删删除除哪些无用节点哪些无用节点,以免造成进一步的时以免造成进一步的时空浪费。空浪费。47启发信息与估价函数启发信息与估价函数l启发信息按运用的方式可分为：启发信息按运用的方式可分为：（1）陈述性启发信息）陈述性启发信息（2）过程性启发信息）过程性启发信息（3）控制性启发信息）控制性启发信息48估价函数估价函数l一个比较灵活的方法是应用某些准则来重新排一个比较灵活的方法是应用某些准则来重新排列每一步列每一步OPEN表中所有节点的顺序。然后，搜表中所有节点的顺序。然后，搜索
35、就可能沿某个被认为是最有希望的边缘区段向索就可能沿某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点外扩展。应用这种排序过程，需要某些估算节点“希望希望”的量度。用来估算节点希望程度的量度，的量度。用来估算节点希望程度的量度，叫做估价函数（叫做估价函数（evaluation function）。）。491、基本思想、基本思想 a)对于每个在搜索过程中遇到的新状态，计算对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。将从哪一个状态开始继续前进。b)一般以估计值小者作为较优的状
36、态，以此实一般以估计值小者作为较优的状态，以此实现最佳优先搜索。现最佳优先搜索。c)计算状态估计值的函数是确定的，但每个状计算状态估计值的函数是确定的，但每个状态的估计值的大小与初始状态到该路径有关。态的估计值的大小与初始状态到该路径有关。有序搜索算法有序搜索算法502、算法、算法 1)建立一个空的建立一个空的状态状态序列序列SS 2)建立一个空的建立一个空的状态状态库库SB 3)定义一个估值函数定义一个估值函数f 4)若初始状态为若初始状态为S0,则定义初始则定义初始状态状态S0(0,f(0)为当为当前新前新状态状态 5)将当前新将当前新状态状态按估计值从小到大的顺序插入到按估计值从小到大的
37、顺序插入到SS中，若新状态为目标状态，则将相应中，若新状态为目标状态，则将相应状态状态插入到插入到具有相同估计值的具有相同估计值的状态状态的最前面；否则将相应的最前面；否则将相应状态状态插入到具有相同估计值的插入到具有相同估计值的状态状态的最后面的最后面有序搜索算法有序搜索算法51 6)若在若在SS或或SB中原有一个中原有一个状态状态与当前新与当前新状态状态共一个状态，则删去原有共一个状态，则删去原有状态状态 7)若新若新状态状态在在SS的最前面，则转的最前面，则转11)8)若某种状态极限已达到，则搜索失败，算法若某种状态极限已达到，则搜索失败，算法运行结束，无解运行结束，无解.有序搜索算法有
38、序搜索算法529)若任何规则均不能应用于若任何规则均不能应用于状态状态序列序列SS中的第一中的第一个状态，或者虽能应用，但不能产生合适的新个状态，或者虽能应用，但不能产生合适的新状状态态(在在SS或或SB中均没有者，称为新中均没有者，称为新)，或虽能产，或虽能产生合适的新生合适的新状态状态S(path2,f(path2),但不是改进型但不是改进型的的(若若SS和和SB中已有中已有状态状态S(path1,f(path1),它与它与新新状态状态共一个状态共一个状态S，且，且f(path2)f(path1),则称则称新状态不是改进型的新状态不是改进型的)，则将此第一个状态从，则将此第一个状态从SS中
39、除去，送入中除去，送入SB中，否则转中，否则转12)5310)若若SS成为空序列，则搜索失败，算法运行结束，成为空序列，则搜索失败，算法运行结束，无解无解 11)若若SS中第一个状态已是目标状态，则搜索成中第一个状态已是目标状态，则搜索成功，算法运行结束功，算法运行结束(若该若该状态状态形如形如S(path,f(path)，则解就是则解就是(path)；否则转否则转9)12)取一个可应用于取一个可应用于SS的第一个的第一个状态状态S(path,f(path)，并产生改进型的合适新并产生改进型的合适新状态状态的规的规则则Rn，产生新产生新状态状态T(path,n,f(path)，定义它为当定义它
40、为当前新前新状态状态，转，转5)#算法完算法完541)状态状态是带路径和估计值的状态，而状态只是一个状态。是带路径和估计值的状态，而状态只是一个状态。2)对当前生成的新状态是否是目标状态的判断需要两次对当前生成的新状态是否是目标状态的判断需要两次3)这里每次只生成一个后代这里每次只生成一个后代4)给定估计值函数给定估计值函数f的意义，则有序搜索就可归结为已知的意义，则有序搜索就可归结为已知的搜索，如令的搜索，如令f为状态节点的深度，则有序搜索就成为广度为状态节点的深度，则有序搜索就成为广度优先搜索。优先搜索。5)有序搜索算法不一定找到解，即使有解有序搜索算法不一定找到解，即使有解6)有序搜索算
41、法的特点是使用启发式信息有序搜索算法的特点是使用启发式信息(表现在估计值函表现在估计值函数数f上上)，可是启发式信息也会骗人，会引人误入歧途，可是启发式信息也会骗人，会引人误入歧途7)有序搜索即使能找到解，也未必一定是最优的。有序搜索即使能找到解，也未必一定是最优的。备注备注55 1)用多个估计值函数来用多个估计值函数来“层层设卡层层设卡”2)对估计值函数的形式加以限制，以保证它对估计值函数的形式加以限制，以保证它一定能找到解，甚至一定能找到最优解。一定能找到解，甚至一定能找到最优解。有序搜索算法改进有序搜索算法改进56 令令S为初始节点，为初始节点，ti为一组目标节点，为一组目标节点，n,n
42、i,nj为任意节点为任意节点 k*(ni,nj)为从为从ni到到nj的最小代价的最小代价 g*(n)=k*(S,n)为从初始节点为从初始节点S到节点到节点n的最小代价的最小代价 h*(n)=min k*(n,ti)为从节点为从节点n到一个目标节点到一个目标节点ti的的最小代价最小代价 f*(n)=g*(n)+h*(n)为从初始节点出发，经过节点为从初始节点出发，经过节点n，到达一个目标节点的最小代价到达一个目标节点的最小代价 ti估计值函数的改进估计值函数的改进57估计值函数的改进估计值函数的改进 g(n)为对为对g*(n)的估计，的估计，g(n)0 h(n)为对为对h*(n)的估计，的估计，h(n)0 f(n)=g(n)+h(n)为每个节点为每个节点n处的估计值函数处的估计值函数5.4 启发式搜索启发式搜索58Thanks.59