计算机算法基础9.ppt

第九章 分枝－限界法 第八章中的基本概念 问题解的n元组表示 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点 分枝－限界法 分枝－限界法：在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。 例9.1 4-皇后问题的状态空间树。 采用FIFO分枝－限界法检索4-皇后问题的状态空间树： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树（续）： 采用FIFO分枝－限界法检索4-皇后问题的状态空间树： 4-皇后问题—回溯 vs FIFO分枝-限界 LC-检索（Least Cost） LIFO和FIFO分枝-限界法存在的问题 对下一个E-结点的选择规则过于死板、盲目。对于有可能快速检索到一个答案结点的结点没有给出任何优先权。如结点30。 结点成本函数 C(·)：“有智力”的排序函数，依据成本排序，优先选择成本 最小的活结点作为下一个扩展的E结点。 C(·)又称为“结点成本函数” 结点成本函数C(X)的定义： 1）如果X是答案结点，则C(X)是由状态空间树的根结点到 X的成本(即所用的代价，可以是级数、计算复杂度等) 2) 如果X不是答案结点且子树X不包含任何答案结点，则 C(X)＝∞ 3) 如果X不是答案结点但子树X包含答案结点，则C(X)等 于子树X中具有最小成本的答案结点的成本 结点成本函数的计算 计算结点成本函数的困难 计算一个结点的代价通常要检索包含一个答案结点的子树X才能确定，因此计算C(X)的工作量和复杂度与解原始问题是相同的。 ：设 是由X到达一个答案结点所需成本的 估计函数。 性质：单纯使用 选择E结点会导致算法偏向 纵深检查。 如何避免单纯考虑 造成的纵深检查？ 引进h(X)改进成本估计函数。 h(X)：根结点到结点X的成本。 15-谜问题（问题描述） 问题状态：15块牌在棋盘上的任一种排列。 初始状态：初始排列（任意给定的） 目标状态：目标排列（确定的） 棋盘存在16！种（约20万亿种）不同排列，而对于任一给定的初始状态，可到达的状态为这些排列中的一半。 如何判定目标状态在初始状态的状态空间中？ 判定条件由以下4步给出： 1）给棋盘的方格位置编号：按目标状态各块牌在棋盘上的排列给对应方格编号，空格为16。 目标状态是否在初始状态的状态空间中的判别条件由定理7.1给出： 定理7.1 当且仅当 是偶数时， 目标状态可由此初始状态到达。 证明 （略） 15-谜问题实例 FIFO检索 FIFO检索 15-谜问题深度优先检索 简单检索存在的问题：呆板和盲目 例：使用 的LC-检索 LC-检索的抽象化控制 设： T 是一棵状态空间树 c(·)是T的结点成本函数 是成本估计函数。 具备以下性质： 如果X是一个答案结点或者是一个叶结点，则c(X)= 。 LC-检索的抽象化控制 procedure LC(T, ) //为找答案结点检索T, 为结点成本估计函数// if T是答案结点 then 输出T; return endif //T为答案结点，输出T// E ? T //E－结点// 将活结点表初始化为空 loop for E的每个儿子X do if X是答案结点