[工学]状态空间的搜索策略

《[工学]状态空间的搜索策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、因素，尽量使搜索系统的总开销较小。搜索策略4.1状态空间的搜索策略4.2与/或树的搜索策略4.1状态空间的搜索策略一般搜索过程盲目搜索策略回溯策略、宽度优先搜索（广度优先搜索）、深度优先搜索、代价树的宽度优先搜索、代价树的深度优先搜索启发式搜索策略有序搜索、A*算法搜索的基本问题是否一定能找到一个解；是否能终止运行或陷入一个死循环；找到的是否是最佳解；时间与空间复杂性如何。一般搜索过程的数据结构OPEN：未扩展节点表扩展：用合适算符对一个节点进行操作，生成一组子节点。存放刚生成的节点。不同搜索策略，节点在OPEN表中的排列顺序不同。CLOSED：已扩展节点表存放将扩展或已扩展节点。OP

4、EN表状态节点父节点COLSE表编号状态节点父节点一般搜索过程算法流程建立只含有初始节点S的搜索图G，把S放到OPEN表中；建立CLOSED表，其初始值为空表；若OPEN表是空表，则失败退出；选择OPEN表中第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n；若n为目标节点，则有解并成功退出，解是追踪图G中沿指针从n到S这条路径得到（指针在第⑦步中设置）；扩展n，生成不是n的祖先的那些后继节点的集合M，把M的这些成员作为n的后继节点添入图G中；一般搜索过程算法流程对M中子节点进行如下处理：对没在G中出现过的（即没在OPEN或CLOSED表中出现过的）M成员设置一个

5、指向n的指针，把M的这些成员加进OPEN表；已在OPEN或CLOSED表中的每个M成员，确定是否需要更改指向n的指针方向；已在CLOSED表中的每个M成员，确定是否需要更改图G中它的每个后裔节点指向父节点的指针。按某种方式或按某个试探值，重排OPEN表；转第③步。3.1.3一般搜索过程一般搜索过程的几点说明搜索过程具有通用性此后讨论的各种搜索策略都可以看成是它的特例。各种搜索策略的主要区别在于：步骤⑧对OPEN表上的节点进行排序的准则，以便选出一个“最好”的节点作为步骤④扩展使用。排序可以是任意的，即肓目的——盲目搜索。可以用启发信息为依据——启发式搜索。一般搜索过程的几点说明搜索图和

6、搜索树图搜索的一般过程中生成的明确图，被称为搜索图G。由图G中所有节点及反向指针（在第⑦步形成的指向父节点的指针）构成的集合T，是一棵树，称为搜索树。扩展某节点时图G已保存了从初始节点到该节点的搜索树。G中每个节点（S除外）都有且仅有一个指向G中一个父节点的指针。OPEN表上的节点都是搜索图上未被扩展的端节点。CLOSED表上的节点，或者是已被扩展但没有生成后继节点的端节点，或者是搜索树的非端节点。一般搜索过程的几点说明搜索过程终止条件在第⑤步，当被选作扩展的节点是目标节点时，搜索过程成功结束，得到了一个解。从目标节点按指向父节点的指针（第⑦步形成）不断回溯，能重现从初始节点到目标节点

7、的成功路径。解是由从初始节点到该目标节点路径上的算符构成。当搜索树不再有末被扩展的端节点时，即OPEN表为空，搜索过程失败，从初始节点达不到目标节点。一般搜索过程的几点说明步骤⑥的说明一个节点经一个算符操作通常指生成一个子节点。由于适用于一个节点的算符可能有多个，此时就会生成一组子节点。判断子节点是否是当前扩展节点的父节点、祖父节点等，若是，则删除。余下的子节点记做集合M，加入图G中。扩展节点时，生成该节点的所有后继节点。一般搜索过程的几点说明