第4章搜索策略.pptx

《第4章搜索策略.pptx》由会员分享，可在线阅读，更多相关《第4章搜索策略.pptx（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2021/5/17,#,人工智能 原理篇,搜 索 策 略,第四章,本 章 导 读,现实世界中多数问题都是非结构化的，一般不能用直接求解的方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。因此，常常使用基于搜索策略的方法来求解问题。搜索策略是人工智能的基本求解策略之一，已在人工智能各领域得到了广泛应用。,本章主要介绍基于状态空间表示法的搜索策略，包括盲目搜索策略和启发式搜索策略。,学习目标,熟悉搜索的基本内容。,理解搜索策略的思想。,掌握宽度优先搜索、深度优先搜索和等代价搜索等盲目搜索策略。,掌握,A,搜索

2、和,A*,搜索等启发式搜索策略。,目 录,4,搜 索 概 述,盲 目 搜 索 策 略,启 发 式 搜 索 策 略,01,02,03,搜 索 概 述,01,搜 索 的 概 念,4.1.1,搜索,就是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条代价较小的推理路线，使问题得到解决的过程。,搜索是人工智能中的一个核心技术，是推理不可分割的一部分，它直接关系到智能系统的性能和运行效率。在搜索问题中，主要的工作是找到正确的搜索策略。搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。,在人工智能中，通过运用搜索策略解决问题的基本思想是：首先把问

3、题的初始状态（即起始节点）作为当前状态，选择适用的操作符对其进行操作，生成一组子状态（即后继节点），然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若未出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及操作符为止。,在运用搜索策略求解问题的过程中，涉及的数据结构除了状态空间图之外，还需要两个辅助的数据结构，即存放已访问但未扩展节点的,OPEN,表，以及存放已扩展节点的,CLOSED,表。状态空间图的搜索过程如左图所示。,搜索过程,4.1.2,（,1,）建立一个只含起始节点,的搜索图，并将,放入,OPEN,

4、表中。,（,2,）建立一个,CLOSED,表，并将其初始化为空表。,（,3,）判断,OPEN,表是否为空表，若为空表，则失败退出；否则继续（,4,）。,（,4,）选择,OPEN,表上的第一个节点（称为节点,n,），将其从,OPEN,表移出，并放入,CLOSED,表中。,（,5,）判断节点,n,是否为目标节点。若,n,为目标节点，则有解并成功退出，此解为沿着指针从节点,n,到,的这条路径,指针将在第（,7,）步中设置,。否则，执行（,6,）。,（,6,）扩展节点,n,，生成后继节点集合,M,，并将集合,M,中的成员作为,n,的后继节点添加入搜索图中。,（,7,）针对,M,中后继节点的不同情况，分

5、别做如下处理。,对那些未曾在搜索图中出现过的（既未曾在,OPEN,表中，也未在,CLOSED,表中出现过）,M,成员，设置其父节点指针指向,n,，并加入,OPEN,表中。,对那些原来已在搜索图中出现过，但还没有扩展的（已经在,OPEN,表或,CLOSED,表中出现过）,M,成员，确定是否需要将其原来的父节点更改为,n,。,对那些先前已在搜索图中出现过，并已经扩展了的（已在,CLOSED,表中）,M,成员，确定是否需要修改其后继节点指向父节点的指针。若修改了其父节点，则将该节点从,CLOSED,表中移出，重新加入,OPEN,表中。,（,8,）按某一方式或按某个估价值，重排,OPEN,表。继续执行

6、步骤（,3,）。,知 识 库,上述搜索过程可生成一个搜索图。不同的搜索策略可得到不同的搜索树。其中，搜索树是搜索图的一个子集。,在搜索树中，除初始节点,外，任意一个节点都含有唯一一个指向其父节点的指针。从目标节点开始，将指针指向的状态回串起来，即找到一条求解路径。,添 砖 加 瓦,在搜索过程中需要解决的基本问题有：,（,1,）搜索过程是否一定能找到一个解。,（,2,）当搜索过程找到一个解时，找到的是否是最佳解。,（,3,）搜索过程的时间与空间复杂性如何。,（,4,）搜索过程是否能终止运行或是否会陷入一个死循环。,根据搜索过程中是否运用与问题有关的信息，可以将搜索策略分为盲目搜索策略和启发式搜索

7、策略。,在搜索过程中对,OPEN,表的节点排序，主要目的是希望从未扩展节点中选出一个最具有希望的节点作为下一个扩展节点使用。若此时的排序是任意的或者是盲目的，则为盲目搜索；若排序是以各种启发式思想或其他准则为依据的，则为启发式搜索。,搜索策略,4.1.3,盲 目 搜 索 策 略,02,盲目搜索策略,又称无信息搜索策略，也就是说，在搜索过程中，只按照预先规定的搜索策略进行搜索，而没有任何中间信息来改变这些策略。常用的盲目搜索策略有宽度优先搜索、深度优先搜索和等代价搜索等。,宽度优先搜索又称广度优先搜索,，其基本思想是从起始节点开始，逐层对节点进行依次扩展（或搜索），同时考察它是否为目标节点。,例

8、如，如左图所示的搜索树，其搜索顺序应为,4.2.1,宽度优先搜索,宽度优先搜索,宽度优先搜索的搜索过程可用如左图所示的算法描述。,宽度优先搜索算法,【,例,4-1】,猫捉老鼠问题，猫位于,A,处，它发现,K,处有一只老鼠（见左图），请用宽度优先搜索算法帮猫寻找捕捉路线。,猫和老鼠的位置表示,【,解,】,使用宽度优先搜索算法解决猫捉老鼠问题的步骤如下。,（,1,）猫所在的位置,A,是起始节点，将,A,放入,OPEN,表中。,（,2,）判断该起始节点,A,是否为一目标节点，若是，则求得一个解并成功退出；否则继续。节点,A,不是老鼠所在的位置，所以不是目标节点。,（,3,）判断,OPEN,表是否为空

9、表，若是空表，则没有解，失败退出；否则继续。,OPEN,表中有节点,A,，非空，继续执行。,（,4,）把,OPEN,表中的第一个节点（记为节点,n,）移出，并放入,CLOSED,表中。将节点,A,从,OPEN,表中移出，并放入,CLOSED,表中。,（,5,）判断节点,n,是否有后继节点，若有，则继续；否则，转向（,3,）。节点,A,有后继节点，继续执行。,（,6,）扩展节点,n,，把节点,n,的所有后继节点放入,OPEN,表的末端，并提供从这些后继节点回到父节点,n,的指针。即扩展节点,A,，其后继节点有,B,和,C,，将它们放入,OPEN,表的末端，并提供回到父节点,A,的指针。,（,7,

10、）判断刚产生的这些后继节点中是否存在一个目标节点，若存在，则找到一个解，成功退出。解可从目标节点到起始节点的返回指针中得到。否则转向（,3,）。后继节点,B,和,C,都不是目标节点，转向（,3,）。,循环执行上述操作，其,OPEN,表和,CLOSED,表的状态变化如表所示。,OPEN,表和,CLOSED,表的状态变化,循环次数,OPEN,表,CLOSED,表,0,（初始化）,A,空,1,B、C,A,2,C、D、E,A、B,3,D、E、F、G,A、B、C,4,E、F、G、H,A、B、C、D,5,F、G、H,A、B、C、D、E,6,G、H、I、J,A、B、C、D、E、F,7,H、I、J、K,A、B

11、、C、D、E、F、G,从表可以看出，在第,7,次循环中，步骤（,7,）判断,G,产生的后继节点,K,是目标节点。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为。,该搜索结束后得到的搜索树如左图所示。,宽度优先搜索树,深度优先搜索的基本思想是从起始节点开始，在其子节点中选择一个节点进行考察，如果不是目标节点，则在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索，如果发现不能到达目标节点，则返回到上一个节点，然后选择该节点的另一个子节点往下搜索，如此反复，直到搜索到目标节点或搜索完全部节点为止。,例如，如图所示的搜索树，其搜索顺序应为,神经元,4.2.2,深度优先搜索,添 砖 加

12、 瓦,节点深度的定义如下。,（,1,）起始节点（即根节点）的深度为,0,。例如，图中节点,A,的深度为,0,。,（,2,）任何其他节点的深度等于其父节点深度加,1,。例如，图中节点,D,的深度是,2,，等于其父节点,B,的深度,1,加,1,。,深度相等的节点可以任意排列。例如，图中节点,B,和,C,的排列也可以是先,C,后,B,。,深度优先搜索,含有深度界限的深度优先搜索的搜索过程可用如左图所示的算法描述。,有界深度优先搜索算法,【,例,】,请用含有深度界限的深度优先搜索算法解决例,1,中的猫捉老鼠问题。,【,解,】,使用含有深度界限的深度优先搜索算法解决猫捉老鼠问题的步骤如下。,（,1,）猫

13、所在的位置,A,是起始节点，将,A,放入,OPEN,表中。,（,2,）判断该起始节点,A,是否为一目标节点，若是，则求得一个解并成功退出；否则继续。节点,A,不是老鼠所在的位置，所以不是目标节点。,（,3,）判断,OPEN,表是否为空表，若是空表，则没有解，失败退出；否则继续。,OPEN,表中有节点,A,，非空，继续执行。,（,4,）把,OPEN,表中的第一个节点（记为节点,n,）移出，并放入,CLOSED,表中。将节点,A,从,OPEN,表中移出，并放入,CLOSED,表中。,（,5,）判断节点,n,的深度是否等于深度界限，若等于，则转向（,3,）；否则继续。针对猫捉老鼠问题，将深度界限设为

14、,3,。第,1,次循环中节点,A,的深度为,0,，不等于深度界限。,（,6,）判断节点,n,是否有后继节点，若有，则继续；否则，转向（,3,）。节点,A,有后继节点，继续执行,（,7,）扩展节点,n,，把节点,n,的所有后继节点放入,OPEN,表的前端，并提供从这些后继节点回到父节点,n,的指针。扩展节点,A,，把,A,的后继节点,B,和,C,放入,OPEN,表的前端。,（,8,）判断刚产生的这些后继节点中是否存在一个目标节点，若存在，则找到一个解，成功退出。解可从目标节点到起始节点的返回指针中得到。否则转向（,3,）。后继节点,B,和,C,都不是目标节点，转向（,3,）。,循环执行上述操作，

15、第,1,次循环结束后，,OPEN,表的节点依次是,B,、,C,，然后进行第,2,次循环，扩展第一个节点,B,，其后继节点有,D,和,E,，将它们放入,OPEN,表的前端，并提供回到父节点,B,的指针。,可见，经过第,2,次循环后，,OPEN,表的节点依次为,D,、,E,、,C,。在整个搜索过程中，,OPEN,表和,CLOSED,表的状态变化如左表所示。,循环次数,OPEN,表,CLOSED,表,0,（初始化）,A,空,1,B、C,A,2,D、E、C,A、B,3,H、E、C,A、B、D,4,E、C,A、B、D、H,5,C,A、B、D、H、E,6,F、G,A、B、D、H、E、C,7,I、J、G,A

16、、B、D、H、E、C、F,8,J、G,A、B、D、H、E、C、F、I,9,G,A、B、D、H、E、C、F、I、J,10,K,A、B、D、H、E、C、F、I、J、G,OPEN,表和,CLOSED,表的状态变化,从表可以看出，在第,10,次循环中，步骤（,8,）判断节点,G,产生的后继节点,K,是目标节点。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为。,该搜索结束后得到的搜索树如图所示。,深度优先搜索树,知 识 库,深度优先搜索策略也是一个通用的与问题无关的方法，其性质有：,（,1,）一般不能保证找到路径最短的解。,（,2,）当深度界限设置不合理时，可能找不到解。,（,3,）在最坏情况

17、下，搜索空间等同于穷举。,在求解实际问题的过程中，搜索所做的每一步操作的代价并不一定相同，因此，由宽度优先搜索找到的最短路径并不等同于最优解。但是，通常人们希望找到具有某种特性的解，尤其是最小代价解。,要解决寻找最小代价的路径问题，可采用宽度优先搜索的推广策略，即等代价搜索。,在等代价搜索算法中，把从节点,n,到其后继节点,m,的连接弧线的代价记为,，把从起始节点,S0,到任一节点,n,的路径代价记为,。在搜索树上，假设,是从起始节点,S0,到节点,n,的最小代价路径上的代价，并且它是唯一的路径。,4.2.3,等代价搜索,等代价搜索以,的递增顺序扩展其节点，其搜索过程可用如左图所示的算法描述。

18、,等代价搜索算法,【,例,】,猫捉老鼠问题中，将弧线赋予意义，即两节点间弧的数值代表猫的体力消耗值，如图所示。,例如，猫从位置,A,到位置,B,所消耗的体力值为,3,，可用,表示。,猫和老鼠位置表示,【,解,】,使用等代价搜索算法求猫捉老鼠所消耗的体力值，其步骤如下。,（,1,）猫所在的位置,A,是起始节点，将,A,放入,OPEN,表中，令,。,（,2,）判断,OPEN,表是否为空表，若是空表，则没有解，失败退出；否则继续。,OPEN,表中有节点,A,，非空，继续执行。,（,3,）把,OPEN,表中具有最小,值的节点,n,从,OPEN,表移至,CLOSED,表中。第,1,次循环，,OPEN,表

19、中只有节点,A,，将节点,A,从,OPEN,表中移至,CLOSED,表中。,（,4,）判断节点,n,是否为一目标节点，若是，则求得一个解且猫消耗的体力值为,，成功退出；否则继续。第,1,次循环中，判断节点,A,不是老鼠所在的位置，所以不是目标节点。,（,5,）判断节点,n,是否有后继节点，若有，则继续；否则，转向（,2,）。节点,A,有后继节点，继续执行。,（,6,）扩展节点,n,，对其后继节点,m,，计算,，并把所有后继节点,m,放入,OPEN,表，同时提供回到父节点,n,的指针，最后转向（,2,）。,将节点,A,的后继节点,B,和,C,放入,OPEN,表中，且,。,循环执行上述操作，第,1

20、,次循环结束后，,OPEN,表的节点依次是,B,、,C,，然后进行第,2,次循环，扩展路径代价值最小的节点,C,，其后继节点有,F,和,G,，将它们放入,OPEN,表中，并提供回到父节点,C,的指针。可见，经过第,2,次循环后，,OPEN,表的节点依次为,B,、,F,、,G,。在整个搜索过程中，,OPEN,表和,CLOSED,表的状态变化如表所示。,OPEN,表和,CLOSED,表的状态变化,从表可以看出，在第,6,次循环中，步骤（,4,）判断的节点,n,是目标节点,K,。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为,，猫消耗的体力值为,。,该搜索结束后得到的搜索树如左图所示。,等

21、代价搜索树,某小说中讲述了一个曲折离奇的故事。在故事中，某人得到了藏有皇家宝藏秘密的宝匣，但是宝匣上面有一个,9,宫格拼图密码（见左图），只有将图片拼完整才可以打开宝匣。,请采用盲目搜索策略完成拼图任务。,宝匣,4.2.4,案例：宝匣上的拼图,【,解,】,（,1,）用数字表示,9,宫格内的图片块，则该拼图的初始状态如图,1,所示，目标状态如图,2,所示。,（,2,）移动拼图中空白的图块，可执行的操作有上、下、左、右，其中，需要约束空白图块不能移出,9,宫格之外。,图,1,拼图的初始状态 图,2,拼图的目标状态,（,3,）使用宽度优先搜索完成拼图任务，其搜索顺序如图所示。,拼图任务的宽度优先搜索

22、树,启 发 式 搜 索 策 略,03,启发式搜索策略又称有信息搜索策略,，是指在搜索过程中，利用与问题有关的信息，引导搜索朝最有利的方向进行，从而加快搜索的速度，提高搜索效率。启发式搜索策略中涉及的重要内容有启发性信息和估价函数，常用的启发式搜索策略有,A,搜索和,A*,搜索。,启发式搜索策略的主要依据是问题自身的启发性信息。,启发性信息,是指可确定搜索方向，简化搜索过程，且可反映问题特性的控制性信息。在启发式搜索过程中，主要根据与问题有关的启发性信息估计各个节点的代价，从而确定每一次搜索的方向。,启发性信息又是通过估价函数而作用于搜索过程的。,估价函数,常用于估计节点的代价，即通过充分利用启

23、发性信息估计出经过当前节点搜索到目标节点的代价。,4.3.1,启发性信息和估价函数,估计一个节点的价值，必须考虑两个重要的因素，即已经付出的代价和将要付出的代价。因此，可将估价函数,定义为从初始节点,出发，经过节点,n,到达目标节点,G,的所有路径中最优路径的代价估计值。,其一般形式为,其中，,表示从初始节点,到达中间节点,n,的实际代价。,表示从中间节点,n,到目标节点,G,的最优路径的估计代价。因此，,可称为,启发函数,。,添 砖 加 瓦,启发性信息按其作用可分为,3,种。,（,1,）用于确定要扩展的下一个节点，避免盲目地扩展节点。,（,2,）在扩展节点的过程中，用于决定生成哪些后继节点，

24、避免盲目地生成所有可能节点。,（,3,）用于确定应从搜索树中修剪或删除的节点，避免盲目地保留“最不具有希望”的节点。,A,搜索,又称为择优搜索，它是一种基于估价函数的启发式搜索算法，它在搜索过程中利用估价函数,对,OPEN,表中的节点进行排序，因此，,A,搜索也可称为有序搜索。,根据启发式搜索过程中选择扩展节点范围的不同，可将,A,搜索分为,全局择优搜索,和,局部择优搜索。,4.3.2,A,搜索,全局择优搜索,的基本思想是当确定下一个扩展节点时，利用估价函数 计算,OPEN,表中每个节点的估价值，然后从,OPEN,表的全部节点中选择一个 值最小的节点作为下一个要考察的节点。由于该搜索是在,OP

25、EN,表的全部节点范围内选择下一个要考察的节点，选择范围全面，故称为全局择优搜索。,全局择优搜索的搜索过程可用如图所示的算法描述。,全局择优搜索算法,1,全局择优搜索,【,例,】,猫捉老鼠问题，在猫去捕捉老鼠的路程中，老鼠察觉到危险，于是，老鼠从,K,处出发经过,P,处逃到,O,处，如左图所示。,其中，两节点间弧的数值代表猫的体力消耗值，请用全局择优搜索算法帮猫寻找捕捉路线。,猫和老鼠位置表示,【,解,】,使用全局择优搜索算法求解猫捉老鼠问题的步骤如下。,其中，估价函数,定义为,，,表示猫从节点,A,到节点的实际体力消耗值；,表示猫从节点,n,到目标节点,O,的最优路径的体力消耗值估计值，此处

26、定义,，其中,i,表示从节点,n,到目标节点,O,的节点个数，“,2”,表示默认任意两个节点间的体力消耗值都为,2,。例如，节点,K,的启发函数,。,（,1,）把起始节点,A,放入,OPEN,表中，计算估价函数值,。,（,2,）判断,OPEN,表是否为空表，若是，则问题无解，失败退出；否则继续。,OPEN,表中含有节点,A,，非空。,（,3,）把,OPEN,表中的第一个节点（记为节点,n,）移出，并放入,CLOSED,表中。第,1,次循环中，,OPEN,表中的第一个节点为,A,。,（,4,）判断节点,n,是否为目标节点，若是，则求得问题的解，成功退出；否则转向（,5,）。节点,A,不是目标节点

27、。,（,5,）判断节点,n,是否可扩展，若可扩展转向（,6,）；否则转向（,2,）。节点,A,可扩展。,（,6,）扩展节点,n,，计算所有后继节点的估价函数值,，并提供从这些后继节点回到父节点,n,的指针。扩展节点,A,，其后继节点为节点,B,和,C,，计算它们的估价函数值,和,，并提供从节点,B,和,C,回到父节点,A,的指针。,（,7,）把这些后继节点都送入,OPEN,表中，然后按照估价函数值从小到大的顺序对,OPEN,表中的全部节点进行排序，最后转向（,2,）。将节点,B,和,C,送入,OPEN,表中，此时,OPEN,表中的所有节点只有,B,和,C,，所以对,OPEN,表中的全部节点进行

28、排序后得到的节点顺序为,C,、,B,。,循环执行上述操作，其,OPEN,表和,CLOSED,表的状态变化如表所示。,OPEN,表和,CLOSED,表的状态变化,从表可以看出，在第,5,次循环中，步骤（,4,）判断的节点,n,是目标节点,O,。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为,该搜索结束后得到的搜索树如左图所示。,全局择优搜索树,局部择优搜索,的基本思想是当扩展某一个节点之后，计算该节点的每一个后继节点的估价函数值,，并在这些后继节点中选择一个,值最小的节点，作为下一个要考察的节点。由于该搜索每次都只在某个节点的所有后继节点范围内选择下一个要考察的节点，选择范围比较小，故

29、称为局部择优搜索。,局部择优搜索的搜索过程可用如左图所示的算法描述。,局部择优搜索算法,2,局部择优搜索,【,例,】,请用局部择优搜索算法求解例中的问题。,【,解,】,使用局部择优搜索算法求解例题的步骤如下：,其中，估价函数,和例中的相同，即为,，,，其中,i,表示从节点,n,到目标节点,O,的节点个数，“,2”,表示默认任意两个节点间的体力消耗值都为,2,。,（,1,）把起始节点,A,放入,OPEN,表中，计算估价函数值,。,（,2,）判断,OPEN,表是否为空表，若是，则问题无解，失败退出；否则继续。,OPEN,表中含有节点,A,，非空。,（,3,）把,OPEN,表中的第一个节点（记为节点

30、,n,）移出，并放入,CLOSED,表中。第,1,次循环中，,OPEN,表中的第一个节点为,A,。,（,4,）判断节点,n,是否为目标节点，若是，则求得问题的解，成功退出；否则转向（,5,）。节点,A,不是目标节点。,（,5,）判断节点,n,是否可扩展，若可扩展转向（,6,）；否则转向（,2,）。节点,A,可扩展。,（,6,）扩展节点,n,，计算所有后继节点的估价函数值,，并提供从这些后继节点回到父节点,n,的指针。扩展节点,A,，其后继节点为节点,B,和,C,，计算它们的估价函数值,和,，并提供从节点,B,和,C,回到父节点,A,的指针。,（,7,）按照估价函数值从小到大的顺序对所有后继节点

31、进行排序，并送入,OPEN,表的前端，最后转向（,2,）。对后继节点,B,和,C,排序得到的节点顺序为,C,、,B,，送入,OPEN,表的前端。,循环执行上述操作，其,OPEN,表和,CLOSED,表的状态变化如表所示。,从表可以看出，在第,5,次循环中，步骤（,4,）判断的节点,n,是目标节点,O,。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为,。,该搜索结束后得到的搜索树与全局择优搜索树一样。,OPEN,表和,CLOSED,表的状态变化,A*,搜索,，俗称,A,星搜索，是在,A,搜索的基础上对估价函数,中的启发函数,加上限定条件，即,，对所有节点,n,其中,，表示节点,n,到目

32、标节点最优路径的实际代价。,利用,A*,搜索进行问题求解一定能得到最优解，保证,A*,搜索找到最优解的充分条件有,4,条，分别是：,（,1,）搜索树中存在从起始节点到目标节点的最优路径。,（,2,）问题域是有限的。,（,3,）所有节点的后继节点的搜索代价值大于,0,，即两节点之间弧线的值大于,0,。,（,4,）,。,4.3.3,A*,搜索,【,例,】,请用,A*,搜索求解例中的问题。,【,解,】,使用,A*,搜索求解例题的步骤如下：,其中，估价函数,定义为,，且,。,表示猫从节点,A,到节点的实际体力消耗值；,表示猫从节点,n,到目标节点,O,的最优路径的体力消耗估计值。,定义,，其中,i,表

33、示从节点,n,到目标节点,O,的节点个数，“,1”,表示默认任意两个节点间的体力消耗值都为,1,。,（,1,）把起始节点,A,放入,OPEN,表中，计算估价函数值,。,（,2,）判断,OPEN,表是否为空表，若是，则问题无解，失败退出；否则继续。,OPEN,表中含有节点,A,，非空。,（,3,）把,OPEN,表中的第一个节点（记为节点,n,）移出，并放入,CLOSED,表中。第,1,次循环中，,OPEN,表中的第一个节点为,A,。,（,4,）判断节点,n,是否为目标节点，若是，则求得问题的解，成功退出；否则转向（,5,）。节点,A,不是目标节点。,（,5,）判断节点,n,是否可扩展，若可扩展转

34、向（,6,）；否则转向（,2,）。节点,A,可扩展。,（,6,）扩展节点,n,，计算所有后继节点的估价函数值,，并提供从这些后继节点回到父节点,n,的指针。扩展节点,A,，其后继节点为节点,B,和,C,，计算它们的估价函数值,和,，并提供从节点,B,和,C,回到父节点,A,的指针。,（,7,）把这些后继节点都送入,OPEN,表中，然后按照估价函数值从小到大的顺序对,OPEN,表中的全部节点进行排序，最后转向（,2,）。将节点,B,和,C,送入,OPEN,表中，此时,OPEN,表中的所有节点只有,B,和,C,，所以对,OPEN,表中的全部节点进行排序后得到的节点顺序为,C,、,B,。,循环执行上

35、述操作，其,OPEN,表和,CLOSED,表的状态变化如表所示。,OPEN,表和,CLOSED,表的状态变化,从表可以看出，在第,7,次循环中，步骤（,4,）判断的节点,n,是目标节点,O,。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为，,且该路线为最优路线。,该搜索结束后得到的搜索树如图所示。,A*,搜索树,知 识 库,A*,搜索具有下列性质。,（,1,）可采纳性。对于一个可求解的问题，如果一个搜索算法能在有限步内终止并找到问题的最优解，则称该搜索算法是可采纳的。,（,2,）单调性。所谓单调性是指在,A*,搜索中，如果对其估价函数中的启发性函数,加上适当的单调性限制条件，就可以减

36、少对,OPEN,表或,CLOSED,表的检查和调整，从而提高搜索效率。,（,3,）信息性。所谓信息性就是指比较两个,A*,搜索的启发函数,和,，如果对搜索空间中的任一节点,n,都有,，就代表搜索策略,比,具有更多的信息性。,有一个 的迷宫地图（见图），其中，用字母表示某位置允许通过，其余位置不允许通过；入口和出口的位置在图中已经标出。现规定在迷宫中只能横向或纵向移动，不能斜向移动，请寻找从入口到出口的最短路径。,4.3.4,案例：迷宫寻路,迷宫地图,【,解,】,（,1,）启发式搜索的关键是定义启发式函数，本问题的启发式函数定义为,，其中,，代表已走过的真实距离,表示不考虑路径是否可通行的情况下

37、，当前节点到目标节点所在行的纵向距离。,（,2,）使用局部择优搜索解决此问题的步骤如下。,从入口进，此时已走过的真实距离,，节点,A,到目标节点所在行的纵向距离,，将节点,A,放入,OPEN,表中，计算估价函数值。,判断,OPEN,表是否为空表，若是，则问题无解，失败退出；否则继续。,OPEN,表中含有节点,A,，非空。,把,OPEN,表中的第一个节点（记为节点,n,）移出，并放入,CLOSED,表中。第,1,次循环中，,OPEN,表中的第一个节点为,A,。,判断节点,n,是否为目标节点，若是，则求得问题的解，成功退出；否则转向。目标节点的位置坐标在出口处，而此时，位置坐标在入口处。,判断节点

38、,n,是否可扩展，若可扩展转向；否则转向。节点,A,可扩展，下一步可移动的位置有,B,和,E,。,扩展节点,n,，计算所有后继节点的估价函数值,，并提供从这些后继节点回到父节点,n,的指针。扩展节点,A,，其后继节点为节点,B,和,E,，计算它们的估价函数值,和,，并提供从节点,B,和,E,回到父节点,A,的指针。,按照估价函数值从小到大的顺序对所有后继节点进行排序，并送入,OPEN,表的前端，最后转向。对后继节点,B,和,E,排序得到的节点顺序为,E,、,B,，送入,OPEN,表的前端。,循环执行上述操作，其,OPEN,表和,CLOSED,表的状态变化如表所示。,4.3.4,案例：迷宫寻路,OPEN,表和,CLOSED,表的状态变化,从表可以看出，在第,9,次循环中，步骤判断的节点,n,是目标节点,K,。此时，找到一个解，成功退出。便可得到从迷宫入口到出口的最短路径为 。,该搜索结束后得到的搜索树如图所示。,局部择优搜索树,Please Add Your Title Here,insert your desired text here,感谢观看,THANKS,