![](https://csdnimg.cn/release/download_crawler_static/86379830/bg3.jpg)
非 目 标 节 点 都 有 h2(n)> h1(n),则 在 具 有 一 条 从 s 到 t 的 路 径 的 隐 含 图 上 ,搜 索 结
束 时 由 A2 所 扩 展 的 每 一 个 节 点 也 必 定 由 A1 所 扩 展 ,即 A1 扩 展 的 结 点 至 少 和 A2
一 样 多 。
单 调 限 制 条 件:即 如 果 对 所 有 结 点 ni 和 nj, nj 是 ni 的 子 节 点 , 都 有 h(ni)-
h(nj)≤C(ni,nj)( 结 点 ni 到 结 点 nj 的 弧 线 耗 散 值 )且 h(ti)=0,则 称 该 h 函 数 满
足 单 调 限 制 条 件 。 意 义 是 从 ni 到 目 标 结 点 , 最 佳 路 径 耗 散 值 估 计 h(ni)不 大 于 nj
到 目 标 结 点 最 佳 路 径 耗 散 值 估 计 h(nj)与 ni 到 nj 弧 线 耗 散 值 两 者 之 和 。 定 义 满 足
单 调 限 制 的 h 函 数 时 避 免 重 复 扩 展 结 点 的 好 办 法 。
定 理 5: 若 h(n)满 足 单 调 限 制 条 件 , 则 A*扩 展 了 结 点 n 后 就 已 经 找 到 了 到
达 结 点 n 的 最 佳 路 径 。
定 理 6:若 h(n)满 足 单 调 限 制 ,则 由 A*所 扩 展 的 结 点 序 列 ,其 f 值 是 非 递 减
的 , 即 f(ni)≤f(nj)。
A*求 解 八 数 码 问 题 : 其 实 完 全 等 同 于 A 算 法 求 解 八 数 码 问 题 , 因 为 我 们 取
h(n)=W(n)即 不 在 位 牌 数 , 是 满 足 单 调 限 制 的 。 就 是 画 出 OPEN 和 CLOSED 的 表
格 以 及 搜 索 树 即 可 , 最 后 给 出 路 径 。
3)给 出 一 个 博 弈 树 , 进 行 α-β 剪 枝 搜 索 ( 与 或 图 ), 标 出 何 处 发 生 剪 枝 、 节 点 的
倒 推 值 和 最 佳 走 步 :
A. 与 或 图 : 对 于 具 有 多 个 求 解 方 法 的 问 题 来 讲 , 其 解 决 方 案 之 间 是 或 的 关 系 ,
而 求 解 每 个 解 决 方 案 又 要 划 分 为 多 个 子 问 题 , 这 些 子 问 题 之 间 是 与 的 关 系 ,
因 而 前 述 关 系 可 以 用 与 或 图 的 形 式 表 现 出 来 。 表 示 方 法 用 k-连 接 符 的 形 式 ,
若 k> 1 且 每 2 个 子 节 点 之 间 的 弧 线 有 类 似 角 的 圆 弧 连 接 , 则 表 示 这 些 子
节 点 是 与 的 关 系 。
B. 解 图 ( 在 与 或 图 无 环 下 ): 一 个 与 或 图 G 中 , 从 节 点 n 到 结 点 集 N 的 解 图
即 为 G', G' 是 G 的 子 图 。 递 归 定 义 : ①若 n 是 N 的 一 个 元 素 , 则 G'