人工智能基础（第2版）-高济-AI-4-本.pptVIP

人工智能基础 浙江大学计算机学院 高 济 2.2.2 与或图搜索 与或图视为对一般图(或图)的扩展； 与或图也有根节点，用于指示初始状态； 同父子节点间可以存在“与”关系，父、 子节点间不能简单地以弧线关联，需要 引入超连接概念； 解答路径往往不复存在，代之以广义的 解路径——解图。 与或图搜索的基本概念： 参见图2.19 K-连接——表示从父节点到子节点间的连接： 也称为父节点的外向连接， 以园弧指示同父子节点间的“与”关系， K为这些子节点的个数，K1时成为超连接， 一个父节点可以有多个外向的K-连接。 当所有超连接的K都等于1时，与或图蜕化为一般图。 2.2.2 与或图搜索 根、叶、终节点 无父节点的节点——根节点，用于指示问题的初始状态； 无子节点的节点——叶节点。 用于联合表示目标状态的节点——终节点， 终节点必定是叶节点，反之不然； 解图的生成——自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。 解图纯粹是一种“与”图； 搜索到多个解图（图2.20），由于与或图中存在“或”关系； 解图应无环，即任何节点的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环。 2.2.2 与或图搜索 2.2.3 与或图的启发式搜索 需求分析 引入应用领域的启发式知识去引导搜索过程， 与或图中搜索的是解图， 估算评价函数f(n)的第1分量g(n)没有意义，只须估算第2分量h(n)， h(n)是对最小解图代价的估计， 会同时出现多个候选的待扩展局部解图， 选择一个可能代价最小的用于下一步搜索。 解图代价的递归方式估算， 父节点n的由外向K-连接指向的子节点：n1，n2，…nk f(n) = K + h(n1) + h(n2) + … + h(nk) 比直接基于h(n)估算而得出的f(n)值更为准确。 如此，可以计算出更为准确的f(n0),即整个局部解图的可能代价。 2.2.3 与或图的启发式搜索1与或图的启发式搜索算法AO* w 参数 G——指示搜索图， G’——指示被选中的待扩展局部解图， LGS——指示候选的待扩展局部解图集， n0——指示根节点，即初始状态节点， n——指示被选中的待扩展节点， fi(n0)——是第i个候选的待扩展局部解图的可能代价。 w 算法的执行划分为二个阶段： 初始化——建立只包括初始状态节点的搜索图； 搜索循环——选择和扩展局部解图，精化解图代价的估计，传递节点的能解性。 1 与或图的启发式搜索算法AO* w 算法 （1）G := n0，LGS为空集； （2）若n0 是终节点，则标记 n0为能解节点；否则计算f(n0) = h(n0), 并把G作为0号候选局部解图加进LGS； （3）n0 标记为能解节点，则算法成功返回； （4）若LGS为空集，则搜索失败返回；否则从LGS选择fi(n0)最小的待扩展局部解图作为G’； （5）G’中选择一个非终节点的外端节点（尚未用于扩展出子节点的节点）作为n； （6）扩展n，生成其子节点集，并从中删去导致有环的子节点以及和它们有“与”关系的子节点；若子节点集为空，则n是不能解节点，从LGS删去G’(因为G’不可能再扩展为解图)；否则，计算每个子节点 ni的f(ni),并通过建立外向K-连接将所有子节点加到G中； （7）若存在j个（j1）外向K-连接, 则从LGS删去G’，并将j个新局部解图加进LGS； （8）G’中或在取代G’的j个新局部解图中用公式f(n) = K + h(n1) + h(n2) + … + h(nk)的计算结果取代原先的f(n)，并传递这种精化的作用到fi(n0)（i = 1, 2, …, j）；同时将作为终节点的子节点标记为能解节点，并传递节点的能解性。 （9）返回语句（3）。 与或图的启发式搜索算法AO* 2.2.3 与或图的启发式搜索2 算法应用的若干问题 从局部解图中选择加以扩展的节点 与或图搜索的是解图而非解路径， 选择f(n) = h(n)的值最小的节点加以扩展并不一定会加速搜索过程， 应选择导致解图代价发生较大变化的节点优先加以扩展， 使搜索的注意力快速地聚焦到实际代价较小的候选解图上。 简单情况下，可随机选择加以扩展的节点。 AO*算法的可采纳性 AO*算法是可采纳的——当某与或图存在解图时，应用AO*算法一定能找出代价最小的解图。 AO*算法的应用要求遵从的约束： 总能满足h(n) ≤ h*(n), h*(n)是实际的代价最小解图找到时解图的代价， 确保h(n)满足单调限制条件: h(n) ≤ K + h(n1) + h(n2) + … + h(nk)，粗略的估计总是不超过细致的计算。 2