·398· 北京科技大学学报 1999年第4期 4启发式搜索算法研究 子节点，即找到满意的图像为止· 4.2算法的修改 在图像库中检索一幅图像就是在检索树上 在上面的由样本集训练求取启发评价函数 从根节点或从某一类节点（中间节点）开始搜索 h(a,b)的算法中存在如下的不足：①用k个样本 满足用户要求的叶子节点（即图像）.我们采用 节点对求取权矢量W时，选用不同的k个样本 启发式搜索技术进行树搜索，其关键在于启发 节点对所求得的权矢量W可能不同.②即使选 评价函数的确定， 用了一个W,它也只是由k个相应的样本节点 41启发评价函数的构造 对求出来的.因此，这时的W也只是对这k个样 设检索树上任一节点a,其子节点之一为b, 本节点对的h(a,b)是最小均方差估计，对剩余 则二者间的启发评价函数构造为： 的样本节点对不一定也是这样. h(a,b)=wo+w (a,b)+wzf (a,b)+.+wf (a,b)(1) 专家经验的可贵之处就在于其对某些特例 其中，w,为权系数，i=0,1,2,…,n;a,b)为节点对 有独到的推理方式，因此启发式搜索中的启发 (a,b)间的第j个联系特征值，广=1,2，…，n:n为联 评价函数h(a,b)应根据这样的经验来获取， 系特征的个数. 定义5任选图像库中的一幅图像，在检索 联系特征f(a,b)的选择应根据检索树上的 树上找出从其对应的叶子节点开始逐层向上直 特征向量或类特征向量的表示形式与内容来确 到根节点的所有分枝，称这些分枝为优先枝，即 定.在人脸图像库中，检索树上的特征向量是15 目标所在路径上的分枝为优先枝，而检索树上 维的向量，因此各节点间最简单的联系特征是： 相应的其他分枝称为非优先枝 节点对应向量间的夹角、距离、对应分量之差与 对检索树上的所有节点对按下述三原则指 和等.对于一组给定的样本节点对集{(a,b)},根 导专家凭经验给定评价值h(a,b). 据专家经验可给出一组评价值h(a,b).将专家 原则1若节点对(a,b)在优先枝上，则 的定性经验定量化就是用h(a,b)尽可能的逼近 h(a,b)<0,为负值：否则h(a,b)>0,为正值. h*(a,b),即确定的h(a,b)必须使下述均方估值 原则2若节点对(a,b)在优先枝上，h(a,b), (MS)最小： 则随着深度增大（即离根节点越远）而减小，即 MS=E(h'(a,b)-[wo+wih(a,b)+wzf (an,b)+ h(a,b)更负；否则，h(a,b)增大，即更正. …+wn(a,b)]}2 (2) 原则3在同一层上的各非优先枝上的节点 其中k为样本节点对数.在MS中，h*(a,b)和 对(a,b)的h(a,b)基本上相同. f(a,b,)为已知，只有权系数w0=0,1,…,n)未知. 在检索树上任选k个节点对由式(4)求出权 由变分法可知，MS最小时，应满足条件： 矢量W,并代入式(1)得到启发评价函数h(a,b). aMS9/aw,=0j=0,l,…,n (3) 按下面的方法利用剩余的样本节点对对权矢量 定义4个矩阵F,H,H*,W如下. W进行修正，即修正启发评价函数h(a,b). 联系特征矩阵F: 对于剩余的节点对(a,b0=k+1…L;L为所 「1f(a,b)5(a,bi)…f(a,b)l [FT(a,b) 有的节点对数)，若h(ab)与h(a,b)同号，则不 1f(a2,b,)5(a,b)…f6(a,b,) F(a2,b2) F- 用修正权矢量W,否则按如下方法修改权矢量 】… 4 W.令 1 f(a,ba)f (asb)..(as,b)F(a,b) a=[h(a,b)-h(a,b,】0≤≤1（由经验选定）. 启发评价函数矢量H和评价值矢量H: 设修正后的权矢量为W,修正后的启发评 H=[h(a,b)h(az,b2)..h(as,ba)]. 价函数为h(a,b),则W'=W+aFa,b), H=[h(a,bi)h'(a,b)…h'(a,b)]'. h'(ab)=h(a,b)+aF(ab). 权矢量W:W=[wo,w,…,w]I.根据矩阵运算求得： 可证明h《a,b)比h(a,b)更为接近h'(a,b,). W=(FT.F)·FT·f (4) 最后重新对所有的节点对进行迭代检查其 H=F.W (5) h(a,b)与h(a,b,)是否同号，若异号则进行修正， 由式(4)就可求出W,进而就确定了启发评 直到所有的节点对都满足h(a,b)与h'(a,b)同号 价函数h(a,b).当启发评价函数确定后，在检索 为止，从而就确定了权矢量W,也就决定了启发 时总是沿着h(a,b)最优的支路进行检索直到叶· 北 京 科 技 大 学 学 报 年 第 期 启发式搜索算法研究 在 图像库 中检索一 幅 图像就 是 在检索树上 从根节 点或 从某一 类节 点 中 间节 点 开 始搜索 满足用 户 要 求 的叶 子 节 点 即 图像 我们 采 用 启 发式搜索技术进 行 树搜索 ， 其 关 键在 于 启 发 评价 函数 的确 定 启 发评价函数的构造 设检索树上任一节 点 ， 其子节 点之一 为 ， 则二 者 间 的启发评 价 函 数构造为 ， 厂 ， 诱 ， … 抓 ， 其 中 ， ，为权系数 ， ， ， ， … ， 双， 为节 点对 ， 间 的第 个联 系特 征值 ， ， ， … ， 为联 系特 征 的个数 联 系特征芳 ， 的选择应根据检索树 上 的 特征 向量或类特征 向量 的表 示 形 式 与 内容来确 定 在人脸 图像库中 ， 检索树上 的特征 向量 是 巧 维 的 向量 ， 因此各 节点 间最简单 的联系特征是 节 点对应 向量 间 的夹 角 、 距 离 、 对应分量之 差 与 和 等 对于 一 组给定 的样本节 点对集 ，， ， 根 据 专 家 经 验 可 给 出一 组 评价 值 山， 将 专 家 的定性经 验 定量化 就是 用 口， 尽 可 能 的逼 近 ， ， 即确 定 的 ， 必 须 使下 述均方估值 最 小 艺 ‘ ，， 护 一 。 厂 ， ‘ 抓 ‘， ‘ … 琳苏 风 ， ’ 其 中 为样 本节 点对 数 在 中 ， ， ， ， 和 芳 ，〕为 已 知 ， 只 有 权 系数 玛仃二 ， ，… ， 未 知 由变分法可 知 ， 最 小时 ， 应满足条件 刁 习 ， ，… ， 定义 个矩 阵 ， ， 月 ， 砰 如 下 … 联系特 征矩 阵 厂 ， 关 ，， ， … 不 ， ， 厂 ， 关 ， … 不 仇 ， 厂 ， 关，，办 … 不 ， 尸 ， 尸 伪 ， 尸 ， 启 发 评 价 函数 矢 量 和 评价值矢量 ‘ 万二 ， ， … 诀力 ’ 【 ’ ，， ’ ， … ‘ 仇 ， 〕 权矢量 琪 环任 ， ， … ， 磷 根据矩阵运算求得 、产、， 了、 了 以︸ 声 ‘ 、 尸 尸 · 刀七 一 ， · 尸 · 矿 甲 由式 就 可 求 出 琳 进而 就确 定 了启发评 价 函 数 ， 当启 发 评价 函 数 确 定后 ， 在检索 时总是沿着 口 ， 最 优 的支路 进行检索直到 叶 子节 点 ， 即 找到满 意 的 图像 为止 算法 的修改 在上 面 的 由样 本集训 练求取启 发 评 价 函 数 ， 的算法 中存在如下 的不足 ①用 个样本 节 点对求取权矢量 甲 时 ， 选用 不 同 的 个样本 节 点对所求得 的权矢量 牙可 能不 同 ② 即使选 用 了一个 矶 它也只 是 由 个相应 的样本节 点 对 求 出来 的 因此 ， 这 时 的 牙也 只 是对这 个样 本节 点对 的 ， 是最 小均方差 估计 ， 对剩余 的样本节 点对不 一 定也 是 这样 专家经验 的可 贵之 处 就在 于 其 对 某些特例 有独 到 的推理 方式 ， 因此 启发式搜索 中的启发 评价 函 数 ， 应 根据 这 样 的经验 来获取 定义 任选 图像库 中的一 幅 图像 ， 在检索 树上 找 出从 其对应 的叶子节 点 开 始逐层 向上 直 到根节 点 的所有分枝 ， 称这些分 枝为优先枝 即 目标所在路径 上 的分枝 为优先 枝 ， 而检 索树上 相 应 的其他分 枝称 为非 优先 枝 对 检索树上 的所 有节 点对按下 述三原则指 导专 家凭经 验给定评 价值 ’ ， 原 则 若 节 点 对 ， 在 优 先 枝 上 ， 则 ’ ， ， 为 负值 否 则 ’ ， ， 为正 值 原 则 若节 点对 ， 在优先 枝上 ， ’ ， ， 则随 着深 度增大 即离根节 点越远 而 减小 ， 即 ‘ ， 更 负 否 则 ， ’ ， 增大 ， 即更 正 原 则 在 同一层 上 的各 非优 先枝上 的节 点 对 ， 的 ’ ， 基 本上 相 同 在检 索树上 任选 个节 点对 由式 求 出权 矢 量 砰 ， 并代入 式 得 到启 发评价 函 数 ， 按下 面 的方法利用剩余 的样 本节 点对 对权矢 量 附 进行 修正 ， 即 修正 启 发 评 价 函 数 ， 对 于 剩余 的节 点对 ，，分 十 卜 · 工工 为所 有 的节 点对 数 ， 若 ， 与 ’ ，助 同号 ， 则不 用修正 权矢 量 砰 ， 否 则按如下 方法 修改权矢 量 跳 令 又 ，，，一 ， 」 ‘ 又‘ 由经验 选定 设修正 后 的权矢量 为 甲 ， 修正 后 的启发评 价 函 数为 ，’ ， 则 甲 牙 口爪， ， ， ， 马 ， 回马 ， ， 可证 明 丫，动 比 ，， 更 为接近 ’ ，动 最 后 重新对所有 的节 点对进行迭代检查 其 ，， 与 ’ ， 是否 同号 ， 若异号则进行修正 ， 直到所有 的节点对都满足 ， 与 厅 ，， 同号 为止 ， 从而 就确定 了权矢量 邢 ， 也就 决定 了启 发