图搜索与问题求解

第3章图搜索与问题求解 2020 4 17 人工智能 2 推理与搜索 图搜索技术是人工智能的核心技术之一 任一搜索过程也都是一个推理过程 隐式图的搜索过程是一种利用局部性知识构造全局性答案的过程 在各种搜索过程中 人工智能最感兴趣的是那些具有很强选择性的启发式方法 即那些利用很局部的状态空间可以有效地找到问题的解的方法 机器学习等很多过程都是在假设空间中搜索目标的过程 2020 4 17 人工智能 3 第3章图搜索与问题求解 3 1状态图知识表示 状态图搜索问题求解 3 2状态图搜索3 3与或图知识表示 与或图搜索问题求解 3 4与或图搜索3 5博弈树搜索 2020 4 17 人工智能 4 3 1状态图知识表示 3 1 1状态 操作和状态空间3 1 2修道士和野人的状态空间3 1 3梵塔问题的状态空间3 1 4重排九宫问题和隐式图3 1 5问题求解的基本框架 2020 4 17 人工智能 5 3 1 1状态 操作和状态空间 1 例3 1走迷宫 走迷宫问题就是从该有向图的初始节点出发 寻找目标节点的问题 或者是寻找通向目标节点的路径问题 2020 4 17 人工智能 6 3 1 1状态 操作和状态空间 2 例3 2八数码难题 重排九宫问题 初始棋局 目标棋局 以上两个问题抽象来看 都是某个有向图中寻找目标或路径的问题 在人工智能技术中 把这种描述问题的有向图称为状态空间图 简称状态图 棋局作为节点 相邻节点通过移动数码一个一个产生出来 所有节点由它们的相邻关系连成一个有向图 2020 4 17 人工智能 7 3 1 1状态 操作和状态空间 3 状态 State p62为了描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量q的有序组合 表征了问题的特征和结构 表示成矢量形式 状态在状态图中表示为节点 2020 4 17 人工智能 8 3 1 1状态 操作和状态空间 4 状态转换规则 操作operator 引起状态中某些分量发生改变 从而使一个具体状态变化到另一个具体状态的作用 它可以是一个机械性的步骤 过程 规则或算子 操作描述了状态之间的关系 状态转换规则在状态图中表示为边 在程序中状态转换规则可用数据对 条件语句 规则 函数 过程等表示 2020 4 17 人工智能 9 3 1 1状态 操作和状态空间 5 状态空间 StateSpace 问题的状态空间是一个表示该问题全部的可能状态及相互关系的图 状态空间一般用赋值有向图表示 记为 S F G S 问题的可能有的初始状态的集合 F 操作的集合 G 目标状态的集合 2020 4 17 人工智能 10 3 1 1状态 操作和状态空间 6 状态空间中问题求解在状态空间表示法中 问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题 也就是寻找操作序列的问题 状态空间的解为三元组Qs 某个初始状态Qg 某个目标状态a 把Qs变换成Qg的有限的操作序列状态转换图 2020 4 17 人工智能 11 3 1 1状态 操作和状态空间 7 例3 7迷宫问题的状态图表示 S So F So S4 S4 So S4 S1 S1 S4 S1 S2 S2 S1 S2 S3 S3 S2 S4 S7 S7 S4 S4 S5 S5 S4 S5 S6 S6 S5 S5 S8 S8 S5 S8 S9 S9 S8 S9 Sg G Sg 迷宫问题规则集描述了图中所有节点和边 类似于这样罗列出全部节点和边的状态图称为显式状态图 或者说状态图的显式表示 2020 4 17 人工智能 12 3 1 1状态 操作和状态空间 8 补充例1三枚钱币 能否从下面状态翻动三次后出现全正或全反状态 反 正 反 正 正 正 反 反 反 初始状态 s 目标状态集合 0 7 2020 4 17 人工智能 13 3 1 1状态 操作和状态空间 9 引入一个三元组 q0 q1 q2 来描述总状态 钱币正面为0 反面为1 全部可能的状态为 Q0 0 0 0 Q1 0 0 1 Q2 0 1 0 Q3 0 1 1 Q4 1 0 0 Q5 1 0 1 Q6 1 1 0 Q7 1 1 1 翻动钱币的操作抽象为改变上述状态的算子 即F a b c a 把钱币q0翻转一次b 把钱币q1翻转一次c 把钱币q2翻转一次问题的状态空间为 2020 4 17 人工智能 14 3 1 1状态 操作和状态空间 10 状态空间图 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 a c a b a c a b c b b c 2020 4 17 人工智能 15 3 1 2修道士和野人问题的状态空间 1 补充例2修道士和野人问题 在河的左岸有三个修道士 三个野人和一条船 修道士们想用这条船将所有的人都运过河去 但受到以下条件的限制 1 修道士和野人都会划船 但船一次最多只能运两个人 2 在任何岸边野人数目都不得超过修道士 否则修道士就会被野人吃掉 假定野人会服从任何一种过河安排 试规划出一种确保修道士安全过河方案 2020 4 17 人工智能 16 3 1 2修道士和野人问题的状态空间 2 解 先建立问题的状态空间 问题的状态可以用一个三元数组来描述 S m c b m 左岸的修道士数c 左岸的野人数b 左岸的船数右岸的状态不必标出 因为 右岸的修道士数m 3 m右岸的野人数c 3 c右岸的船数b 1 b 2020 4 17 人工智能 17 3 1 2修道士和野人问题的状态空间 3 2020 4 17 人工智能 18 3 1 2修道士和野人问题的状态空间 4 操作集F p01 p10 p11 p02 p20 q01 q10 q11 q02 q20 2020 4 17 人工智能 19 3 1 2修道士和野人问题的状态空间 5 2020 4 17 人工智能 20 3 1 3梵塔问题的状态空间 1 例3 9二阶梵塔问题一号杆有A B两个金盘 A小于B 要求将AB移至三号杆 每次只可移动一个盘子 任何时刻B不能在A上 用二元组 SA SB 表示状态 SA表示A所在杆号 SB表示B所在杆号 全部状态如下 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 2020 4 17 人工智能 21 3 1 3梵塔问题的状态空间 2 B A A A A A B A B B B B B 2020 4 17 人工智能 22 3 1 3梵塔问题的状态空间 3 转换规则 A i j 表示金盘A从第i号杆移到j号杆B i j 表示金盘B从第i号杆移到j号杆A 1 2 A 1 3 A 2 1 A 2 3 A 3 1 A 3 2 B 1 2 B 1 3 B 2 1 B 2 3 B 3 1 B 3 2 初始状态 1 1 目标状态 3 3 梵塔问题用状态图表示为 2020 4 17 人工智能 23 3 1 3梵塔问题的状态空间 4 1 1 2 1 3 1 2 3 3 3 1 3 3 2 1 2 2 2 A 1 3 A 2 1 B 3 1 A 3 2 A 1 3 B 1 3 A 2 1 B 1 2 A 3 2 2020 4 17 人工智能 24 n n 3 阶梵塔问题 假设金片Pk从小片到大片按下标k顺序编号 即k 1 2 3 n n阶梵塔问题状态空间可用矢量表示为 P1 P2 P3 Pk Pn Pk表示第k个金片穿在编号为Pk的宝石针上 Pk 1 2 3 初始状态S0 1 1 1 1 1 目标状态Sg1 2 2 2 2 2 Sg2 3 3 3 3 3 2020 4 17 人工智能 25 n n 3 阶梵塔问题 n阶梵塔问题的操作集合表示为 F Rk i j i j 1 2 3 k 1 2 n 全部可能状态数为3n个 最佳解长度为2n 1 三阶梵塔问题状态图 S0 1 1 1 Sg2 3 3 3 Sg1 2 2 2 2020 4 17 人工智能 26 3 1 4重排九宫问题和隐式图 1 例3 8重排九宫问题 八数码难题 将棋局用向量A X0 X1 X2 X3 X4 X5 X6 X7 X8 表示 其中Xi为变量 值表示方格Xi内的数字 初始状态S0 0 2 8 3 4 5 6 7 1 目标状态Sg 0 1 2 3 4 5 6 7 8 数码的移动规则就是该问题的状态变化规则 经分析 该问题共有24条规则 分为9组 初始棋局 目标棋局 2020 4 17 人工智能 27 3 1 4重排九宫问题和隐式图 2 0组规则r1 X0 0 X2 n X0 n X2 0 r2 X0 0 X4 n X0 n X4 0 r3 X0 0 X6 n X0 n X6 0 r4 X0 0 X8 n X0 n X8 0 1组规则r5 X1 0 X2 n X1 n X2 0 r6 X1 0 X8 n X1 n X8 0 8组规则 r22 X8 0 X1 n X8 n X1 0 r23 X8 0 X0 n X8 n X0 0 r24 X8 0 X7 n X8 n X7 0 2020 4 17 人工智能 28 3 1 4重排九宫问题和隐式图 3 八数码的状态图可表示为 S0 r1 r2 r24 Sg 八数码问题状态图仅给出了初始节点和目标节点 其余节点需用状态转换规则来产生 类似于这样表示的状态图称为隐式状态图 或者说状态图的隐式表示 2020 4 17 人工智能 29 3 1 4重排九宫问题和隐式图 4 如何隐式的描述一个状态空间有描述问题状态的有关知识 包括该问题的各状态分量的取值情况 开始条件 结束条件 各种约束条件等等 需要由任何一个状态生成其所有直接后继节点的的有关知识 2020 4 17 人工智能 30 3 1 4重排九宫问题和隐式图 5 例3 10旅行商问题 Traveling SalesmanProblem 简称TSP 设有n个互相可直达的城市 某推销商准备从其中的A城出发 周游各城市一遍 最后又回到A城 要求为该推销商规划一条最短的旅行路线 该问题的状态为以A打头的已访问过的城市序列 A S0 A Sg A A 其中 为其余n 1个城市的一个序列 状态转换规则 规则1如果当前城市的下一个城市还未去过 则去该城市 并把该城市名排在已去过的城市名序列后端 规则2如果所有城市都去过一次 则从当前城市返回A城 把A也添在去过的城市名序列后端 2020 4 17 人工智能 31 3 1 5问题求解的基本框架 1 问题求解所需要的知识与描述问题的状态有关的各种叙述性知识 描述状态之间的变换关系的各种过程性知识 一般以一组操作的形式出现的 任何一个操作都含有条件和动作两部分 条件给定了操作的适用范围 动作描述了由于操作而引起的状态中某些分量的变化情形 描述如何根据当前状态和目标状态选择合适的操作的控制性知识 根据叙述性和过程性知识可以构造问题的状态空间 一般讲状态空间是一个赋值有向图 节点对应着问题的状态 边对应操作 2020 4 17 人工智能 32 3 1 5问题求解的基本框架 2 问题求解就是在图中寻找一条从初始节点到达目标节点的通路或操作序列 首先从操作集中选择可作用在当前状态上的操作 如果符合条件的操作有许多个 则要从挑选出最有希望导致目标状态的操作施加到当前状态上 以便克服组合爆炸 如果解的长度很大 还需要更为复杂的克服组合爆炸的技术 2020 4 17 人工智能 33 3 2状态图搜索 3 2 1状态图搜索3 2 2穷举式搜索3 2 3启发式搜索3 2 4加权状态图搜索3 2 5启发式图搜索的A算法和A 算法3 2 6状态图搜索策略小结 2020 4 17 人工智能 34 3 2 1状态图搜索 1 搜索 从初始节点出发 沿着与之相连的边试探地前进 寻找目标节点的过程 搜索过程中经过的节点和边 按原图的连接关系 便会构成一个树型的有向图 这种树型有向图称为搜索树 搜索进行中 搜索树会不断增长 直到当搜索树中出现目标节点 搜索便停止 这时从搜索树中就可很容易地找出从初始节点到目标节点的路径 解 来 2020 4 17 人工智能 35 3 2 1状态图搜索 2 1搜索方式树式搜索在搜索过程中记录所经过的所有节点和边 树式搜索所记录的轨迹始终是一棵树 这棵树也就是搜索过程中所产生的搜索树 线式搜索在搜索过程中只记录那些当前认为在所找路径上的节点和边 不回溯线式搜索可回溯线式搜索 2020 4 17 人工智能 36 3 2 1状态图搜索 3 2搜索策略盲目搜索无向导的搜索 树式盲目搜索就是穷举搜索 不回溯的线式搜索是随机碰撞式搜索 回溯的线式搜索也是穷举式搜索 启发式搜索是利用 启发性信息 引导的搜索策略 启发性信息 就是与问题有关的有利于尽快找到问题解的信息或知识 启发式搜索分为不同的策略 如全局择优 局部择优 最佳图搜索 按扩展顺序不同分为广度优先和深度优先 2020 4 17 人工智能 37 3 2 1状态图搜索 4 3搜索算法搜索的目的是为了寻找初始节点到目标节点的路径 搜索过程中就得随时记录搜索轨迹 ClOSED表动态数据结构来记录考察过的节点 OPEN表的动态数据结构来专门登记当前待考查的节点 OPEN表 CLOSED表 2020 4 17 人工智能 38 3 2 1状态图搜索 5 树式搜索算法步1把初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以顺序编号n 步4若目标节点Sg N 成功退出 步5若N不可扩展 转步2 步6扩展N 生成一组节点 对这组子节点作如下处理 2020 4 17 人工智能 39 3 2 1状态图搜索 6 1 删除N的先辈节点 如果有的话 2 对已存在于OPEN表中的节点 如果有的话 也删除之 删除之前要比较其返回初始节点的新路径与原路径 如果新路径 短 则修改这些节点在OPEN表中的原返回指针 使其沿新路径返回 3 对已存在于CLOSED表的节点 作与 2 同样的处理 并且将其移出CLOSED表 放入OPEN表中重新扩展 4 对其余子节点配上指向N的返回指针后放入OPEN表中某处 或对OPEN表进行重新排序 转步2 2020 4 17 人工智能 40 3 2 1状态图搜索 7 树式算法的几点说明返回指针指的是父节点在CLOSED表中的编号 步6中修改指针的原因是返回初始节点的路径有两条 要选择 短 的那条路径 这里路径长短以节点数来衡量 在后面将会看到以代价来衡量 按代价衡量修改返回指针的同时还要修改相应的代价值 2020 4 17 人工智能 41 3 2 1状态图搜索 8 图3 5修改返回指针示例 2020 4 17 人工智能 42 3 2 1状态图搜索 9 树式搜索例对于已存在于OPEN表中的节点 如果有的话 也删除之 删除之前要比较其返回初始节点的新路径与原路径 如果新路径短 则修改这些节点在OPEN表中的原返回指针 使其沿原路径返回 Path1 Path2 S0 m n P 先扩展 后扩展 P在n之前已是某一节点m的后继 如图所示 说明从S0 P至少有两条路 这时有两种情况 f Path2 f Path1 当前路径较好 要修改P的指针 使其指向n 即搜索之后的最佳路径 否则 原路径好 2020 4 17 人工智能 43 3 2 1状态图搜索 10 对已存在于CLOSED表的节点 作与 2 同样的处理 并将其移出CLOSED表 放入OPEN表中重新扩展 S0 过去生成P的路径 现在生成P的路径 过去对Ps的最优路径 Ps P m n k a P在n之前已是某一节点m的后继 所以需要做如同 2 同样的处理 如图右部所示 b P在Closed表中 说明P的后继也在n之前已经生成 称为Ps 对Ps而言同样可能由于n P这一路径的加入 又必须比较多条路径之后而取代价小的一条 如图左部所示 2020 4 17 人工智能 44 3 2 1状态图搜索 11 例 设当前搜索图和搜索树如图所示 S0 n P m Ps Ps S0 n P m Ps Ps F F 2020 4 17 人工智能 45 3 2 1状态图搜索 12 若启发函数f n 为从S0到节点n的最短路径的长度 用边的数目来考察 当前扩展的节点是搜索图中的n P是n的后继 S0 n P m Ps Ps n P Ps Ps S0 m F F 2020 4 17 人工智能 46 3 2 1状态图搜索 13 P的指针改变后 修改搜索树结果如下 n P Ps S0 F m P s 2020 4 17 人工智能 47 3 2 1状态图搜索 14 不回溯线式搜索算法步1把初始节点S0放入CLOSED表中 步2令N S0 步3若N是目标节点 则搜索成功 结束 步4若N不可扩展 则搜索失败 退出 步5扩展N 选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中 令N N1 转步3 2020 4 17 人工智能 48 3 2 1状态图搜索 15 可回溯的线式搜索步1把初始节点S0放入CLOSED表中 步2令N S0 步3若N是目标节点 则搜索成功 结束 步4若N不可扩展 则移出CLOSED表中的末端节点Ne 若Ne S0 则搜索失败 退出 否则以CLOSED表新的末端节点Ne作为N 即令N Ne 转步4 步5扩展N 选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中 令N N1 转步3 2020 4 17 人工智能 49 3 2 2穷举式搜索 1 广度优先搜索 算法A ed 策略始终在同一级节点中考查 当同一级节点考查完了之后 才考查下一级节点 搜索树自顶向下一层一层逐渐生成 算法步1把初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以顺序编号n 步4若节点N为目标节点 成功退出 步5若N不可扩展 转步2 步6扩展N 将其所有子节点配上指向N的指针放入OPEN尾部 转步2 2020 4 17 人工智能 50 3 2 2穷举式搜索 2 2020 4 17 人工智能 51 3 2 2穷举式搜索 3 广度优先搜索的特点广度优先中OPEN表是一个队列 CLOSED表是一个顺序表 表中各节点按顺序编号 正被考察的节点在表中编号最大 广度优先搜索又称为宽度优先或横向搜索 广度优先策略是完备的 即如果问题的解存在 则它一定可以找到解 并且找到的解还是最优解 广度优先搜索策略与问题无关 具有通用性 缺点搜索效率低 2020 4 17 人工智能 52 3 2 2穷举式搜索 4 八数码问题 2020 4 17 人工智能 53 3 2 2穷举式搜索 5 八数码广度优先搜索 2020 4 17 人工智能 54 3 2 2穷举式搜索 6 深度优先搜索 过程Apd 搜索策略在搜索树的每一层始终先扩展一个子节点 不断地向纵深前进 直到不能再前进 才从当前节点返回到上一级节点 从另一方向继续前进 算法步1把初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以编号n 步4节点N为目标节点 成功退出 步5若N不可扩展 转步2 步6扩展N 将其所有子节点配上指向N的指针放入OPEN首部 转步2 2020 4 17 人工智能 55 3 2 2穷举式搜索 7 2020 4 17 人工智能 56 3 2 2穷举式搜索 8 深度优先搜索的特点OPEN表为一个堆栈 深度优先又称纵向搜索 一般不能保证找到最优解 当深度限制不合理时 可能找不到解 可以将算法改为可变深度限制 即有界深度优先搜索 最坏情况时 搜索空间等同于穷举 2020 4 17 人工智能 57 3 2 2穷举式搜索 9 八数码深度优先搜索 2020 4 17 人工智能 58 3 2 2穷举式搜索 10 有界深度优先搜索 过程Acd 搜索策略给出搜索树深度的限制 当从初始节点出发沿某一分支扩展到一定深度限制时 就不能再继续往下扩展 而只能改变方向继续搜索 算法步1把初始节点S0放入OPEN表中 置S0的深度d S0 0 步2若OPEN表为空 则搜索失败 退出 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以编号n 步4若节点N为目标节点 成功退出 步5若N的深度d N dm 深度限制值 或者若N无子节点 则转步2 步6扩展N 将其所有子节点Ni配上指向N的指针放入OPEN首部 置的d Ni d N 1 转步2 2020 4 17 人工智能 59 3 2 2穷举式搜索 11 a1 a2 a3 a6 b1 b2 b4 b3 b5 S 2020 4 17 人工智能 60 3 2 2穷举式搜索 12 有界深度优先搜索存在的问题深度界限的选择很重要dm若太小 则达不到解的深度 得不到解 若太大 既浪费了计算机的存储空间与时间 又降低了搜索效率 由于解的路径长度事先难以预料 所以要恰当地给出dm的值是比较困难的 即使能求出解 它也不一定是最优解 2020 4 17 人工智能 61 3 2 2穷举式搜索 13 有界深度优先搜索改进dm随搜索深度不断加大 迭代加深搜索 先任意给定一个较小的数作为dm 然后进行上述的有界深度优先搜索 当搜索达到了指定的深度界限dm仍未发现目标节点 并且CLOSED表中仍有待扩展节点时 就将这些节点送回OPEN表 同时增大深度界限dm 继续向下搜索 如此不断地增大dm 只要问题有解 就一定可以找到它 增加一个R表此时找到的解不一定是最优解 为找到最优解 可增设一个表 R 每找到一个目标节点Sg后 就把它放入到R的前 并令dm等于该目标节点所对应的路径长度 然后继续搜索 由于后求得的解的路径长度不会超过先求得的解的路径长度 所以最后求得的解一定是最优解 2020 4 17 人工智能 62 3 2 2穷举式搜索 14 迭代加深搜索过程 步1把初始节点S0放入OPEN表中 置S0的深度d S0 0 dm为任意初值 步2若OPEN表为空 则考查CLOSED表是否有待扩展节点 若无 则问题无解 退出 若有 则取出CLOSED表中待扩展节点放入到OPEN表中 令dm dm d 2020 4 17 人工智能 63 3 2 2穷举式搜索 15 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以编号n 步4若节点N为目标节点 成功退出 步5若N的深度d N dm 深度限制值 则标N为待扩展节点 则转步2 步6N无子节点 则转步2 步7扩展N 将其所有子节点Ni配上指向N的指针放入OPEN首部 置d Ni d N 1 转步2 2020 4 17 人工智能 65 3 2 3启发式搜索 1 启发式搜索的目的利用知识来引导搜索 达到减少搜索范围 降低问题复杂度 启发性信息的强弱强 降低搜索的工作量 但可能导致找不到最优解 弱 一般导致工作量加大 极限情况下变为盲目搜索 但可能可以找到最优解 启发性信息的类型用于扩展节点的选择用于生成节点的选择用于删除节点的选择 2020 4 17 人工智能 66 3 2 3启发式搜索 2 启发函数启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数 通常记为h x 定义启发函数的参考思路一个节点到目标节点的某种距离或差异的量度 一个节点处在最佳路径上的概率根据主观经验的主观打分等 启发式搜索算法启发式搜索要用启发函数来导航 其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程 并且由启发函数值来确定节点的扩展顺序 2020 4 17 人工智能 67 3 2 3启发式搜索 3 全局择优搜索全局择优搜索就是利用启发函数制导的一种启发式搜索方法 该方法亦称为最好优先搜索法 基本思想 在OPEN表中保留所有已生成而未考察的节点 并用启发函数h x 对它们全部进行估价 从中选出最优节点进行扩展 而不管这个节点出现在搜索树的什么地方 2020 4 17 人工智能 68 3 2 3启发式搜索 4 全局择优搜索算法步1把初始节点S0放入OPEN表中 计算h S0 步2若OPEN表为空 则搜索失败 退出 步3移出OPEN表中第一个节点N放入CLOSED表中 并冠以序号n 步4若目标节点Sg N 则搜索成功结束 步5若N不可扩展 则转步2 步6扩展N 计算每个子节点x的函数值h x 并将所有子节点配以指向N的返回指针后放入OPEN表中 再对OPEN表中所有子节点按其函数值的大小以升序排列 转步2 2020 4 17 人工智能 69 3 2 3启发式搜索 6 启发函数h x 为节点x与目标格局相比数码不同的位置个数 从图看出解为 S0 S1 S2 S3 Sg Sg 81324765 2020 4 17 人工智能 70 3 2 3启发式搜索 7 局部择优搜索局部择优搜索是一种启发式搜索方法 是对深度优先搜索方法的一种改进 基本思想是当每一个节点被扩展后 按h x 对每一个子节点计算启发值 并选择最小者作为下一个要考察的节点 由于每次都只是在子节点的范围内选择下一个要考察的节点 范围比较狭窄 所以称为局部择优搜索 2020 4 17 人工智能 71 3 2 3启发式搜索 8 局部择优搜索算法步1把初始节点S0放入OPEN表中 计算h S0 步2若OPEN表为空 则搜索失败 退出 步3移出OPEN表中第一个节点N放入CLOSED表中 并冠以序号n 步4若目标节点Sg N 则搜索成功结束 步5若N不可扩展 则转步2 步6扩展N 计算N每个子节点x的函数值h x 并将N的子节点按估计值升序排列放入OPEN表的首部 为每个子节点配置指向节点N的指针 转步2 2020 4 17 人工智能 72 3 2 4加权状态图搜索 1 例3 6交通图A城是出发地 E是目的地 数字表示两城之间交通费用 求A到E的最小费用的旅行路线 A D C E B 4 6 4 3 3 2 2020 4 17 人工智能 73 3 2 4加权状态图搜索 2 加权状态图与代价树边上附有数值的状态图称为加权状态图或赋权状态图 这种数值称为权值 加权状态图的搜索加权状态图的搜索与权值有关 并且要用权值来导航 具体来讲 加权状态图的搜索算法 要在一般状态图搜索算法基础上再增加权值的计算与传播过程 并且要由权值来确定节点的扩展顺序 代价的计算g x 表示从初始节点S0到节点x的代价 c xi xj 表示父节点xi到子节点xj的代价g xj g xi c xi xj g x0 0 2020 4 17 人工智能 74 3 2 4加权状态图搜索 3 加权状态图转换为代价树搜索从初始节点出发 先把每一个与初始节点相邻的节点作为该节点的子节点 然后对其他节点依次类推 但对其他节点x 不能将其父节点及祖先再作为x的子节点 A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2020 4 17 人工智能 75 3 2 4加权状态图搜索 4 分支界限法 A eg 其基本思想是 每次从OPEN表中选出g x 值最小的节点进行考察 而不管这个节点在搜索树的什么位置上 与全局择优法的区别 2020 4 17 人工智能 76 3 2 4加权状态图搜索 5 分支界限搜索算法步1把初始节点S0放入OPEN表中 计算g S0 步2若OPEN表为空 则搜索失败 退出 步3移出OPEN表中第一个节点N放入CLOSED表中 并冠以序号n 步4若目标节点Sg N 则搜索成功结束 步5若N不可扩展 则转步2 步6扩展N 并将所有子节点配以指向N的返回指针后放OPEN表中 计算每个子节点x的函数值g x 再对OPEN表中所有子节点按g x 值的大小以升序排列 转步2 2020 4 17 人工智能 77 3 2 4加权状态图搜索 6 最近择优法 瞎子爬山法 基本思想 每次仅考察N的子节点的g x 选取N的子节点中代价最小的子节点进行扩展 最近择优法与局部择优法的区别 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 A 2020 4 17 人工智能 79 3 2 4加权状态图搜索 7 代价树的有界深度优先法与直接树的有界深度优先相比 用gm来代替最大深度dm 2020 4 17 人工智能 80 3 2 4加权状态图搜索 8 代价树深度优先搜索搜索的解为A C D E 2020 4 17 人工智能 81 内容回顾 树形图树式搜索策略比较 S0 Sg 2 3 a b 4 6 1 5 c d g f h i j k 5 f 5 4 3 7 8 9 h x 有利于搜索纵向发展 提高搜索效率 但影响完备性 g x 有利于搜索横向发展 提高完备性 但影响搜索效率 穷举式搜索 启发式搜索 加权状态图搜索 2020 4 17 人工智能 82 3 2 5启发式图搜索的A算法和A 算法 1 1 估价函数将启发函数与代价函数相结合 为了防止在单独利用启发函数的时候误入歧途 f x g x h x f x 是初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和 是g x 与h x 的折中 wh x 通过调整w的值 使结果偏重效率或偏重完备性 2020 4 17 人工智能 83 3 2 5启发式图搜索的A算法和A 算法 2 2 A算法步1把附有f S0 的初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3移出OPEN表中第一个节点N放入CLOSED表中 并冠以顺序编号n 步4若目标节点Sg N 则搜索成功 结束 步5若N不可扩展 则转步2 2020 4 17 人工智能 84 3 2 5启发式图搜索的A算法和A 算法 3 步6扩展N 生成一组附有f x 的子节点 对这组节点作如下处理 1 考察是否有已在OPEN表或CLOSED表中存在的节点 若有则再考察其中有无N的先辈节点 若有则删除之 对于其余节点 也删除之 但由于它们被第二次生成 需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f x 的值 修改原则是抄f x 值小的路走 2 对其余子节点配上指向N的返回指针后放入OPEN表中 并对OPEN表按f x 以升序排列 转步2 2020 4 17 人工智能 85 回顾 树式搜索一般算法 1 树式搜索例对于已存在于OPEN表中的节点 如果有的话 也删除之 删除之前要比较其返回初始节点的新路径与原路径 如果新路径短 则修改这些节点在OPEN表中的原返回指针 使其沿原路径返回 Path1 Path2 S0 m n P 先扩展 后扩展 P在n之前已是某一节点m的后继 如图所示 说明从S0 P至少有两条路 这时有两种情况 f Path2 f Path1 当前路径较好 要修改P的指针 使其指向n 即搜索之后的最佳路径 否则 原路径好 2020 4 17 人工智能 86 回顾 树式搜索一般算法 2 对已存在于CLOSED表的节点 作与 2 同样的处理 并将其移出CLOSED表 放入OPEN表中重新扩展 S0 过去生成P的路径 现在生成P的路径 过去对Ps的最优路径 Ps P m n k a P在n之前已是某一节点m的后继 所以需要做如同 2 同样的处理 如图右部所示 b P在Closed表中 说明P的后继也在n之前已经生成 称为Ps 对Ps而言同样可能由于n P这一路径的加入 又必须比较多条路径之后而取代价小的一条 如图左部所示 2020 4 17 人工智能 87 3 2 5启发式图搜索的A算法和A 算法 4 f x g x h x 探讨九宫重排问题的估价函数的设计过程 g x 对某一确定的节点 是确定的值 h x 不同的问题启发函数的定义不同 相同的问题也可以定义出不同的启发函数 衡量h x 优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度 距离 3 估价函数定义探讨 2020 4 17 人工智能 88 3 2 5启发式图搜索的A算法和A 算法 5 九宫重排问题 八数码难题 将棋局用向量A X0 X1 X2 X3 X4 X5 X6 X7 X8 表示 其中Xi为变量 值表示方格Xi内的数字 初始状态S0 0 2 8 3 4 5 6 7 1 目标状态Sg 0 1 2 3 4 5 6 7 8 数码的移动规则就是该问题的状态变化规则 经分析 该问题共有24条规则 分为9组 初始棋局 目标棋局 2020 4 17 人工智能 89 3 2 5启发式图搜索的A算法和A 算法 6 0组规则r1 X0 0 X2 n X0 n X2 0 r2 X0 0 X4 n X0 n X4 0 r3 X0 0 X6 n X0 n X6 0 r4 X0 0 X8 n X0 n X8 0 1组规则r5 X1 0 X2 n X1 n X2 0 r6 X1 0 X8 n X1 n X8 0 8组规则 r22 X8 0 X1 n X8 n X1 0 r23 X8 0 X0 n X8 n X0 0 r24 X8 0 X7 n X8 n X7 0 2020 4 17 人工智能 90 3 2 5启发式图搜索的A算法和A 算法 7 例1 九宫重排问题如下图所示初始节点S0与目标节点Sg 估价函数f x g x h x 因素1格局中将牌是否在家 g x 用节点深度d x 来衡量 如何定义 h x 用x的格局与目标节点格局相比 不在家的将牌数目w x 来衡量 4 2 3 6 5 28314765 4 4 28314765 5 5 5 6 4 6 4 12378465 6 12384765 4 1 扩展顺序 f x 值 2020 4 17 人工智能 92 3 2 5启发式图搜索的A算法和A 算法 9 81263754 a 问题 是否对于所有的节点w x 都能反映出从x节点变化到目标节点的难易程度 到目标的距离 w a 7w b 6 从w x 值看a格局离目标格局更远 a格局真的比b格局距离目标更远吗 81263754 a 81263754 12863754 12863754 12863754 12386754 12386475 12386475 w a 7 实际距离为8 1 2 3 4 5 6 7 8 28143765 28143765 81243765 81243765 81243765 28146375 81324765 81324765 13824765 13824765 12384765 81324765 w b 6 实际距离为11 1 2 3 4 5 6 7 8 9 10 11 2020 4 17 人工智能 95 3 2 5启发式图搜索的A算法和A 算法 12 w x 并不能很好地反映从x节点变化到目标节点的难易程度 w x 启发信息不够 因素2格局中将牌离家的远近 直线距离之和 影响x节点到达目标节点难易程度的因素有哪些 81263754 a 2020 4 17 人工智能 96 3 2 5启发式图搜索的A算法和A 算法 13 81263754 a 28146375 b 考虑因素2 定义h x p x p x 是x格局中每个将牌离家 Sg中的位置 的最短距离 不论路上是否放有其他将牌 的总和 0 2 1 1 1 1 1 1 p a 8 0 2 1 2 2 1 0 1 p b 9 仍未反映出a b到达目标格局的难易程度 实际距离为8 实际距离为11 2020 4 17 人工智能 97 3 2 5启发式图搜索的A算法和A 算法 14 因素3格局中将牌回家的顺序 81263754 28146375 b a 因素4中心位置是否有将牌 沿着周围非中心方格上依顺时针检查x格局中的每一个将牌 如果其后紧跟着的将牌正好是目标格局中该将牌的后续者 该将牌得0分 否则得2分 在正中方格上有将牌得1分 否则得0分 综合因素3和因素4的值 记为s x 2020 4 17 人工智能 98 3 2 5启发式图搜索的A算法和A 算法 15 81263754 a 28146375 b 考虑因素2 p x 因素3和4 s x 2 2 0 0 0 0 0 2 s a 6 2 2 2 0 2 2 2 1 s b 13 h a 8 3 6 36 h b 9 3 13 48 s x 比p x 对到达目标的难易程度影响更大 故 定义h x p x 3s x p a 8 p b 9 2020 4 17 人工智能 99 3 2 5启发式图搜索的A算法和A 算法 16 例2 利用上面定义的h x 解下列九宫重排问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24 2020 4 17 人工智能 102 3 2 5启发式图搜索的A算法和A 算法 13 A 算法对A算法再限制其估价函数中的启发函数h x 满足 对所有的节点x均有 h x h x 其中h x 是从节点x到目标节点的最小代价 这就称为A 算法 A 算法也称为最佳图搜索算法 利用A 算法 如果问题存在最优解 就保证能找到最优解 2020 4 17 人工智能 103 3 2 5启发式图搜索的A算法和A 算法 18 例 修道士和野人问题 在河的左岸有五个修道士 五个野人和一条船 修道士们想用这条船将所有的人都运过河去 但受到以下条件的限制 1 修道士和野人都会划船 但船一次最多只能运三个人 2 在任何岸边及船上野人数目都不得超过修道士 否则修道士就会被野人吃掉 假定野人会服从任何一种过河安排 试规划出一种确保修道士安全过河方案 请定义启发函数 并给出相应的搜索树 2020 4 17 人工智能 104 3 2 5启发式图搜索的A算法和A 算法 15 解 先建立问题的状态空间 问题的状态可以用一个三元数组来描述 S m c b m 左岸的修道士数c 左岸的野人数b 左岸的船数 2020 4 17 人工智能 105 3 2 5启发式图搜索的A算法和A 算法 16 定义启发函数 若满足h n h n 即满足A 条件的 启发函数1 h n 0 启发函数2 h n M C 对状态 1 1 1 启发函数2不满足h n h n 提示 不考虑限制条件的运送次数一定小于有限制条件的运送次数 2020 4 17 人工智能 106 3 2 5启发式图搜索的A算法和A 算法 17 先考虑船在左岸的情况 如果不考虑限制条件 至少需要 M C 3 2 2 1化简后为 M C 3 2 2 1 M C 2再考虑船在右岸的情况 同样不考虑限制条件 船在右岸 需要一个人将船运往左岸 因此 对于状态 M C 0 需要的摆渡数 相当于船在左岸的 M 1 C 1 或 M C 1 1 所以需要的最少摆渡数为 M C 1 2 1 M C综合条件 需要的最少摆渡数为M C 2B 0 4 1 15 h 2f 10 0 5 1 h 3f 11 0 3 1 h 8f 9 0 2 0 h 2f 11 2020 4 17 人工智能 109 3 2 6状态图搜索策略小结 1 树式搜索盲目搜索穷举式广度优先深度优先有界深度优先启发式搜索全局择优 最好优先 基于启发函数h x 局部择优 瞎子爬山 基于h x 分支界限 全局最小代价优先 基于代价g x 最近择优 瞎子爬山 局部最小代价优先 基于g x A算法 基于估价函数f x g x h x A 算法 最佳图搜索 h x h x 线式搜索盲目搜索随机碰撞回溯穷举 生成 测试法 启发式搜索不回溯 瞎子爬山 基于h x g x f x 智能回溯 启发式生成 测试法 2020 4 17 人工智能 110 3 2 6状态图搜索策略小结 2 搜索策略的诸要素分类选择下一个被考察节点的范围全局的 用下标e表示 广度优先分支界限法全局择优局部的 用下标p表示 深度优先瞎子爬山局部择优 2020 4 17 人工智能 111 3 2 6状态图搜索策略小结 3 选择下一个被考察节点标准d N 用下标d表示 搜索树中从S0到N的路径长度 g N 用下标g表示 代价树从S0到N的路径的代价 f N 用下标f表示 代价树中从S0出发经过N节点到Sg的路径的最小代价范围和标准是最基本的要素 由他们演变出了A ed Apd A eg A pg Aef和Apf 2020 4 17 人工智能 112 3 2 6状态图搜索策略小结 4 在p型策略中 又有两个要素需要考虑试探性e型策略本质都是试探型的 因为它必须用OPEN表保存已生成的未考察节点以备选择 P型则不同 无OPEN表一样可以工作无OPEN表 不可撤回 用下标pn表示 一般用n 有OPEN表 可撤回有界性e型策略不会误入无穷分支路径 所以无须设搜索界限 不可撤回n无须设界 试探性P型需要设界 有界用pc表示 一般用c 2020 4 17 人工智能 113 3 3与或图知识表示 3 3 1与或图基本概念3 3 2与或图知识表示 p78 3 3 3博弈问题的与或图表示 2020 4 17 人工智能 114 3 3 1与或图基本概念 1 例3 15证明四边形全等 分析 连接BD B D 原来问题可以分解为两个子问题 Q1 证明 ABC A B C Q2 证明 BCD B C D 原来问题可以分为两个子问题解决 2020 4 17 人工智能 115 3 3 1与或图基本概念 2 问题Q1还可以再被分解为 Q11 证明AB A B Q12 证明AD A D Q13 证明 A A 或Q11 证明AB A B Q12 证明AD A D Q13 证明BD B D 问题Q2还可以再被分解为 Q21 证明BC B C Q22 证明CD C D Q23 证明 C C 或Q21 证明BC B C Q22 证明CD C D Q23 证明BD B D 2020 4 17 人工智能 116 3 3 1与或图基本概念 3 将原问题用图的形式表示如下 弧线表示所连边为 与 的关系 不带弧线的边为或关系 问题的解 2020 4 17 人工智能 117 3 3 1与或图基本概念 4 与或图的概念来源于问题求解一个复杂的问题P常常可以分解为与之等价的一组子问题P1 P2 Pn 当这些问题全部可解时 问题可解 任何一个子问题无解时 都将导致原问题P无解 即一个问题与一组子问题的与等价 一个复杂的问题P常常可以分别归约为与之等价的一组子问题P1 P2 Pn 其中任何一个子问题可解时 问题可解 全部子问题无解时 原问题P无解 即一个问题与一组子问题的或等价 2020 4 17 人工智能 118 3 3 1与或图基本概念 5 2020 4 17 人工智能 119 3 3 2与或图知识表示 1 与或图的几个概念直接可解的问题称为本原问题 本原问题对应的节点称为终止节点 无子节点的节点称为端节点 子节点为与关系 则该节点为与节点 子节点为或关系 则该节点为或节点 与或图一般表示问题的变换过程 就是从原问题出发 运用某些规则不断的进行问题的分解 得到与分支 和变换 得到或分支 而得到一个与或图 与或图的节点一般代表问题 整个图就表示问题空间 2020 4 17 人工智能 120 3 3 2与或图知识表示 2 与或图也是一个三元组 Q0 F Qn Q0表示初始问题F表示问题变换规则集Qn表示本原问题集 2020 4 17 人工智能 121 3 3 2与或图知识表示 3 例3 19三阶梵塔问题 对于