工学状态空间的搜索策略课件

1、搜索策略搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的核心问题之一。第1页，共60页。已提出的搜索策略求任一解路的搜索策略爬山法（Hill Climbing）、深度优先法（Depth-first）、限定范围搜索法（Beam Search）、回溯法（Back-tracking）、最好优先法（Best-first）求最佳解路的搜索策略宽度优先法（Breadth-first）、分枝界限法（Branch and Bound）、动态规划法（Dynamic Programming）、最佳图搜索法（A*）求与或关系解图的搜索法

2、一般的与或图搜索法（AO*）、极大极小法（Minima）、-剪枝法（Alpha-beta Pruning）、启发式剪枝法（Heuristic Pruning）第2页，共60页。搜索策略选取操作算子的方式搜索策略的主要任务是确定选取操作算子的方式。盲目搜索对特定问题不具有任何有关信息，按预定步骤（依次或随机）进行搜索，搜索过程中获得的中间信息不用来改进控制策略。特点：能快速调用操作算子。启发式搜索考虑特定问题领域可应用的启发性信息，动态确定调用操作算子的步骤，指导搜索朝最有希望的方向前进。特点：优先选取合适的操作算子，减少不必要搜索，提高效率 启发式搜索一般优于盲目搜索，但不能过于追求更多的甚至

3、更完整的启发信息。应综合考虑各种因素，尽量使搜索系统的总开销较小。第3页，共60页。搜索策略4.1 状态空间的搜索策略4.2 与/或树的搜索策略第4页，共60页。4.1 状态空间的搜索策略一般搜索过程盲目搜索策略回溯策略、宽度优先搜索（广度优先搜索）、深度优先搜索、代价树的宽度优先搜索、代价树的深度优先搜索启发式搜索策略有序搜索、A*算法第5页，共60页。第6页，共60页。搜索的基本问题是否一定能找到一个解；是否能终止运行或陷入一个死循环；找到的是否是最佳解；时间与空间复杂性如何。第7页，共60页。一般搜索过程的数据结构OPEN：未扩展节点表扩展：用合适算符对一个节点进行操作，生成一组子节点。

4、存放刚生成的节点。不同搜索策略，节点在OPEN表中的排列顺序不同。CLOSED：已扩展节点表存放将扩展或已扩展节点。OPEN表状态节点父节点COLSE表编号状态节点父节点第8页，共60页。一般搜索过程算法流程建立只含有初始节点S的搜索图G，把S放到OPEN表中；建立CLOSED表，其初始值为空表；若OPEN表是空表，则失败退出；选择OPEN表中第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n；若n为目标节点，则有解并成功退出，解是追踪图G中沿指针从n到S这条路径得到（指针在第步中设置）；扩展n，生成不是n的祖先的那些后继节点的集合M，把M的这些成员作为n的后继节点添入图

5、G中；第9页，共60页。一般搜索过程算法流程对M中子节点进行如下处理：对没在G中出现过的（即没在OPEN或CLOSED表中出现过的）M成员设置一个指向n的指针，把M的这些成员加进OPEN表；已在OPEN或CLOSED表中的每个M成员，确定是否需要更改指向n的指针方向；已在CLOSED表中的每个M成员，确定是否需要更改图G中它的每个后裔节点指向父节点的指针。按某种方式或按某个试探值，重排OPEN表；转第步。第10页，共60页。3.1.3 一般搜索过程第11页，共60页。一般搜索过程的几点说明搜索过程具有通用性此后讨论的各种搜索策略都可以看成是它的特例。各种搜索策略的主要区别在于：步骤对OPEN表

6、上的节点进行排序的准则，以便选出一个“最好”的节点作为步骤扩展使用。排序可以是任意的，即肓目的盲目搜索。可以用启发信息为依据启发式搜索。第12页，共60页。一般搜索过程的几点说明搜索图和搜索树图搜索的一般过程中生成的明确图，被称为搜索图G 。由图G中所有节点及反向指针（在第步形成的指向父节点的指针）构成的集合T，是一棵树，称为搜索树。扩展某节点时图G已保存了从初始节点到该节点的搜索树。G中每个节点（S除外）都有且仅有一个指向G中一个父节点的指针。OPEN表上的节点都是搜索图上未被扩展的端节点。CLOSED表上的节点，或者是已被扩展但没有生成后继节点的端节点， 或者是搜索树的非端节点。第13页，

7、共60页。一般搜索过程的几点说明搜索过程终止条件在第步，当被选作扩展的节点是目标节点时，搜索过程成功结束，得到了一个解。从目标节点按指向父节点的指针（第步形成）不断回溯，能重现从初始节点到目标节点的成功路径。解是由从初始节点到该目标节点路径上的算符构成。当搜索树不再有末被扩展的端节点时，即OPEN表为空，搜索过程失败，从初始节点达不到目标节点。第14页，共60页。一般搜索过程的几点说明步骤的说明 一个节点经一个算符操作通常指生成一个子节点。由于适用于一个节点的算符可能有多个，此时就会生成一组子节点。判断子节点是否是当前扩展节点的父节点、祖父节点等，若是，则删除。余下的子节点记做集合M，加入图G

8、中。 扩展节点时，生成该节点的所有后继节点。第15页，共60页。一般搜索过程的几点说明步骤的说明问题：一个新生成的节点，若已作为其他节点的后继节点被生成过，该新节点应作为哪个节点的后继节点？解决方法：一般由初始节点到该节点路径上所付出的代价来决定，那条路经付出的代价小，相应的节点就作为父节点。第16页，共60页。实心圆圈代表已扩展节点，它们位于CLOSED表中；空心圆圈代表未扩展节点，它们位于OPEN表中；有向边旁的箭头是指向父节点的指针。设有向弧两端节点间的代价都为14452435第17页，共60页。常见的几种盲目搜索策略回溯策略宽度优先搜索（广度优先搜索）深度优先搜索代价树的宽度优先搜索代

9、价树的深度优先搜索第18页，共60页。宽度优先搜索基本思想从初始节点开始，逐层对节点进行扩展，并考察它是否为目标节点。在第n层节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。第19页，共60页。宽度优先搜索的数据结构OPEN表包含已生成但子节点未被搜索的节点。表中节点的排列次序就是搜索的次序。OPEN表采用先进先出的队列结构。CLOSED表记录已被生成扩展过的节点。相当于回溯算法中PS表和NSS表的合并。第20页，共60页。宽度优先搜索算法流程把起始节点放到OPEN表中，如果该起始节点为一目标节点，则求得一个解答。若OPEN是空表，则没有解，失败退出；否则继续。把第一个节点（节点n）

10、从OPEN表移出，并把它放入CLOSED的扩展节点表中。扩展n。如果没有后继节点，则转向步骤。把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向步骤；第21页，共60页。3.1.4 盲目搜索策略宽度优先搜索第22页，共60页。宽度优先搜索算法的几点说明删除OPEN或CLOSED表中出现过的子状态，避免循环搜索。只要问题有解，总能找到最短解题路径。如果问题无解，对有限图，算法会失败退出；对无限图，则永远不会终止。第23页，共60页。宽度优先搜索算法的缺陷盲目性较大，当目标节点距初始节点较远，会产生许多无

11、用节点，搜索效率低。因此，当图中分枝数太多，实用意义不大。图中各边代价都相同，都为一个单位量，从而可用路径的长度代替路径的代价。然而，对许多问题这种假设是不现实的，即状态空间中各边的代价不可能完全相同。代价树的宽度优先搜索算法启发式搜索算法第24页，共60页。代价树的宽度优先搜索算法的引入例：城市交通问题。设有5个城市, 它们之间的交通路线如图所示，图中的数字表示两个城市之间的交通费用，即代价。求从A市出发到E市，费用最小的交通路线。结论：在搜索树中给每条边都标上代价。第25页，共60页。生成代价树的方法从初始节点A开始，把与A直接相邻的节点作为子节点。对其他节点作相同处理。若一个节点已是某节

12、点的直系先辈节点，就不能再作为该节点的子节点。除A外，其它节点可能在代价树中多次出现。为便于区分，用下标1, 2, 标出。第26页，共60页。相关记号若节点j是i的子女， c(i, j)：从i到j的连接弧线代价。g(i)：从起始节点S到i的路径代价，即从S到i的最少代价路径上的代价。g(j)=g(i)+c(i, j)第27页，共60页。代价树的宽度优先搜索算法流程把起始节点S放到未扩展节点表OPEN中。如果S为一目标节点，则求得一个解；否则令g(S)=0。如果OPEN是个空表，则没有解，失败退出。把OPEN表中第一个节点n取出，放入CLOSED表。如果n是目标节点，则求得问题的解，退出。若n不

13、可扩展，则转第(2)步。扩展n，将其子节点放入OPEN表，并配置指向父节点的指针；计算各子节点的代价，按代价对OPEN表中全部节点从小到大进行排序，然后转第步。第28页，共60页。代价树的宽度优先搜索示例最优解为：A B1 E1代价为：9OPEN表状态节点AC1B1B1D1D2E1D1E1D1E3C2COLSED表状态节点AC1AB1C1AD2B1C1AE1D2B1C1A第29页，共60页。深度优先搜索的基本思想从初始节点开始，在其子节点中选择一个进行考察，记为子节点n。若n不是目标节点，搜索n所有子节点以及子节点的后裔节点。当到达某个子节点，该子节点既不是目标节点又不能继续扩展，才选择n的兄

14、弟节点进行考察。第30页，共60页。深度与宽度优先搜索的不同宽度深度OPEN表先进先出的队列结构先进后出的堆栈结构最优解总能找到最短解题路径不一定能找到最优解第31页，共60页。深度优先搜索的缺陷及解决方法搜索一旦进入某个分支，就沿着该分支一直向下搜索。如果目标节点不在此分支上，且该分支又是一个无穷分支，则不可能得到解。因此，深度优先搜索是不完备的。为了防止搜索沿着一条路径无限地扩展下去，深度优先搜索常设定深度限制值，即有界深度优先搜索。第32页，共60页。有界深度优先搜索节点深度定义起始节点（即根节点）的深度为0。其他节点的深度等于其父节点的深度加1。深度界限为避免考虑太长路径，防止搜索沿着

15、无益路径扩展，往往给出一个节点扩展的最大深度，称为深度界限。若达到深度界限，对任何节点都认为它们没有后继节点。采用深度界限后，解答路径也不一定是最短路径。第33页，共60页。有界深度优先搜索算法流程把起始节点S放到OPEN表中。如果此节点为目标节点，则得到一个解。如果OPEN为空表，则失败退出。把第一个节点（节点n）从OPEN表移到CLOSED表。如果n的深度等于最大深度dm，则转向步骤。扩展n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向步骤。如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向步骤。第34页，共60页。第35页，共60页。有界深度优先搜

16、索的几点说明如果问题有解，且路径长度dm，则上述搜索过程一定能求得解。但若解的路径长度 dm，则得不到解。为找到最优解，可增设表R，每找到一个目标节点Sg后，就把它放到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。第36页，共60页。代价树的深度优先搜索算法流程把起始节点S放到未扩展节点表OPEN中。如果S为一目标节点，则求得一个解；否则令g(S)=0。如果OPEN是个空表，则没有解，失败退出。把OPEN表中第一个节点n取出，放入CLOSED表。如果n是目标节点，则求得问题的解，退出。若n不可扩展，则转第(2)步。扩展n，将其子节点按边代价从小到大的顺序放入OPEN表，并配置

17、指向父节点的指针，然后转第步。第37页，共60页。代价树的深度优先搜索示例代价树的宽度优先搜索最优解为：A B1 E1代价为：9OPEN表状态节点AC1B1D1B1E2B2B1COLSE表状态节点AC1AD1C1AE2D1C1A代价树的深度优先搜索最优解为：A C1 D1 E2代价为：13第38页，共60页。盲目搜索存在的问题扩展节点数目较多。效率低，耗费过多的计算时间和空间。解决方案：选择最有希望的节点扩展。第39页，共60页。启发式策略的应用场合由于在问题陈述和数据获取方面固有的模糊性，可能使问题没有一个确定解，即它是一个模糊系统。一个问题可能有确定解，但求解过程中的搜索代价太大。 启发搜

18、索通常由两部分组成：启发方法使用该方法搜索状态空间的算法注意：启发式搜索可能得到一个次最佳解，也可能无解，这是由其固有局限性决定的，不能通过“更好”的启发式策略来克服。第40页，共60页。启发信息指导搜索过程，与具体问题求解有关的控制性信息。陈述性更准确精练地描述状态，使状态空间缩小。过程性构造操作算子，使操作算子少而精。控制性：一般被反映在估价函数之中关于控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关知识。第41页，共60页。估价函数f(n) f(n)是从初始节点经过节点n到达目标节点的路径的最小代价估计值，其一般形式是：f(n)=g(n)+h(

19、n)g(n)：从初始节点到n的实际代价；g(n)在f(n)所占比重较大，越倾向于宽度优先搜索方式，它有利于搜索完备性，但影响搜索效率。h(n)：启发函数从n到目标节点的最佳路径的估计代价。h(n)的比重越大，表示启发性能越强第42页，共60页。估价函数的选择一个节点处在最佳路径上的概率。求出任意一个节点与目标节点集之间的距离度量或差异度量。根据格局（如博弈问题）或状态的特点来计算。第43页，共60页。启发式与宽度/深度优先搜索的异同相同处都使用了两张表来记录状态信息。OPEN表中保留所有已生成而未扩展的节点；CLOSED表中记录已扩展过的节点。不同处：启发式：OPEN表按节点的启发估价函数值的

20、大小排列，深度/宽度：队列或堆栈的数据结构。第44页，共60页。有序搜索算法（ A算法）的基本思想 应用某个算法选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，这种搜索方法叫做有序搜索（最佳优先搜索）。 有序搜索总是选择最有希望的节点作为下一个要扩展的节点。第45页，共60页。有序搜索算法流程把起始节点S放到OPEN表中，计算f(S)，并把值与S联系起来。如果OPEN表是个空表，则失败退出，无解。从OPEN表中选择一个f值最小的节点i。如果有多个节点满足这一要求，且其中有一个为目标节点，则选择它作为i ；否则就选择其中任意一个节点作为i。把i 从OPEN表中移出，并放入CLOSED表

21、中。如果i是个目标节点，则成功退出，求得一个解。第46页，共60页。有序搜索算法流程扩展i，生成其全部后继节点。对i的每个后继节点j：a) 计算f(j)。b) 如果j不在OPEN和CLOSED表中，则用f(j)把它添入OPEN表，并为j设置指向i的指针。c) 若j已在OPEN或CLOSED表上，则比较f(j)和前面计算过的该节点在表中的f(j)old值。若f(j)较小，则：I. 以f(j) 取代f(j)old。II. 修正j的父指针，使其指向i。III. 若j在CLOSED表中，把它移回OPEN表。转向。第47页，共60页。有序搜索算法的几点说明宽度优先算法搜索是它的特例，此时f(i)为节点i

22、的深度。f(i)定义为从起始节点至i的代价，则退化为代价树的宽度优先搜索。f的选择直接决定了有序搜索中被扩展节点的数目，即直接影响了搜索算法效率，对搜索结果具有决定性作用。第48页，共60页。A*算法中的估价函数定义f*(n) = g*(n) + h*(n)：称为从节点n到目标节点的最小代价。g*(n) = k(S, n)：从初始节点S到节点n的最小代价。k(ni, nj)：表示任意两个节点ni和nj之间最小代价路径的实际代价（对于两节点间没有通路的节点，函数k没有定义）。h*(n)：表示整个目标节点集合ti上所有k(n, ti)中最小的一个, 即从节点n 到目标节点最优路径的实际代价。第49

23、页，共60页。A*算法定义：在A算法中，如果对所有的n存在h(n)h*(n)，则称h(n)为h*(n)的下界。A*算法： 在A算法，采用h*(n)的下界h(n)为启发函数，即对任意的节点n均有：h(n)h*(n)，且g(n)是对g*(n)的估计， g(n)0，则算法成为A*算法。第50页，共60页。A*算法流程把S放入OPEN表，记f =h，令CLOSED为空表。重复下列过程，直至找到目标节点为止。若OPEN表为空，则失败退出。选取OPEN表中未设置过的具有最小f值的节点为最佳节点BESTNODE，并把它放入CLOSED表。若BESTNODE为目标节点，则成功求解。若BESTNODE不是目标节点，则扩展产生后继节点SUCCESSOR。对每个SUCCESSOR进行下列过程：第51页，共60页。3.1.5.3 A*算法a) 建立从SUCCESSOR返回BESTNODE的指针。b) 计算g(SUC)=g(BES) + k(BES, SUC)。c) 如果SUCCESSOROPEN，则称此节点为OLD，把它添至BESTNODE的后继节点表中。d) 比较新旧路径代价。若g(SUC)g(OLD)，则重新确定OLD的父亲节点为BESTNODE，记下较小代价