资源描述
ArtificialIntelligence(AI)章：知识表示章：知识表示与推理与推理内容提要第二章：知识表示与推理第二章：知识表示与推理1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理二、确定性推理二、确定性推理二、确定性推理二、确定性推理搜索策略v搜索策略搜索策略v搜索的基本概念搜索的基本概念v状态空间的搜索策略状态空间的搜索策略v与与/或树的搜索策略或树的搜索策略v搜索的完备性与效率搜索的完备性与效率状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法状态空间的搜索策略v状态空间搜索算法的数据结构和符号约定状态空间搜索算法的数据结构和符号约定vOPENOPEN表：未扩展节点表，用于存放刚生成节点表：未扩展节点表，用于存放刚生成节点vCLOSEDCLOSED表：已扩展节点表，用于存放已经扩展或将表：已扩展节点表，用于存放已经扩展或将要扩展的节点要扩展的节点vS S：用表示问题的初始状态：用表示问题的初始状态vG G：表示搜索过程所得到的搜索图：表示搜索过程所得到的搜索图vM M：表示当前扩展节点新生成的且不为自己先辈的：表示当前扩展节点新生成的且不为自己先辈的子节点集子节点集状态空间的搜索策略v图搜索的一般过程图搜索的一般过程v(1)(1)把初始节点把初始节点S S放入未扩展节点表放入未扩展节点表OPENOPEN表，并建表，并建立目前仅包含立目前仅包含S S的图的图G G；v(2)(2)检查检查OPENOPEN表是否为空，若为空，则问题无解，表是否为空，若为空，则问题无解，失败退出；失败退出；v(3)(3)把把OPENOPEN表的第一个节点取出放入已扩展节点表的第一个节点取出放入已扩展节点表表CLOSEDCLOSED表，并记该节点为节点表，并记该节点为节点n n；v(4)(4)考察节点考察节点n n是否为目标节点。若是则得到了问是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图题的解，成功退出。此时的解为追踪图G G中沿着指中沿着指针（步骤针（步骤6 6中设置的指针）从中设置的指针）从n n到初始节点到初始节点S S的路径。的路径。状态空间的搜索策略v图搜索的一般过程图搜索的一般过程v(5)(5)扩展节点扩展节点n n，生成一组子节点。把这些子节点，生成一组子节点。把这些子节点中不是节点中不是节点n n先辈的那部分子节点记入集合先辈的那部分子节点记入集合M M，并，并把这些子节点作为节点把这些子节点作为节点n n的子节点加入的子节点加入G G中中v(6)(6)针对针对M M中子节点的不同情况，分别作如下处理：中子节点的不同情况，分别作如下处理：v 对那些没有在对那些没有在G G中出现过的中出现过的M M成员设置一个指向成员设置一个指向其父节点（即节点其父节点（即节点n n）的指针，并把它放入）的指针，并把它放入OPENOPEN表。表。（新生成的）（新生成的）v 对那些原来已在对那些原来已在G G中出现过，但还没有被扩展中出现过，但还没有被扩展的的M M成员，确定是否需要修改它指向父节点的指针。成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）（原生成但未扩展的）v 对于那些先前已在对于那些先前已在G G中出现过，并已经扩展了中出现过，并已经扩展了的的M M成员，确定是否需要修改其后继节点指向父节成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）点的指针。（原生成也扩展过的）v图搜索的一般过程图搜索的一般过程v(7)(7)按某种策略对按某种策略对OPENOPEN表中的节点进表中的节点进行排序。行排序。v(8)(8)转第转第(2)(2)步。步。状态空间的搜索策略广度优先搜索v状态空间的广度优先搜索状态空间的广度优先搜索v广度优先搜索的基本思想：广度优先搜索的基本思想：v从初始节点从初始节点S S开始逐层向下扩展，在第开始逐层向下扩展，在第n n层节点还层节点还没有全部搜索完之前，不进入第没有全部搜索完之前，不进入第n+1n+1层节点的搜索。层节点的搜索。v未扩展节点表未扩展节点表OPENOPEN表中的节点总是按进入的先后表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排排序，先进入的节点排在前面，后进入的节点排在后面。在后面。广度优先搜索v状态空间的广度优先搜索状态空间的广度优先搜索v广度优先搜索算法流程：广度优先搜索算法流程：v(1)(1)把初始节点把初始节点S S放入放入OPENOPEN表中；表中；v(2)(2)如果如果OPENOPEN表为空，则问题无解，失败退出；表为空，则问题无解，失败退出；v(3)(3)把把OPENOPEN表的第一个节点取出放入表的第一个节点取出放入CLOSEDCLOSED表，并表，并记该节点为记该节点为n n；v(4)(4)考察节点考察节点n n是否为目标节点。若是，则得到问是否为目标节点。若是，则得到问题的解，成功退出；题的解，成功退出；v(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；v(6)(6)扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的尾部，表的尾部，并为每一个子节点设置指向父节点的指针，然后并为每一个子节点设置指向父节点的指针，然后转第转第(2)(2)步。步。广度优先搜索v广度优先搜索的例子：八数码难题广度优先搜索的例子：八数码难题v在在3333的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8的八张牌，初始状态的八张牌，初始状态S0S0，目标，目标状态状态SgSg，如下图所示。要求应用广度优先搜索策，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。略寻找从初始状态到目标状态的解路径。1238476528314765S0Sg广度优先搜索八八数数码码难难题题的的宽宽度度优优先先搜搜索索树树广度优先搜索v在上述广度优先算法中需要注意两个问题：在上述广度优先算法中需要注意两个问题：v对于任意一个可扩展的节点，总是按照固定的操对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（空格左移、上移、右作符的顺序对其进行扩展（空格左移、上移、右移、下移）。移、下移）。v在对任一节点进行扩展的时候，如果所得的某个在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入弃，不再重复画出（不送入OPENOPEN表）。表）。v因此，广度优先搜索的本质是，以初始节点为根因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。成一棵搜索树。广度优先搜索v广度优先搜索的特点：广度优先搜索的特点：v优点：优点：v只要问题有解，用广度优先搜索总可以得到解，只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。而且得到的是路径最短的解。v缺点：缺点：v广度优先搜索盲目性较大，当目标节点距初始节广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。点较远时将会产生许多无用节点，搜索效率低。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索v深度优先搜索的基本思想：深度优先搜索的基本思想：v从初始节点从初始节点S S开始，在其子节点中选择一个最新生开始，在其子节点中选择一个最新生成的节点进行考察成的节点进行考察v如果该子节点不是目标节点且可以扩展，则扩展如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察个最新生成的节点进行考察v依此向下搜索，直到某个子节点既不是目标节点，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。又不能继续扩展时，才选择其兄弟节点进行考察。深度优先搜索v状态空间的深度优先搜索状态空间的深度优先搜索v深度优先搜索算法流程：深度优先搜索算法流程：v(1)(1)把初始节点把初始节点S S放入放入OPENOPEN表中；表中；v(2)(2)如果如果OPENOPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；v(3)(3)把把OPENOPEN表的第一个节点取出放入表的第一个节点取出放入CLOSEDCLOSED表，表，并记该节点为并记该节点为n n；v(4)(4)考察节点考察节点n n是否为目标节点。若是，则得到问是否为目标节点。若是，则得到问题的解，成功退出；题的解，成功退出；v(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；v(6)(6)扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的首部，表的首部，并为每一个子节点设置并为每一个子节点设置 指向父节点的指针，然后指向父节点的指针，然后转第转第(2)(2)步。步。深度优先搜索v深度优先搜索：深度优先搜索：v八数码难题八数码难题v八数码难题的深度优八数码难题的深度优先搜索如右图先搜索如右图v首先扩展最新产生的首先扩展最新产生的(最深的最深的)节点节点v如果目标节点不在当如果目标节点不在当前搜索的分支上？前搜索的分支上？深度优先搜索v深度优先搜索与广度优先搜索的唯一区别是：广深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点度优先搜索是将节点n的子节点放入到的子节点放入到OPEN表的表的尾部，而深度优先搜索是把节点尾部，而深度优先搜索是把节点n的子节点放入到的子节点放入到OPEN表的首部。表的首部。v在深度优先搜索中，搜索一旦进入某个分支，就在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。完备的，即使问题有解，它也不一定能求得解。v深度优先搜索本质：以初始节点为根节点，在状深度优先搜索本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索态空间图中按照深度优先的原则，生成一棵搜索树。树。有界深度优先搜索v有界深度优先搜索：有界深度优先搜索：v动动机机：为为了了防防止止搜搜索索过过程程沿沿着着无无益益的的路路径径扩扩展展下下去去，往往往往给给出出一一个个节节点点扩扩展展的的最最大大深深度度，即即深深度度界限。界限。v思思想想：对对状状态态空空间间的的深深度度优优先先搜搜索索引引入入搜搜索索深深度度界界限限，设设为为dmdm，当当搜搜索索深深度度达达到到了了深深度度界界限限而而仍仍未出现目标节点时，就换一个分支进行搜索。未出现目标节点时，就换一个分支进行搜索。有界深度优先搜索八数码难题：八数码难题：dm=4dm=4有界深度优先搜索v有界深度优先搜索：有界深度优先搜索：v问问题题：如如果果问问题题有有解解，且且其其路路径径长长度度 dm dm，则则上上述述搜搜索索过过程程一一定定能能求求得得解解。但但是是，若若解解的的路路径径长长度度 dm,dm,则则上上述述搜搜索索过过程程就就得得不不到到解解。这这说说明明在在有有界界深深度度优优先先搜搜索索中中，深深度度界界限限的的选选择择是是很很重重要要的。的。v要要恰恰当当地地给给出出dmdm的的值值是是比比较较困困难难的的。即即使使能能求求出出解，它也不一定是最优解。解，它也不一定是最优解。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法代价树搜索v代价树：边上标有代价代价树：边上标有代价(或费用或费用)的树称为代价树的树称为代价树v在代价树中，若用在代价树中，若用g(x)g(x)表示从初始节点表示从初始节点S S到节点到节点x x的代价，用的代价，用c(x1,x2)c(x1,x2)表示从父节点表示从父节点x1x1到子节点到子节点x2x2的代价，则有：的代价，则有：vg(x2)=g(x1)+c(x1,x2)g(x2)=g(x1)+c(x1,x2)v代价树搜索：考虑边的代价的搜索方法，代价树代价树搜索：考虑边的代价的搜索方法，代价树搜索的目的是为了找到一条代价最小的解路径。搜索的目的是为了找到一条代价最小的解路径。代价树搜索方法包括：代价树搜索方法包括：v代价树的广度优先搜索代价树的广度优先搜索v代价树的深度优先搜索代价树的深度优先搜索代价树的广度优先搜索v代价树的广度优先搜索代价树的广度优先搜索v基本思想：每次从基本思想：每次从OPENOPEN表中选择节点往表中选择节点往CLOSEDCLOSED表表传送时，总是选择其中代价最小的节点。也就是传送时，总是选择其中代价最小的节点。也就是说，说，OPENOPEN表中的节点在任一时刻都是按其代价从表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大小到大排序的。代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什的节点排在后面，而不管节点在代价树中处于什么位置上。么位置上。v如果问题有解，代价树的广度优先搜索一定可以如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。求得解，并且求出的是最优解。v该算法应用的条件：该算法是针对代价树的算法。该算法应用的条件：该算法是针对代价树的算法。为了采用该算法对图进行搜索，必须先将图转换为了采用该算法对图进行搜索，必须先将图转换为代价树。为代价树。代价树的广度优先搜索v代价树的广度优先搜索算法流程：代价树的广度优先搜索算法流程：v(1)(1)把初始节点把初始节点S S放入放入OPENOPEN表中，置表中，置S S的代价的代价g(S)=0g(S)=0；v(2)(2)如果如果OPENOPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；v(3)(3)把把OPENOPEN表的第一个节点取出放入表的第一个节点取出放入CLOSEDCLOSED表，并表，并记该节点为记该节点为n n；v(4)(4)考察节点考察节点n n是否为目标。若是，则找到了问题是否为目标。若是，则找到了问题的解，成功退出；的解，成功退出；v(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；否则转第步；否则转第(6)(6)步；步；v(6)(6)扩展节点扩展节点n n，为每一个子节点都配置指向父节点，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放的指针，计算各子节点的代价，并将各子节点放入入OPENOPEN表中。并根据各子结点的代价对表中。并根据各子结点的代价对OPENOPEN表中表中的全部结点按由小到大的顺序排序。然后转第的全部结点按由小到大的顺序排序。然后转第(2)(2)步。步。代价树的广度优先搜索v例子：城市交通问题。设有例子：城市交通问题。设有5 5个城市，它们之间的个城市，它们之间的交通线路如下方左图所示，图中的数字表示两个交通线路如下方左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度城市之间的交通费用，即代价。用代价树的广度优先搜索，求从优先搜索，求从A A市出发到市出发到E E市，费用最小的交通市，费用最小的交通路线。路线。ABCDE43 4 523城市交通图城市交通图代价树的广度优先搜索v解：首先将交通图转化为代价树。解：首先将交通图转化为代价树。具体转化方法如下：具体转化方法如下：v从起始节点从起始节点A开始，把与它直接开始，把与它直接相邻的节点作为它的子节点相邻的节点作为它的子节点v对其他节点也做相同的处理对其他节点也做相同的处理v若一个节点已经为某节点的直系若一个节点已经为某节点的直系先辈节点时，就不能作为这个节先辈节点时，就不能作为这个节点的子节点。点的子节点。v图中除了起始节点图中除了起始节点A之外，其它之外，其它节点都可能要在代价树中出现多节点都可能要在代价树中出现多次，为了区分它们的多次出现，次，为了区分它们的多次出现，分别用下标分别用下标1,2，标出标出城市交通图的代价树城市交通图的代价树2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35ABCDE43 4 523代价树的广度优先搜索v解：对此代价树进行广度优先搜索，可得到最优解：对此代价树进行广度优先搜索，可得到最优解，如图红线部分为最优解，其代价为解，如图红线部分为最优解，其代价为8ABCDE43 4 5232 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35代价树的深度优先搜索v代价树的深度优先搜索代价树的深度优先搜索v基本思想：与代价树的广度优先搜索不同，代价基本思想：与代价树的广度优先搜索不同，代价树的深度优先搜索是从刚扩展出的子节点中选择树的深度优先搜索是从刚扩展出的子节点中选择一个代价最小的节点送入一个代价最小的节点送入CLOSED表进行考察，表进行考察，而不是在整个而不是在整个OPEN表中选择代价最小的。表中选择代价最小的。代价树的深度优先搜索v代价树的深度优先搜索算法流程：代价树的深度优先搜索算法流程：v(1)(1)把初始节点把初始节点S S放入放入OPENOPEN表中，置表中，置S S的代价的代价g(S)=0g(S)=0；v(2)(2)如果如果OPENOPEN表为空，则问题无解表为空，则问题无解 ，失败退出；，失败退出；v(3)(3)把把OPENOPEN表的第一个节点取出放入表的第一个节点取出放入CLOSEDCLOSED表，并表，并记该节点为记该节点为n n；v(4)(4)考察节点考察节点n n是否为目标节点。若是，则找到了是否为目标节点。若是，则找到了问题的解，成功退出；问题的解，成功退出；v(5)(5)若节点若节点n n不可扩展，则转第不可扩展，则转第(2)(2)步；步；v(6)(6)扩展节点扩展节点n n，生成其子节点，将这些子节点按，生成其子节点，将这些子节点按边代价由小到大放入边代价由小到大放入OpenOpen表的首部，并为每一个表的首部，并为每一个子节点设置指向父节点的指针。然后转第子节点设置指向父节点的指针。然后转第(2)(2)步。步。状态空间的盲目搜索v状态空间的盲目搜索状态空间的盲目搜索v上述几种搜索方法的本质是，以初始节点为根节上述几种搜索方法的本质是，以初始节点为根节点，按照既定的策略对状态空间图进行遍历，并点，按照既定的策略对状态空间图进行遍历，并希望能够尽早发现目标节点。希望能够尽早发现目标节点。v由于对状态空间图遍历的策略是既定的，因此这由于对状态空间图遍历的策略是既定的，因此这些方法统称为盲目搜索方法。些方法统称为盲目搜索方法。v盲目搜索具有较大的盲目性，产生的无用节点较盲目搜索具有较大的盲目性，产生的无用节点较多，效率不高。多，效率不高。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法启发性信息和估价函数v启发式搜索：采用问题自身的特性信息，以指导启发式搜索：采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。搜索朝着最有希望的方向前进。v启发性信息的概念：启发性信息是指那种与具体启发性信息的概念：启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发信息的启发能有希望方向前进的控制信息。启发信息的启发能力越强，扩展的无用结点越少。力越强，扩展的无用结点越少。v启发性信息的种类启发性信息的种类v有效地帮助确定扩展节点的信息有效地帮助确定扩展节点的信息v有效的帮助决定哪些后继节点应被生成的信息有效的帮助决定哪些后继节点应被生成的信息v能决定在扩展一个节点时哪些节点应从搜索树上能决定在扩展一个节点时哪些节点应从搜索树上删除的信息删除的信息启发性信息和估价函数v估价函数：用于评估节点重要性的函数称为估价估价函数：用于评估节点重要性的函数称为估价函数。估价函数的一般形式为：函数。估价函数的一般形式为：vf(x)=g(x)+h(x)vg(x)表示从初始节点表示从初始节点S0到节点到节点x的代价；的代价；vh(x)是从节点是从节点x到目标节点到目标节点Sg的最优路径的代价的的最优路径的代价的估计，它体现了问题的启发性信息。估计，它体现了问题的启发性信息。vh(x)称为启发函数。称为启发函数。启发性信息和估价函数v例子：八数码难题例子：八数码难题v设问题的初始状态设问题的初始状态S0和目标状态和目标状态Sg如图所示如图所示v估价函数为：估价函数为：v f(n)=d(n)+W(n)vd(n)：表示节点：表示节点n在搜索树中的深在搜索树中的深度度vW(n)：表示节点：表示节点n中中“错放错放”的的棋子个数棋子个数v请计算初始状态请计算初始状态S0的估价函数值的估价函数值f(S0)1238476528314765S0Sg启发性信息和估价函数v计算初始状态计算初始状态S0的估价函数值的估价函数值f(S0)v解：取解：取g(n)=d(n)，h(n)=W(n)v它说明是用从它说明是用从S0到到n的路径上的单的路径上的单位代价表示实际代价位代价表示实际代价v用结点用结点n中中“错放错放”的棋子个数作的棋子个数作为启发信息。为启发信息。v一般来说，某节点中的一般来说，某节点中的“错放错放”的棋子个数越多，说明它离目标的棋子个数越多，说明它离目标节点越远（代价的估计）。节点越远（代价的估计）。v对初始节点对初始节点S0，d(S0)=0，W(S0)=3。因此，。因此，f(S0)=0+3=3 1238476528314765S0Sg状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法A算法vA算法：在图搜索算法中，如果能在搜索的每一步算法：在图搜索算法中，如果能在搜索的每一步都利用估价函数都利用估价函数f(n)=g(n)+h(n)对对OPEN表中的节表中的节点进行排序，则该搜索算法为点进行排序，则该搜索算法为A算法。算法。由于估价由于估价函数中带有问题自身的启发性信息，因此，函数中带有问题自身的启发性信息，因此，A算法算法也被称为启发式搜索算法。也被称为启发式搜索算法。vA算法的类型：可根据搜索过程中选择扩展节点的算法的类型：可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为：范围，将启发式搜索算法分为：v全局择优搜索算法：全局择优搜索算法：从从OPEN表的所有节点中选表的所有节点中选择一个估价函数值最小的一个进行扩展。择一个估价函数值最小的一个进行扩展。v局部择优搜索算法：仅从刚生成的子节点中选择局部择优搜索算法：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。一个估价函数值最小的一个进行扩展。A算法v全局择优搜索算法流程全局择优搜索算法流程v(1)把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。v(2)如果如果OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。v(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出）取出放入放入CLOSED表。表。v(4)考察节点考察节点n是否为目标节点。若是，则求得了是否为目标节点。若是，则求得了问题的解，退出。问题的解，退出。v(5)若节点若节点n不可扩展，则转第不可扩展，则转第2步。步。v(6)扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点计算每个子节点的估价值，并为每一个子节点都配置指向父节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入的指针。把这些子节点都送入OPEN表中，然后表中，然后对对OPEN表中的全部节点按估价值从小至大的顺表中的全部节点按估价值从小至大的顺序进行排序，然后转第序进行排序，然后转第2步。步。A算法v全局择优搜索算法：八数码难题全局择优搜索算法：八数码难题v设问题的初始状态设问题的初始状态S0和目标状态和目标状态Sg如图所示如图所示v估价函数为：估价函数为：v f(n)=d(n)+W(n)vd(n)：表示节点：表示节点n在搜索树中的深在搜索树中的深度度vW(n)：表示节点：表示节点n中中“不在位不在位”的数码个数的数码个数v用全局择优搜索解决该问题用全局择优搜索解决该问题1238476528314765S0Sg启发性信息和估价函数v用全局择优搜索求解八数用全局择优搜索求解八数码难题码难题v解：解：v该问题的全局择优搜索树该问题的全局择优搜索树如右图所示如右图所示v在该图中，每个节点旁边在该图中，每个节点旁边的数字是该节点的估价函的数字是该节点的估价函数值数值v该问题的解为：该问题的解为：v S0S1S2S3SgA算法v局部择优搜索算法流程局部择优搜索算法流程v(1)把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0)。v(2)如果如果OPEN表为空，则问题无解，退出。表为空，则问题无解，退出。v(3)把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出）取出放入放入CLOSED表。表。v(4)考察节点考察节点n是否为目标节点。若是，则求得了是否为目标节点。若是，则求得了问题的解，退出。问题的解，退出。v(5)若节点若节点n不可扩展，则转第不可扩展，则转第2步。步。v(6)扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点计算每个子节点的估价值，并按估价值从小到大的顺序放到的估价值，并按估价值从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第向父节点的指针，然后转第2步。步。状态空间的搜索策略v状态空间的搜索策略状态空间的搜索策略v状态空间搜索的基本思想状态空间搜索的基本思想v图搜索的一般过程图搜索的一般过程v状态空间的盲目搜索状态空间的盲目搜索v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索v代价树搜索代价树搜索v状态空间的启发式搜索状态空间的启发式搜索v启发性信息和估价函数启发性信息和估价函数vA A算法和算法和A*A*算法算法
展开阅读全文