西电人工智能9 确定性推理 part2

1、西安电子科技大学西安电子科技大学Artificial Intelligence (AI)人工智能人工智能主讲：戚玉涛Email：qi_第三章：确定第三章：确定性推理性推理西安电子科技大学西安电子科技大学内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.归结演绎推理归结演绎推理5.5.基于规则的演绎推理基于规则的演绎推理西安电子科技大学西安电子科技大学搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的搜索策略状态空间的搜索策略与与/ /或树的搜索策略或树的搜索策略搜索的完备性与效率搜索的完备性与效率西安电子科技大学西安电子科

2、技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间搜索算法的数据结构和符号约定状态空间搜索算法的数据结构和符号约定OPEN表：表：未扩展节点表，用于存放刚生成节点未扩展节点表，用于存放刚生成节点CLOSED表：表：已扩展节点表，用于

3、存放已经扩已扩展节点表，用于存放已经扩展或将要扩展节点的展或将要扩展节点的S：用表示问题的初始状态用表示问题的初始状态G：表示搜索过程所得到的搜索图表示搜索过程所得到的搜索图M：表示当前扩展节点新生成的表示当前扩展节点新生成的且不为自己先辈且不为自己先辈的子节点集的子节点集西安电子科技大学西安电子科技大学状态空间的搜索策略v图搜索的一般过程图搜索的一般过程(1) 把初始节点把初始节点S放入未扩展节点表放入未扩展节点表OPEN表，并建立目表，并建立目前仅包含前仅包含S的图的图G；(2) 检查检查OPEN表是否为空，若为空，则问题无解，失表是否为空，若为空，则问题无解，失败退出；败退出；(3) 把

4、把OPEN表的表的第一个节点第一个节点取出放入已扩展节点表取出放入已扩展节点表CLOSED表，并记该节点为节点表，并记该节点为节点n；(4)考察节点考察节点n是否为目标节点。若是则得到了问题的解，是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图成功退出。此时的解为追踪图G中沿着指针中沿着指针（步骤（步骤6中中设置的指针）设置的指针）从从n到初始节点到初始节点S的路径。的路径。西安电子科技大学西安电子科技大学状态空间的搜索策略v图搜索的一般过程图搜索的一般过程(5) 扩展节点扩展节点n，生成一组子节点。把这些子节点中，生成一组子节点。把这些子节点中不是不是节点节点n先辈的那部分子

5、节点先辈的那部分子节点记入集合记入集合M，并把这些子节，并把这些子节点作为节点点作为节点n的子节点加入的子节点加入G中中(6) 针对针对M中子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：p 对那些没有在对那些没有在G中出现过的中出现过的M成员设置一个指向其父节点成员设置一个指向其父节点（即节点（即节点n）的指针，并把它放入）的指针，并把它放入OPEN表。（新生成的）表。（新生成的）p 对那些原来已在对那些原来已在G中出现过，但还没有被扩展的中出现过，但还没有被扩展的M成员，确成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）定是否需要修改它指向父节点的指针。

6、（原生成但未扩展的）p 对于那些先前已在对于那些先前已在G中出现过，并已经扩展了的中出现过，并已经扩展了的M成员，确成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）展过的）西安电子科技大学西安电子科技大学v图搜索的一般过程图搜索的一般过程(7) 按某种策略对按某种策略对OPEN表中的节点表中的节点进行排序。进行排序。(8) 转第转第(2)步。步。 状态空间的搜索策略西安电子科技大学西安电子科技大学广度优先搜索v状态空间的广度优先搜索状态空间的广度优先搜索广度优先搜索的基本思想：广度优先搜索的基本思想：p从初始节点从初始

7、节点S开始逐层向下扩展，在第开始逐层向下扩展，在第n层层节点还没有全部搜索完之前，不进入第节点还没有全部搜索完之前，不进入第n+1层节点的搜索。层节点的搜索。p未扩展节点表未扩展节点表OPEN表中的节点总是按进入表中的节点总是按进入的先后排序，先进入的节点排在前面，后进的先后排序，先进入的节点排在前面，后进入的节点排在后面。入的节点排在后面。西安电子科技大学西安电子科技大学广度优先搜索v状态空间的广度优先搜索状态空间的广度优先搜索广度优先搜索算法流程：广度优先搜索算法流程： (1)把初始节点把初始节点S放入放入OPEN表中；表中； (2)如果如果OPEN表为空，则问题无解，失败退出；表为空，则

8、问题无解，失败退出； (3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记表，并记该节点为该节点为n； (4)考察节点考察节点n是否为目标节点。若是，则得到问题的解，是否为目标节点。若是，则得到问题的解，成功退出；成功退出； (5)若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6)扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的尾部尾部，并为每，并为每一个子节点设置指向父节点的指针，然后转第一个子节点设置指向父节点的指针，然后转第(2)步。步。西安电子科技大学西安电子科技大学广度优先搜索v广度优先搜索的例子：广度优先搜索的例子：

9、八数码难题八数码难题在在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状态，目标状态Sg，如下图所示。要求应用广度优先搜索策略寻找从初始如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径状态到目标状态的解路径。1238476528314765S0Sg西安电子科技大学西安电子科技大学广度优先搜索八八数数码码难难题题的的宽宽度度优优先先搜搜索索树树西安电子科技大学西安电子科技大学广度优先搜索v在上述广度优先算法中需要注意两个问题：在上述广度优先算法中需要注意两个问题：对于任意一个可扩

10、展的节点，总是按照固定的操作对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（符的顺序对其进行扩展（空格左移、上移、右移、空格左移、上移、右移、下移下移）。）。在对任一节点进行扩展的时候，在对任一节点进行扩展的时候，如果所得的某个子如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入不再重复画出（不送入OPEN表）表）。因此，广度优先搜索的本质是，以初始节点为根节因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一点，在状态空间图中按照广度优先的原则，生成一棵搜索树。棵搜

11、索树。西安电子科技大学西安电子科技大学广度优先搜索v广度优先搜索的特点：广度优先搜索的特点：优点：优点：p只要问题有解，用广度优先搜索总可以得到只要问题有解，用广度优先搜索总可以得到解，解，而且得到的是路径最短的解而且得到的是路径最短的解。缺点：缺点：p广度优先搜索盲目性较大，当目标节点距初广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索始节点较远时将会产生许多无用节点，搜索效率低。效率低。西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目

12、搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索的基本思想：深度优先搜索的基本思想：p从初始节点从初始节点S开始，在其子节点中选择一个最新开始，在其子节点中选择一个最新生成的节点进行考察生成的节点进行考察p如果该子节点不是目标节点且可以扩展，则扩如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选展该子节点，然

13、后再在此子节点的子节点中选择一个最新生成的节点进行考察择一个最新生成的节点进行考察p依此向下搜索，直到某个子节点既不是目标节依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进点，又不能继续扩展时，才选择其兄弟节点进行考察。行考察。西安电子科技大学西安电子科技大学深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索深度优先搜索算法流程：深度优先搜索算法流程： (1) 把初始节点把初始节点S放入放入OPEN表中；表中； (2) 如果如果OPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) 把把OPEN表的第一个节点取出放入表的第一个节点

14、取出放入CLOSED表，并记表，并记该节点为该节点为n； (4) 考察节点考察节点n是否为目标节点。若是，则得到问题的解，是否为目标节点。若是，则得到问题的解，成功退出；成功退出； (5) 若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6) 扩展节点扩展节点n，将其子节点放入，将其子节点放入OPEN表的表的首部首部，并为，并为每一个子节点设置每一个子节点设置 指向父节点的指针，然后转第指向父节点的指针，然后转第(2)步。步。西安电子科技大学西安电子科技大学深度优先搜索v深度优先搜索：深度优先搜索：八数码难题八数码难题八数码难题的深度优八数码难题的深度优先搜索如右图先搜索如右图

15、首先扩展最新产生的首先扩展最新产生的(最深的最深的)节点节点如果目标节点不在当如果目标节点不在当前搜索的分支上？前搜索的分支上？西安电子科技大学西安电子科技大学深度优先搜索v深度优先搜索与广度优先搜索的唯一区别是：深度优先搜索与广度优先搜索的唯一区别是：广度广度优先搜索是将节点优先搜索是将节点n的子节点放入到的子节点放入到OPEN表的表的尾部尾部，而深，而深度优先搜索是把节点度优先搜索是把节点n的子节点放入到的子节点放入到OPEN表的表的首部首部。v 在深度优先搜索中，搜索一旦进入某个分支，就将沿着该在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上

16、，则可分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。分支又是一个无穷分支，则就不可能得到解。所以深度优所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。先搜索是不完备的，即使问题有解，它也不一定能求得解。v深度优先搜索本质：深度优先搜索本质：以初始节点为根节点，在状态空以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。间图中按照深度优先的原则，生成一棵搜索树。西安电子科技大学西安电子科技大学有界深度优先搜索v有界深度优先

17、搜索：有界深度优先搜索：动机：动机：为了防止搜索过程沿着无益的路径扩展为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度，即下去，往往给出一个节点扩展的最大深度，即深度界限。深度界限。思想：思想：对状态空间的深度优先搜索引入搜索深对状态空间的深度优先搜索引入搜索深度界限，设为度界限，设为dm，当搜索深度达到了深度界限，当搜索深度达到了深度界限而仍未出现目标节点时，就换一个分支进行搜而仍未出现目标节点时，就换一个分支进行搜索。索。西安电子科技大学西安电子科技大学有界深度优先搜索八数码难题：八数码难题：dm=4西安电子科技大学西安电子科技大学有界深度优先搜索v有界深度优先搜索：

18、有界深度优先搜索：问题：问题：如果问题有解，且其路径长度如果问题有解，且其路径长度 dm ，则，则上述搜索过程一定能求得解。但是，若解的路上述搜索过程一定能求得解。但是，若解的路径长度径长度 dm,则上述搜索过程就得不到解。这说则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是明在有界深度优先搜索中，深度界限的选择是很重要的。很重要的。要恰当地给出要恰当地给出dm的值是比较困难的。即使能求的值是比较困难的。即使能求出解，它也不一定是最优解。出解，它也不一定是最优解。西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想

19、状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学代价树搜索v代价树：代价树：边上标有代价边上标有代价( (或费用或费用) )的树称为代价树的树称为代价树v 在代价树中，若用在代价树中，若用g(x)表示从初始节点表示从初始节点S到节点到节点x的代价，的代价，用用c(x1,x2)表示从父节点表示从父节点x1到子节点到子节点x2的代价，则有：的代

20、价，则有：g(x2)=g(x1)+c(x1,x2)v代价树搜索：代价树搜索：考虑边的代价的搜索方法，代价树搜索的考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法目的是为了找到一条代价最小的解路径。代价树搜索方法包括：包括：代价树的广度优先搜索代价树的广度优先搜索代价树的深度优先搜索代价树的深度优先搜索西安电子科技大学西安电子科技大学代价树的广度优先搜索v代价树的广度优先搜索代价树的广度优先搜索基本思想：基本思想：每次从每次从OPEN表中选择节点往表中选择节点往CLOSED表表传送时，传送时，总是选择其中代价最小的节点总是选择其中代价最小的节点。也就是说，。

21、也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。面，而不管节点在代价树中处于什么位置上。如果问题有解，代价树的广度优先搜索一定可以求得如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。解，并且求出的是最优解。该算法应用的条件：该算法应用的条件：该算法是针对代价树的算法。该算法是针对代价树的算法。为了采用该算法对图进行搜索，为了采用该算法对图进行搜索，必须先将图转换为代必须先将图转换为代价树价

22、树。西安电子科技大学西安电子科技大学代价树的广度优先搜索v 代价树的广度优先搜索算法流程：代价树的广度优先搜索算法流程：(1) 把初始节点把初始节点S放入放入OPEN表中，置表中，置S的代价的代价g(S)=0； (2) 如果如果OPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) 把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记该节表，并记该节点为点为n； (4) 考察节点考察节点n是否为目标。若是，则找到了问题的解，成功是否为目标。若是，则找到了问题的解，成功退出；退出； (5) 若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；否

23、则转第步；否则转第(6)步；步；(6)扩展节点扩展节点n，为每一个子节点都配置指向父节点的指针，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入计算各子节点的代价，并将各子节点放入OPEN表中。表中。并根并根据各子结点的代价对据各子结点的代价对OPEN表中的表中的全部结点全部结点按由小到大的顺按由小到大的顺序排序序排序。然后转第。然后转第(2)步。步。西安电子科技大学西安电子科技大学代价树的广度优先搜索v例子：例子：城市交通问题。设有城市交通问题。设有5个城市，它们之间的交通线个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个城市之间的交通路如下方左图所示，

24、图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从费用，即代价。用代价树的广度优先搜索，求从A市出发市出发到到E市，费用最小的交通路线。市，费用最小的交通路线。ABCDE43 4 523城市交通图城市交通图西安电子科技大学西安电子科技大学代价树的广度优先搜索v解：解：首先将交通图转化为代价首先将交通图转化为代价树。具体转化方法如下：树。具体转化方法如下： 从起始节点从起始节点A开始，把与它直接开始，把与它直接相邻的节点作为它的子节点相邻的节点作为它的子节点 对其他节点也做相同的处理对其他节点也做相同的处理 若一个节点已经为某节点的直系若一个节点已经为某节点的直系先辈节点

25、时，就不能作为这个节先辈节点时，就不能作为这个节点的子节点。点的子节点。 图中除了起始节点图中除了起始节点A之外，其它之外，其它节点都可能要在代价树中出现多节点都可能要在代价树中出现多次，为了区分它们的多次出现，次，为了区分它们的多次出现，分别用下标分别用下标1,2，标出标出城市交通图的代价树城市交通图的代价树2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35西安电子科技大学西安电子科技大学代价树的广度优先搜索v解：解：对此代价树进行广度优先搜索，可得到最优对此代价树进行广度优先搜索，可得到最优解，如图红线部分为最优解，其代价为解，如图红线部分为最优解，其代价为8ABC

26、DE43 4 5232 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35西安电子科技大学西安电子科技大学代价树的深度优先搜索v代价树的深度优先搜索代价树的深度优先搜索基本思想：基本思想：与代价树的广度优先搜索不同，代与代价树的广度优先搜索不同，代价树的深度优先搜索是价树的深度优先搜索是从刚扩展出的子节点中从刚扩展出的子节点中选择选择一个代价最小的节点送入一个代价最小的节点送入CLOSED表进行表进行考察，而不是在整个考察，而不是在整个OPEN表中选择代价最小表中选择代价最小的。的。西安电子科技大学西安电子科技大学代价树的深度优先搜索v 代价树的深度优先搜索算法流程：代价树

27、的深度优先搜索算法流程：(1) 把初始节点把初始节点S放入放入OPEN表中，置表中，置S的代价的代价g(S)=0； (2) 如果如果OPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出； (3) 把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并表，并记该节点为记该节点为n； (4) 考察节点考察节点n是否为目标节点。若是，则找到了问题是否为目标节点。若是，则找到了问题的解，成功退出；的解，成功退出； (5) 若节点若节点n不可扩展，则转第不可扩展，则转第(2)步；步； (6) 扩展节点扩展节点n，生成其子节点，生成其子节点，将这些子节点按边代价将这些子

28、节点按边代价由小到大放入由小到大放入Open表的首部表的首部，并为每一个子节点设置，并为每一个子节点设置指向父节点的指针。然后转第指向父节点的指针。然后转第(2)步。步。西安电子科技大学西安电子科技大学状态空间的盲目搜索v状态空间的盲目搜索状态空间的盲目搜索上述几种搜索方法的本质是，以初始节点为根上述几种搜索方法的本质是，以初始节点为根节点，按照既定的策略对状态空间图进行遍历，节点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。并希望能够尽早发现目标节点。由于对状态空间图遍历的策略是既定的，因此由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。这些方法统称为

29、盲目搜索方法。盲目搜索具有较大的盲目性，产生的无用节点盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。较多，效率不高。西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学启发性信息和估价函数v启发式搜索：启发式搜索：采用问题自身

30、的特性信息，以指导搜索朝采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。着最有希望的方向前进。v启发性信息的概念：启发性信息的概念：启发性信息是指那种与具体问题启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。进的控制信息。启发信息的启发能力越强，扩展的无用结启发信息的启发能力越强，扩展的无用结点越少。点越少。v启发性信息的种类启发性信息的种类有效地帮助确定扩展节点的信息有效地帮助确定扩展节点的信息有效的帮助决定哪些后继节点应被生成的信息有效的帮助决定哪些后继节点应被生成的信息能决定在扩展一个

31、节点时哪些节点应从搜索树上删除能决定在扩展一个节点时哪些节点应从搜索树上删除的信息的信息西安电子科技大学西安电子科技大学启发性信息和估价函数v估价函数：估价函数：用于评估节点重要性的函数称为估价用于评估节点重要性的函数称为估价函数。估价函数的一般形式为：函数。估价函数的一般形式为：f(x) = g(x)+h(x)g(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；h(x)是从节点是从节点x到目标节点到目标节点Sg的最优路径的代价的最优路径的代价的的估计估计，它体现了问题的启发性信息。，它体现了问题的启发性信息。h(x)称为称为启发函数启发函数。西安电子科技大学西安电子科技大学

32、启发性信息和估价函数v例子：例子：八数码难题八数码难题设问题的初始状态设问题的初始状态S0和目标状态和目标状态Sg如图所示如图所示估价函数为：估价函数为： f(n)=d(n)+W(n)d(n)：表示节点：表示节点n在搜索树中的深在搜索树中的深度度W(n)：表示节点：表示节点n中中“不在位不在位”的的数码个数数码个数请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)1238476528314765S0Sg西安电子科技大学西安电子科技大学启发性信息和估价函数v计算初始状态计算初始状态S0的估价函数值的估价函数值f(S0)v解：解：取取g(n)=d(n)，h(n)=W(n) 它说明是

33、用从它说明是用从S0到到n的路径上的单位的路径上的单位代价表示实际代价代价表示实际代价 用结点用结点n中中“不在位不在位”的数码个数作的数码个数作为启发信息。为启发信息。 一般来说，某节点中的一般来说，某节点中的“不在位不在位”的的数码个数越多，说明它离目标节点越数码个数越多，说明它离目标节点越远（代价的估计）。远（代价的估计）。 对初始节点对初始节点S0，d(S0)=0，W(S0)=3。因此，因此， f(S0)=0+3=3 1238476528314765S0Sg西安电子科技大学西安电子科技大学状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略状态空间搜索的基本思想状态空间搜索的基本思

34、想图搜索的一般过程图搜索的一般过程状态空间的盲目搜索状态空间的盲目搜索p广度优先搜索广度优先搜索p深度优先搜索深度优先搜索p代价树搜索代价树搜索状态空间的启发式搜索状态空间的启发式搜索p启发性信息和估价函数启发性信息和估价函数pA算法和算法和A*算法算法西安电子科技大学西安电子科技大学A算法vA算法：算法：在图搜索算法中，如果能在搜索的每一步都在图搜索算法中，如果能在搜索的每一步都利利用估价函数用估价函数f(n)=g(n)+h(n)对对OPEN表中的节点进行排序表中的节点进行排序，则该搜索算法为则该搜索算法为A算法算法。 由于估价函数中带有问题自身的由于估价函数中带有问题自身的启发性信息，因此

35、，启发性信息，因此，A算法也被称为算法也被称为启发式搜索算法启发式搜索算法。vA算法的类型：算法的类型：可根据搜索过程中选择扩展节点的范围，可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为：将启发式搜索算法分为：全局择优搜索算法全局择优搜索算法： 从从OPEN表的表的所有节点所有节点中选择一中选择一个估价函数值最小的一个进行扩展。个估价函数值最小的一个进行扩展。局部择优搜索算法：局部择优搜索算法：仅从刚生成的子节点仅从刚生成的子节点中选择一个中选择一个估价函数值最小的一个进行扩展。估价函数值最小的一个进行扩展。西安电子科技大学西安电子科技大学A算法v 全局择优搜索算法流程全局择优搜索算

36、法流程(1)把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。(2)如果如果OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表。表。(4)考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。(5)若节点若节点n不可扩展，则转第不可扩展，则转第2步。步。(6)扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。并为每一个子节点

37、都配置指向父节点的指针。把这些子节把这些子节点都送入点都送入OPEN表中，然后对表中，然后对OPEN表中的全部节点按估价表中的全部节点按估价值从小至大的顺序进行排序值从小至大的顺序进行排序，然后转第，然后转第2步。步。西安电子科技大学西安电子科技大学A算法v全局择优搜索算法：全局择优搜索算法：八数码难题八数码难题设问题的初始状态设问题的初始状态S0和目标状态和目标状态Sg如图所示如图所示估价函数为：估价函数为： f(n)=d(n)+W(n)d(n)：表示节点：表示节点n在搜索树中的深在搜索树中的深度度W(n)：表示节点：表示节点n中中“不在位不在位”的的数码个数数码个数用全局择优搜索解决该问题

38、用全局择优搜索解决该问题1238476528314765S0Sg西安电子科技大学西安电子科技大学启发性信息和估价函数v 用全局择优搜索求解八数用全局择优搜索求解八数码难题码难题v 解：解： 该问题的全局择优搜索树该问题的全局择优搜索树如右图所示如右图所示 在该图中，每个节点旁边在该图中，每个节点旁边的数字是该节点的估价函的数字是该节点的估价函数值数值 该问题的解为：该问题的解为： S0S1S2S3Sg西安电子科技大学西安电子科技大学A算法v 局部择优搜索算法流程局部择优搜索算法流程(1) 把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。(2)如果如果OPEN表为空，则问题无

39、解，退出。表为空，则问题无解，退出。(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表。表。(4)考察节点考察节点n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。(5)若节点若节点n不可扩展，则转第不可扩展，则转第2步。步。(6) 扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，计算每个子节点的估价值，并按估价值从小到大的顺序放到并按估价值从小到大的顺序放到OPEN表中的首部表中的首部，并为，并为每一个子节点都配置指向父节点的指针，然后转第每一个子节点都配置指向父节点的指

40、针，然后转第2步。步。西安电子科技大学西安电子科技大学A*算法vA*算法：算法：A*算法是对算法是对A算法的估价函数算法的估价函数f(n)=g(n)+h(n)加加上某些限制后得到的一种启发式搜索算法。上某些限制后得到的一种启发式搜索算法。v 假设假设f*(n)是从初始节点出发经过节点是从初始节点出发经过节点n达到目标节点的最达到目标节点的最小代价，估价函数小代价，估价函数f(n)是对是对f*(n)的的估计值估计值。且。且 f*(n)=g*(n)+h*(n)v A*算法对算法对A算法（全局择优的启发式搜索算法）中的算法（全局择优的启发式搜索算法）中的g(n)和和h(n)分别提出如下限制：分别提出

41、如下限制： 第一，第一，g(n)是对最小代价是对最小代价g*(n)的估计，且的估计，且g(n)0； 第二，第二，h(n)是最小代价是最小代价h*(n)的的下界下界，即对任意节点，即对任意节点n均有均有h(n)h*(n)。v 即：满足上述两条限制的即：满足上述两条限制的A算法称为算法称为A*算法算法。西安电子科技大学西安电子科技大学A*算法v在在A*算法中，算法中， g(n)比较容易得到，它比较容易得到，它实际上就是从初始节点实际上就是从初始节点S0到节点到节点n的路的路径代价，恒有：径代价，恒有： g(n) g*(n)v在算法执行过程中，随着更多搜索信在算法执行过程中，随着更多搜索信息的获得，

42、息的获得， g(n)呈下降的趋势。呈下降的趋势。v如右图的例子：如右图的例子：p对对S0扩展后扩展后g(n1)=3， g(n2)=7p对对n1扩展后扩展后g(n2)=6， g(n3)=5S0n137n2n332西安电子科技大学西安电子科技大学A*算法vA*算法的可纳性：算法的可纳性：可纳性的含义：可纳性的含义：对任一状态空间图，当从初始对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法节点到目标节点有路经存在时，如果搜索算法总能在总能在有限步骤内有限步骤内找到一条从初始节点到目标找到一条从初始节点到目标节点的节点的最佳路径最佳路径，并在此路径上结束，则称该，并在此路径上结束，则

43、称该搜索算法是搜索算法是可纳的可纳的。A*算法是可纳的，即它能在有限步内终止，并算法是可纳的，即它能在有限步内终止，并找到问题的最优解。找到问题的最优解。证明：证明：西安电子科技大学西安电子科技大学A*算法A*算法的可纳性证明：算法的可纳性证明： 第一步：第一步：对于有限图，对于有限图， A*算法一定会在有算法一定会在有限步骤内终止。限步骤内终止。 第二步：第二步：对于无限图，如果从初始节点对于无限图，如果从初始节点S0到到目标节点目标节点Sg有路径存在，则有路径存在，则A*算法也必然会算法也必然会终止。终止。 第三步：第三步： A*算法一定终止在最优路径上。算法一定终止在最优路径上。西安电子

44、科技大学西安电子科技大学A*算法vA*算法的最优性：算法的最优性：h(n)的确定依赖于具体问题领域的启发性信息，的确定依赖于具体问题领域的启发性信息，其中其中h(n) h*(n)的限制是十分重要的，的限制是十分重要的，它可以它可以保证保证A*算法能找到问题的最优解算法能找到问题的最优解。A*算法的搜索效率很大程度上取决于估价函数算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，。一般来说，在满足在满足h(n) h*(n)的前提下，的前提下，h(n)的值越大越好的值越大越好。h(n)的值越大，说明它携的值越大，说明它携带的启发性信息越多，带的启发性信息越多，A*算法搜索时扩展的节算法搜索

45、时扩展的节点就越少，搜索效率就越高。点就越少，搜索效率就越高。西安电子科技大学西安电子科技大学A*算法vh(n)的单调限制的单调限制在在A*算法中，每当扩展一个节点算法中，每当扩展一个节点n时，都需要检查其子时，都需要检查其子节点是否已在节点是否已在OPEN表或表或CLOSED表中。表中。p对已在对已在OPEN表中的子节点，需要决定是否调整指表中的子节点，需要决定是否调整指向其父节点的指针；向其父节点的指针；p对已在对已在CLOSED表中的子节点，除需要决定是否调表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。子节点的后继节点的父指针。如果能够保证，每当扩展一个节点时就已经找到了通如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述检查。往这个节点的最佳路径，就没有必要再去作上述检