人工智能ch3 盲目搜索

第3章盲目搜索3.1一般搜索过程3.2回溯策略3.3宽度(广度)优先搜索3.4代价树的宽度优先搜索3.5深度优先搜索1参考教材M.TimJones著,黄厚宽等译.人工智能,电子工业出版社,2010年7月.第3章盲目搜索搜索、推理与人工智能 搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与运行效率，尼尔逊把它列为人工智能研究中的核心问题之一。搜索的基本问题：是否一定能找到一个解；是否能终止运行或陷入一个死循环；找到的是否是最佳解；时间与空间复杂性如何。第3章盲目搜索已提出的搜索策略求任一解路的搜索策略爬山法、深度优先法、限定范围搜索法、回溯法、最好优先法……求最佳解路的搜索策略宽度优先法、分枝界限法、动态规划法、最佳图搜索法（A*）……求与或关系解图的搜索法一般与或图搜索法、极大极小法、-剪枝法、启发式剪枝法……第3章盲目搜索搜索策略选取操作算子的方式盲目搜索对特定问题不具有任何有关信息，按预定步骤（依次或随机）进行搜索，搜索过程中获得的中间信息不用来改进控制策略。特点：能快速调用操作算子。启发式搜索考虑特定问题领域可应用的启发性信息，动态确定调用操作算子的步骤，指导搜索朝最有希望的方向前进。特点：优先选取合适的操作算子，减少不必要搜索，提高效率启发式一般优于盲目搜索，但不能过于追求更多甚至更完整的启发信息。应综合考虑，尽量使搜索系统的总开销较小。第3章盲目搜索3.1一般搜索过程一、数据结构OPEN：未扩展节点表扩展：用合适算符对一个节点进行操作，生成一组子节点。存放刚生成的节点。不同搜索策略，节点在OPEN表中的排列顺序不同。CLOSED：已扩展节点表存放将扩展或已扩展节点。OPEN表状态节点父节点COLSE表编号状态节点父节点3.1一般搜索过程3.1.3一般搜索过程3.1一般搜索过程二、算法流程建立只含有初始节点S的搜索图G，把S放到OPEN表中；建立CLOSED表，其初始值为空表；若OPEN表是空表，则失败退出；选择OPEN表中第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n；若n为目标节点，则有解并成功退出，解是追踪图G中沿指针从n到S这条路径得到（指针在第⑦步中设置）；扩展n，生成不是n的祖先的那些后继节点的集合M，把M的这些成员作为n的后继节点添入图G中；3.1一般搜索过程二、算法流程对M中子节点进行如下处理：对没在G中出现过的（即没在OPEN或CLOSED表中出现过的）M成员设置一个指向n的指针，把M的这些成员加进OPEN表；已在OPEN或CLOSED表中的每个M成员，确定是否需要更改指向n的指针方向；已在CLOSED表中的每个M成员，确定是否需要更改图G中它的每个后裔节点指向父节点的指针。按某种方式或按某个试探值，重排OPEN表；转第③步。3.1一般搜索过程三、几点说明搜索过程具有通用性此后讨论的各种搜索策略都可以看成是它的特例。各种搜索策略的主要区别在于：步骤⑧对OPEN表上的节点进行排序的准则，以便选出一个“最好”的节点作为步骤④扩展使用。排序是任意的，即肓目的——盲目搜索。排序用启发信息为依据——启发式搜索。3.1一般搜索过程三、几点说明搜索图和搜索树图搜索的一般过程中生成的明确图，被称为搜索图G

。由图G中所有节点及反向指针（在第⑦步形成的指向父节点的指针）构成的集合T，是一棵树，称为搜索树。扩展某节点时图G已保存了从初始节点到该节点的搜索树。G中每个节点（S除外）有且仅有一个指向G中一个父节点的指针。OPEN表中节点都是搜索图上未被扩展的端节点。CLOSED表中节点，是已被扩展但没有生成后继节点的端节点，或是搜索树的非端节点。3.1一般搜索过程三、几点说明搜索过程终止条件有解：在第⑤步，当被选作扩展的节点是目标节点时，搜索过程成功结束，得到了一个解。从目标节点按指向父节点的指针（第⑦步形成）不断回溯，能重现从初始节点到目标节点的成功路径。解是由从初始节点到该目标节点路径上的算符构成。无解：当搜索树不再有末被扩展的端节点时，即OPEN表为空，搜索过程失败，从初始节点达不到目标节点。3.1一般搜索过程三、几点说明步骤⑥的说明一个节点经一个算符操作通常指生成一个子节点。由于适用于一个节点的算符可能有多个，此时就会生成一组子节点。判断子节点是否是当前扩展节点的父节点、祖父节点等，若是，则删除。余下的子节点记做集合M，加入图G中。

扩展节点时，生成该节点的所有后继节点。3.1一般搜索过程三、几点说明步骤⑦的说明问题：一个新生成的节点，若已作为其他节点的后继节点被生成过，该新节点应作为哪个节点的后继节点？解决方法：一般由初始节点到该节点路径上所付出的代价来决定，那条路经付出的代价小，相应的节点就作为父节点。3.1一般搜索过程实心圆圈代表已扩展节点，它们位于CLOSED表中；空心圆圈代表未扩展节点，它们位于OPEN表中；有向边旁的箭头是指向父节点的指针。设有向弧两端节点间的代价都为144524353.1一般搜索过程3.2回溯策略基本思想：从初始节点出发，不停地、试探性地寻找路径直到到达目标节点或“不可解节点”为止。当遇到不可解节点时，就回溯到路径中最近的父节点上，查看该节点是否还有其他的子节点未被扩展。如有，则沿这些子节点继续搜索。如找到目标，就成功地退出搜索，返回解题路径。3.2回溯策略回溯策略示例1A2B5F6G7H8I9J3C4D3.2回溯策略回溯策略的数据结构PS（PathStates）表——保存当前搜索路径上的节点若找到目标节点，PS就是解题路径上的节点有序集。NPS（NewPathStates）表——新路径表包含待搜索节点，其后裔节点还未被搜索，即未被扩展。NPS可使算法回溯到其中任一节点；NSS（NoSolvableStates）表——不可解节点表列出找不到解题路径的节点。如果在搜索中，扩展出的节点包含在NSS中，则立即将它排除，不需要沿着该节点继续搜索。NSS可避免算法重新搜索无解的路径。——Open表Close表3.2回溯策略回溯策略示例CSPSNPSNSS0AAA1BBABEFA2CCBACDBEFA3DDBADBEFAC4EEAEFABDC5FFAFAEBDC6GGFAGHIFAEBDC7HHFAHIFAGEDBC1A2B5E6F7G8H9I3C4D3.2回溯策略回溯策略的伪代码procedurebreadth_first_searchbeginPS:=[Start]；NPS:=[Start]；NSS:=[]；CS:=Start；*初始化whileNPS[]dobeginifCS=目标节点thenreturn(PS)ifCS没有子节点(不包括PS，NPS，NSS中已有节点)thenbeginwhile((PS非空)and(CS=PS中第一个元素))dobegin将CS加入到NSS*标明此*节点不可解从CS中删除第一个元素CS*回溯从NPS中删去第一个元素CSCS:=NPS中第一个元素；end将CS加入PS；endendelsebegin将CS子节点(不包括PS、NPS和NSS中已有的)加入到NPS；CS:=NPS中第一个元素；将CS加入到PS；endruturnFAIL；endendend3.2回溯策略回溯策略的几点说明各种合适的推理规则或其他问题求解操作都可以应用于PS，得到一些新的子节点有序集；为避免死循环，若有序集中的子节点已在3张表的任一表中，说明它已被搜索过，不需要再考虑；有序集中的第一个子节点作为CS（当前正在被检测的节点），并加入到PS中；有序集中其余子节点按顺序放入NPS，用于以后搜索；如应用后，CS无子节点，从PS、NPS中删除它，并将它加入到NSS中，之后回溯查找NPS中表首位置的节点。3.2回溯策略3.3宽度优先搜索基本思想：从初始节点开始，逐层对节点进行扩展，并考察它是否为目标节点。在第n层节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。3.3宽度优先搜索一、数据结构OPEN表包含已生成但子节点未被搜索的节点。表中节点的排列次序就是搜索的次序。OPEN表采用先进先出的队列结构。CLOSED表记录已被生成扩展过的节点。相当于回溯算法中PS表和NSS表的合并。3.3宽度优先搜索二、算法流程把起始节点放到OPEN表中，如果该起始节点为一目标节点，则求得一个解答。若OPEN是空表，则没有解，失败退出；否则继续。把第一个节点（节点n）从OPEN表移出，并把它放入CLOSED的扩展节点表中。扩展n。如果没有后继节点，则转向步骤②。把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向步骤②；3.3宽度优先搜索四、几点说明删除OPEN或CLOSED表中出现过的子状态，避免循环搜索。只要问题有解，总能找到最短解题路径。如果问题无解，对有限图，算法会失败退出；对无限图，则永远不会终止。3.3宽度优先搜索五、算法的缺陷盲目性较大，当目标节点距初始节点较远，会产生许多无用节点，搜索效率低。因此，当图中分枝数太多，实用意义不大。图中各边代价都相同，都为一个单位量，从而可用路径的长度代替路径的代价。然而，对许多问题这种假设是不现实的，即状态空间中各边的代价不可能完全相同。代价树的宽度优先搜索算法启发式搜索算法3.3宽度优先搜索3.4代价树的宽度优先搜索算法例：城市交通问题。设有5个城市,它们之间的交通路线如图所示，图中的数字表示两个城市之间的交通费用，即代价。求从A市出发到E市，费用最小的交通路线。结论：在搜索树中给每条边都标上代价。3.4代价树的宽度优先搜索一、代价树生成方法从初始节点A开始，把与A直接相邻的节点作为子节点。对其他节点作相同处理。若一个节点已是某节点的直系先辈节点，就不能再作为该节点的子节点。除A外，其它节点可能在代价树中多次出现。为便于区分，用下标1,2,……标出。3.4代价树的宽度优先搜索二、代价的定义若节点j是i的子女，

c(i,j)：从i到j的连接弧线代价。g(i)：从起始节点S到i的路径代价，即从S到i的最少代价路径上的代价。g(j)=g(i)+c(i,j)3.4代价树的宽度优先搜索三、算法流程把起始节点S放到未扩展节点表OPEN中。如果S为一目标节点，则求得一个解；否则令g(S)=0。如果OPEN是个空表，则没有解，失败退出。把OPEN表中第一个节点n取出，放入CLOSED表。如果n是目标节点，则求得问题的解，退出。若n不可扩展，则转第(2)步。扩展n，将其子节点放入OPEN表，并配置指向父节点的指针；计算各子节点的代价，按代价对OPEN表中全部节点从小到大进行排序，然后转第②步。3.4代价树的宽度优先搜索四、示例最优解为：AB1E1代价为：9OPEN表状态节点AC1B1B1D1D2E1D1E1D1E3C2COLSED表状态节点AC1AB1C1AD2B1C1AE1D2B1C1A3.4代价树的宽度优先搜索3.5深度优先搜索从初始节点开始，在其子节点中选择一个进行考察，记为子节点n。若n不是目标节点，搜索n所有子节点以及子节点的后裔节点。当到达某个子节点，该子节点既不是目标节点又不能继续扩展，才选择n的兄弟节点进行考察。3.5深度优先搜索一、两种算法比较深度与宽度优先搜索的不同宽度深度OPEN表先进先出的队列结构先进后出的堆栈结构最优解总能找到最短解题路径不一定能找到最优解3.5深度优先搜索二、算法缺陷和解决方法缺陷：搜索一旦进入某个分支，就沿着该分支一直向下搜索。如果目标节点不在此分支上，且该分支又是一个无穷分支，则不可能得到解。因此，深度优先搜索是不完备的。解决方法：为防止搜索沿一条路径无限扩展，深度优先搜索常设定深度限制值，即有界深度优先搜索。3.5深度优先搜索三、有界深度优先搜索节点深度定义起始节点的深度为0。其他节点的深度等于其父节点的深度加1。深度界限为避免考虑太长路径，防止搜索沿着无益路径扩展，往往给出一个节点扩展的最大深度，称为深度界限。若达到深度界限，对任何节点都认为它们没有后继节点。采用深度界限后，解答路径也不一定是最短路径。3.5深度优先搜索三、有界深度优先搜索算法流程：把起始节点S放到OPEN表中。如果此节点为目标节点，则得到一个解