33启发式搜索 ☆特点:重排OPEN表,选择最有希望的节点 加以扩展 令种类:有序搜索、A算法等 33.1启发式搜索策略和估价函数 令盲目搜索可能带来组合爆炸 令启发式信息 用来加速搜索过程的有关问題领域的特征信息 11
11 3.3 启发式搜索 ❖特点：重排OPEN表，选择最有希望的节点 加以扩展 ❖种类：有序搜索、A*算法等 3.3.1 启发式搜索策略和估价函数 ❖盲目搜索可能带来组合爆炸 ❖启发式信息 用来加速搜索过程的有关问题领域的特征信息
33启发式搜索 ■令估价函数 为获得某些节点“希望”的启发信息 (提供 (个评定侯选扩畏节点的方法,以便确定哪个节点最 有可能在通向目标的最佳路径上 f(n)—表示节点n的估价函数值 令应用节点“希望”程度「估价函数值)重排OPEN 3.3有序搜索 心实质 选择OPEN表上具有最小f值的节点作为下一个 要扩畏的节点。 12
12 ❖估价函数 为获得某些节点“希望”的启发信息，提供一 个评定侯选扩展节点的方法，以便确定哪个节点最 有可能在通向目标的最佳路径上 。 f(n)——表示节点n的估价函数值 ❖应用节点“希望”程度（估价函数值）重排OPEN 表 3.3.2 有序搜索 ❖实质 选择OPEN表上具有最小f值的节点作为下一个 要扩展的节点。 3.3 启发式搜索
33启发式搜索 开始 ■算法 把S放入OPEN表, 计算佑价函数f(s) 是 OPEN表为空表? 失败 否 选取OPEN表中f值录小的节点放入 CLOSED表 i为目标节点吗? 成功 扩長i,得后继节点j,计算f(j),提供返回 掌点的指什用联)对OPE重排C 图39有序披索算法框图 3
13 开始 把S放入OPEN表， 计算估价函数f (s) OPEN表为空表？ 选取OPEN表中f值最小的节点i放入CLOSED表 i为目标节点吗？ 扩展i，得后继节点j，计算f(j)，提供返回 节点i的指针，利用f(j)对OPEN表重新排 序，调整亲子关系及指针 失败 成功 图3.9 有序搜索算法框图 是 否 是 否 3.3 启发式搜索 ❖算法
33启发式搜索 心例子 八数码难題(8 puzzle problem) 283 123 164 8 7 5 765 ((初始状态) (目标状态) 八数码难题的有序搜索树见下图: 14
14 ❖ 例子 八数码难题（8-puzzle problem） 1 2 3 8 4 7 6 5 （目标状态） 1 2 8 3 4 5 6 7 （初始状态） 八数码难题的有序搜索树见下图： 3.3 启发式搜索
33启发式搜索 (6 3 (5) 5) (6) (6) l(7 (5) (7) (5)8 图3.10八数码难题的 有序搜索树 (5) (7) 15
15 7 5 1 4 5 6 3 1 2 8 3 4 7 6 5 1 2 8 3 4 5 6 7 1 2 8 3 4 5 6 7 （6） （4） （6） 2 1 2 3 8 4 7 6 5 1 2 8 3 4 7 6 5 1 2 8 3 4 7 6 5 （5） （5） （6） 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 （5） （7） 2 8 3 4 6 5 2 1 7 8 3 4 7 6 5 （6） （7） 1 2 3 8 4 7 6 5 （5） 8 1 2 3 4 7 6 5 1 2 3 8 4 6 5 （5） 7 （7） 图3.10 八数码难题的 有序搜索树 1 2 8 3 6 4 （4） 7 3.3 启发式搜索