动态规划网络

《动态规划网络》由会员分享，可在线阅读，更多相关《动态规划网络（51页珍藏版）》请在装配图网上搜索。

1、 学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩； （7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。 n 动 态 规 划 算 法 与 分 治 法 类 似 ， 其 基 本 思

2、想 也 是 将 待 求 解 问 题 分解 成 若 干 个 子 问 题 nT(n/2) T(n/2) T(n/2) T(n/2)T(n) = n 但 是 经 分 解 得 到 的 子 问 题 往 往 不 是 互 相 独 立 的 。 不 同 子 问 题 的数 目 常 常 只 有 多 项 式 量 级 。 在 用 分 治 法 求 解 时 ， 有 些 子 问 题 被重 复 计 算 了 许 多 次 。 n=n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2T(n/4)T(n/4) n/2T(n/4) T(n/4) T(n/4)T(n/4) T(n/4)T(n) n 如 果 能 够

3、 保 存 已 解 决 的 子 问 题 的 答 案 ， 而 在 需 要 时 再 找 出 已 求得 的 答 案 ， 就 可 以 避 免 大 量 重 复 计 算 ， 从 而 得 到 多 项 式 时 间 算法 。 n=n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2T(n/4)T(n/4) n/2T(n/4) T(n/4) T(n/4)T(n/4) T(n/4)T(n) n 找 出 最 优 解 的 性 质 ， 并 刻 划 其 结 构 特 征 。n 递 归 地 定 义 最 优 值 。n 以 自 底 向 上 的 方 式 计 算 出 最 优 值 。n 根 据 计 算 最 优 值

4、 时 得 到 的 信 息 ， 构 造 最 优 解 。 u 完 全 加 括 号 的 矩 阵 连 乘 积 可 递 归 地 定 义 为 ： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC) 。u 设 有 四 个 矩 阵 A,B,C,D ， 它 们 的 维 数 分 别 是 ： A=5010，B=1040，C=4030，D=305 总共有五中完全加括号的方式： (AB)C)D)，(A(BC)D)，(A(B(CD)，(AB)(CD)，(A(BC)D) 计算量分别为87500, 16000, 10500, 3600

5、0, 34500 n 给 定 n个 矩 阵 ， 其 中 与 是 可 乘的 ， 。 考 察 这 n个 矩 阵 的 连 乘 积 n 由 于 矩 阵 乘 法 满 足 结 合 律 ， 所 以 计 算 矩 阵 的 连 乘 可 以 有 许 多 不同 的 计 算 次 序 。 这 种 计 算 次 序 可 以 用 加 括 号 的 方 式 来 确 定 。n 若 一 个 矩 阵 连 乘 积 的 计 算 次 序 完 全 确 定 ， 也 就 是 说 该 连 乘 积 已完 全 加 括 号 ， 则 可 以 依 此 次 序 反 复 调 用 2个 矩 阵 相 乘 的 标 准 算法 计 算 出 矩 阵 连 乘 积 ,., 21

6、nAAA iA 1iA1,.,2,1 ni nAAA .21 给 定 n个 矩 阵 A1,A2,An ， 其 中 Ai与 Ai+1是 可 乘 的 ， i=1，2， n-1。 如 何 确 定 计 算 矩 阵 连 乘 积 的 计 算 次 序 ， 使 得 依 此 次序 计 算 矩 阵 连 乘 积 需 要 的 数 乘 次 数 最 少 。u穷 举 法 ： 列 举 出 所 有 可 能 的 计 算 次 序 ， 并 计 算 出 每 一 种 计算 次 序 相 应 需 要 的 数 乘 次 数 ， 从 中 找 出 一 种 数 乘 次 数 最 少 的计 算 次 序 。 算 法 复 杂 度 分 析 ：对 于 n个 矩

7、阵 的 连 乘 积 ， 设 其 不 同 的 计 算 次 序 为 P(n)。由 于 每 种 加 括 号 方 式 都 可 以 分 解 为 两 个 子 矩 阵 的 加 括 号 问 题 ：(A1.Ak)(Ak+1An)可 以 得 到 关 于 P(n)的 递 推 式 如 下 ：)/4()( 11)()( 1)( 2/311 nnPnnknPkPnP nnk u穷 举 法u动 态 规 划将 矩 阵 连 乘 积 简 记 为 Ai:j ， 这 里 ij jii AAA .1考 察 计 算 Ai:j的 最 优 计 算 次 序 。 设 这 个 计 算 次 序 在 矩 阵Ak和 Ak+1之 间 将 矩 阵 链 断

8、开 ， ikj， 则 其 相 应 完 全加 括 号 方 式 为 ).)(.( 211 jkkkii AAAAAA 计 算 量 ： Ai:k的 计 算 量 加 上 Ak+1:j的 计 算 量 ， 再 加 上Ai:k和 Ak+1:j相 乘 的 计 算 量 n 特 征 ： 计 算 Ai:j的 最 优 次 序 所 包 含 的 计 算 矩 阵 子链 Ai:k和 Ak+1:j的 次 序 也 是 最 优 的 。n 矩 阵 连 乘 计 算 次 序 问 题 的 最 优 解 包 含 着 其 子 问 题的 最 优 解 。 这 种 性 质 称 为 最 优 子 结 构 性 质 。 问 题的 最 优 子 结 构 性 质

9、是 该 问 题 可 用 动 态 规 划 算 法 求解 的 显 著 特 征 。 n 设 计 算 Ai:j， 1ijn， 所 需 要 的 最 少 数 乘 次 数 mi,j， 则原 问 题 的 最 优 值 为 m1,n n 当 i=j时 ， Ai:j=Ai， 因 此 ， mi,i=0， i=1,2,nn 当 ij时 ， n 可 以 递 归 地 定 义 mi,j为 ： jki pppjkmkimjim 1,1, 这 里 的 维 数 为 iA ii pp 1 jipppjkmkim jijim jki ,1,min 0, 1jki 的 位 置 只 有 种 可 能k ij n 对 于 1ijn不 同 的

10、有 序 对 (i,j)对 应 于 不 同 的 子 问 题 。 因 此 ，不 同 子 问 题 的 个 数 最 多 只 有n 由 此 可 见 ， 在 递 归 计 算 时 ， 许 多 子 问 题 被 重 复 计 算 多 次 。 这 也是 该 问 题 可 用 动 态 规 划 算 法 求 解 的 又 一 显 著 特 征 。n 用 动 态 规 划 算 法 解 此 问 题 ， 可 依 据 其 递 归 式 以 自 底 向 上 的 方 式进 行 计 算 。 在 计 算 过 程 中 ， 保 存 已 解 决 的 子 问 题 答 案 。 每 个 子问 题 只 计 算 一 次 ， 而 在 后 面 需 要 时 只 要 简

11、 单 查 一 下 ， 从 而 避 免大 量 的 重 复 计 算 ， 最 终 得 到 多 项 式 时 间 的 算 法)(2 2nnn void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j

12、 + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; 若 给 定 序 列 X=x1,x2,xm， 则 另 一 序 列Z=z1,z2,zk，

13、是 X的 子 序 列 是 指 存 在 一 个 严 格 递 增下 标 序 列 i1,i2,ik使 得 对 于 所 有 j=1,2,k有 ： zj=xij。例 如 ， 序 列 Z=B， C， D， B是 序 列 X=A， B， C， B，D， A， B的 子 序 列 ， 相 应 的 递 增 下 标 序 列 为 2， 3， 5，7。给 定 2个 序 列 X和 Y， 当 另 一 序 列 Z既 是 X的 子 序 列 又 是Y的 子 序 列 时 ， 称 Z是 序 列 X和 Y的 公 共 子 序 列 。给 定 2个 序 列 X=x1,x2, ,xm和 Y=y1,y2, ,yn， 找出 X和 Y的 最 长 公

14、 共 子 序 列 。 设 序 列 X=x1,x2,xm和 Y=y1,y2,yn的 最 长 公 共 子 序 列 为Z=z1,z2,zk ， 则(1)若 xm=yn， 则 zk=xm=yn， 且 zk-1是 xm-1和 yn-1的 最 长 公 共 子 序 列 。(2)若 xmyn且 zkxm， 则 Z是 xm-1和 Y的 最 长 公 共 子 序 列 。(3)若 xmyn且 zkyn， 则 Z是 X和 yn-1的 最 长 公 共 子 序 列 。由 此 可 见 ， 2个 序 列 的 最 长 公 共 子 序 列 包 含 了 这 2个 序 列 的 前 缀的 最 长 公 共 子 序 列 。 因 此 ， 最

15、长 公 共 子 序 列 问 题 具 有 最 优 子 结构 性 质 。 由 最 长 公 共 子 序 列 问 题 的 最 优 子 结 构 性 质 建 立 子 问 题 最 优 值的 递 归 关 系 。 用 cij记 录 序 列 和 的 最 长 公 共 子 序 列 的 长 度 。其 中 ， Xi=x1,x2,xi； Yj=y1,y2,yj。 当 i=0或 j=0时 ， 空 序列 是 Xi和 Yj的 最 长 公 共 子 序 列 。 故 此 时 Cij=0。 其 它 情 况 下 ，由 最 优 子 结 构 性 质 可 建 立 递 归 关 系 如 下 ： ji ji yxji yxji jijicjic ji

16、cjic ;0, ;0, 0,01,1max 111 0 由 于 在 所 考 虑 的 子 问 题 空 间 中 ， 总 共 有 (mn)个 不 同 的 子 问 题 ，因 此 ， 用 动 态 规 划 算 法 自 底 向 上 地 计 算 最 优 值 能 提 高 算 法 的 效 率 。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j

17、 = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 构 造 最 长 公 共 子 序 列void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); coutxi; else if (bij= 2) LCS(i-1，j，x，b); else LCS(i，j-1，x，b); 在 算 法 lcsLength和 lcs中 ， 可 进 一 步 将 数 组 b省 去 。事 实 上 ， 数 组 元 素 cij的 值 仅 由 ci

18、-1j-1， ci-1j和cij-1这 3个 数 组 元 素 的 值 所 确 定 。 对 于 给 定 的 数 组元 素 cij， 可 以 不 借 助 于 数 组 b而 仅 借 助 于 c本 身 在 时间 内 确 定 cij的 值 是 由 ci-1j-1， ci-1j和 cij-1中哪 一 个 值 所 确 定 的 。如 果 只 需 要 计 算 最 长 公 共 子 序 列 的 长 度 ， 则 算 法 的 空间 需 求 可 大 大 减 少 。 事 实 上 ， 在 计 算 cij时 ， 只 用 到数 组 c的 第 i行 和 第 i-1行 。 因 此 ， 用 2行 的 数 组 空 间 就 可以 计 算

19、出 最 长 公 共 子 序 列 的 长 度 。 进 一 步 的 分 析 还 可将 空 间 需 求 减 至 O(min(m,n)。 用 多 边 形 顶 点 的 逆 时 针 序 列 表 示 凸 多 边 形 ， 即 P=v0,v1,vn-1表 示 具 有 n条 边 的 凸 多 边 形 。若 vi与 vj是 多 边 形 上 不 相 邻 的 2个 顶 点 ， 则 线 段 vivj称 为 多 边 形 的一 条 弦 。 弦 将 多 边 形 分 割 成 2个 多 边 形 vi,vi+1,vj和 vj,vj+1,vi。多 边 形 的 三 角 剖 分 是 将 多 边 形 分 割 成 互 不 相 交 的 三 角 形

20、 的 弦 的集 合 T。给 定 凸 多 边 形 P， 以 及 定 义 在 由 多 边 形 的 边 和 弦 组 成 的 三 角 形上 的 权 函 数 w。 要 求 确 定 该 凸 多 边 形 的 三 角 剖 分 ， 使 得 即 该 三 角剖 分 中 诸 三 角 形 上 权 之 和 为 最 小 。 一 个 表 达 式 的 完 全 加 括 号 方 式 相 应 于 一 棵 完 全 二 叉 树 ， 称为 表 达 式 的 语 法 树 。 例 如 ， 完 全 加 括 号 的 矩 阵 连 乘 积(A1(A2A3)(A4(A5A6)所 相 应 的 语 法 树 如 图 (a)所 示 。凸 多 边 形 v0,v1,

21、vn-1的 三 角 剖 分 也 可 以 用 语 法 树 表 示 。 例如 ， 图 (b)中 凸 多 边 形 的 三 角 剖 分 可 用 图 (a)所 示 的 语 法 树表 示 。 矩 阵 连 乘 积 中 的 每 个 矩 阵 Ai对 应 于 凸 (n+1)边 形 中 的 一 条 边vi-1vi。 三 角 剖 分 中 的 一 条 弦 vivj， ij， 对 应 于 矩 阵 连 乘 积Ai+1:j。 凸 多 边 形 的 最 优 三 角 剖 分 问 题 有 最 优 子 结 构 性质 。事 实 上 ， 若 凸 (n+1)边 形 P=v0,v1,vn-1的 最优 三 角 剖 分 T包 含 三 角 形 v0

22、vkvn， 1kn-1， 则 T的 权 为 3个 部 分 权 的 和 ： 三 角 形 v0vkvn的 权 ，子 多 边 形 v0,v1,vk和 vk,vk+1,vn的 权 之 和 。可 以 断 言 ， 由 T所 确 定 的 这 2个 子 多 边 形 的 三 角剖 分 也 是 最 优 的 。 因 为 若 有 v0,v1,vk或vk,vk+1,vn的 更 小 权 的 三 角 剖 分 将 导 致 T不 是最 优 三 角 剖 分 的 矛 盾 。 定 义 tij， 1ijn为 凸 子 多 边 形 vi-1,vi,vj的 最 优 三 角 剖 分 所对 应 的 权 函 数 值 ， 即 其 最 优 值 。 为

23、 方 便 起 见 ， 设 退 化 的 多 边 形vi-1,vi具 有 权 值 0。 据 此 定 义 ， 要 计 算 的 凸 (n+1)边 形 P的 最 优 权值 为 t1n。tij的 值 可 以 利 用 最 优 子 结 构 性 质 递 归 地 计 算 。 当 j-i1时 ， 凸子 多 边 形 至 少 有 3个 顶 点 。 由 最 优 子 结 构 性 质 ， tij的 值 应 为tik的 值 加 上 tk+1j的 值 ， 再 加 上 三 角 形 vi-1vkvj的 权 值 ， 其 中ikj-1。 由 于 在 计 算 时 还 不 知 道 k的 确 切 位 置 ， 而 k的 所 有 可 能位 置 只

24、 有 j-i个 ， 因 此 可 以 在 这 j-i个 位 置 中 选 出 使 tij值 达 到 最 小的 位 置 。 由 此 ， tij可 递 归 地 定 义 为 ： ji jivvvwjktkitjit jkijki )(1min 0 1 多 边 形 游 戏 是 一 个 单 人 玩 的 游 戏 ， 开 始 时 有 一 个 由 n个 顶 点构 成 的 多 边 形 。 每 个 顶 点 被 赋 予 一 个 整 数 值 ， 每 条 边 被 赋 予 一个 运 算 符 “ +”或 “ *” 。 所 有 边 依 次 用 整 数 从 1到 n编 号 。游 戏 第 1步 ， 将 一 条 边 删 除 。随 后

25、n-1步 按 以 下 方 式 操 作 ：(1)选 择 一 条 边 E以 及 由 E连 接 着 的 2个 顶 点 V1和 V2；(2)用 一 个 新 的 顶 点 取 代 边 E以 及 由 E连 接 着 的 2个 顶 点 V1和 V2。将 由 顶 点 V1和 V2的 整 数 值 通 过 边 E上 的 运 算 得 到 的 结 果 赋 予 新 顶点 。最 后 ， 所 有 边 都 被 删 除 ， 游 戏 结 束 。 游 戏 的 得 分 就 是 所 剩 顶点 上 的 整 数 值 。问 题 :对 于 给 定 的 多 边 形 ， 计 算 最 高 得 分 。 在 所 给 多 边 形 中 ， 从 顶 点 i(1i

26、n)开 始 ， 长 度 为 j(链 中 有 j个 顶 点 )的 顺 时 针 链 p(i， j) 可 表 示 为 vi， opi+1， ， vi+j-1。如 果 这 条 链 的 最 后 一 次 合 并 运 算 在 opi+s处 发 生 (1sj-1)， 则可 在 opi+s处 将 链 分 割 为 2个 子 链 p(i， s)和 p(i+s， j-s)。设 m1是 对 子 链 p(i， s)的 任 意 一 种 合 并 方 式 得 到 的 值 ， 而 a和 b分 别 是 在 所 有 可 能 的 合 并 中 得 到 的 最 小 值 和 最 大 值 。 m2是 p(i+s，j-s)的 任 意 一 种 合

27、 并 方 式 得 到 的 值 ， 而 c和 d分 别 是 在 所 有 可 能 的合 并 中 得 到 的 最 小 值 和 最 大 值 。 依 此 定 义 有 am1b， cm2d(1)当 opi+s=+时 ， 显 然 有 a+cmb+d(2)当 opi+s=*时 ， 有 minac， ad， bc， bdmmaxac， ad，bc， bd 换 句 话 说 ， 主 链 的 最 大 值 和 最 小 值 可 由 子 链 的 最 大 值 和 最 小 值得 到 。 图 象 的 变 位 压 缩 存 储 格 式 将 所 给 的 象 素 点 序 列p1,p2,pn,0pi255分 割 成 m个 连 续 段 S1

28、,S2,Sm。 第 i个 象素 段 Si中 (1im)， 有 li个 象 素 ,且 该 段 中 每 个 象 素 都 只 用 bi位表 示 。 设 则 第 i个 象 素 段 Si为设 ， 则 hibi8。 因 此 需 要 用 3位 表 示 bi,如 果 限 制 1li255， 则 需 要 用 8位 表 示 li。 因 此 ， 第 i个 象 素段 所 需 的 存 储 空 间 为 li*bi+11位 。 按 此 格 式 存 储 象 素 序 列p1,p2,pn， 需 要 位 的 存 储 空 间 。 图 象 压 缩 问 题 要 求 确 定 象 素 序 列 p1,p2, ,pn的 最 优 分 段 ，使 得

29、 依 此 分 段 所 需 的 存 储 空 间 最 少 。 每 个 分 段 的 长 度 不 超 过256位 。 11 ik klit , 1 ilititi ppS 1maxlog 1 kilitkiti ph mibil mi 11*1 设 li， bi (1i m )， 是 p1,p2,pn的 最 优 分 段 。 显 而 易 见 ， l1，b1是 p1,pl1的 最 优 分 段 ， 且 li， bi (2i m ) ， 是 pl1+1,pn的 最 优 分 段 。 即 图 象 压 缩 问 题 满 足 最 优 子 结 构 性 质 。设 si， 1in， 是 象 素 序 列 p1,pn的 最 优

30、分 段 所 需 的 存 储 位 数 。由 最 优 子 结 构 性 质 易 知 ：其 中 11),1max(b*min 256,min1 ikikkisis ik 1maxlog),bmax( kjki pji算 法 复 杂 度 分 析 ：由 于 算 法 compress中 对 k的 循 环 次 数 不 超 这 256， 故 对每 一 个 确 定 的 i， 可 在 时 间 O(1)内 完 成 的 计 算 。 因 此 整个 算 法 所 需 的 计 算 时 间 为 O(n)。 在 一 块 电 路 板 的 上 、 下 2端 分 别 有 n个 接 线 柱 。 根 据 电 路 设 计 ，要 求 用 导 线

31、 (i,(i)将 上 端 接 线 柱 与 下 端 接 线 柱 相 连 ， 如 图 所 示 。其 中 (i)是 1,2,n的 一 个 排 列 。 导 线 (i,(i)称 为 该 电 路 板 上的 第 i条 连 线 。 对 于 任 何 1i(j)。电 路 布 线 问 题 要 确 定 将 哪 些 连 线 安 排 在 第 一 层 上 ， 使 得 该 层 上有 尽 可 能 多 的 连 线 。 换 句 话 说 ， 该 问 题 要 求 确 定 导 线 集Nets=(i,(i),1in的 最 大 不 相 交 子 集 。 记 。 N(i,j)的 最 大 不 相 交 子集 为 MNS(i,j)。 Size(i,j

32、)=|MNS(i,j)|。(1)当 i=1时 ，(2)当 i1时 ，2.1 j(i)。 此 时 ， 。 故 在 这 种 情 况 下 ，N(i,j)=N(i-1,j)， 从 而 Size(i,j)=Size(i-1,j)。2.2 j(i)， (i,(i) MNS(i,j) 。 则 对 任 意 (t,(t) MNS(i,j)有ti且 (t)(i)。 在 这 种 情 况 下 MNS(i,j)-(i,(i)是 N(i-1,(i)-1)的 最 大 不 相 交 子 集 。 2.3 若 ， 则 对 任 意 (t,(t) MNS(i,j)有 t1时 )1(1 )1(0),1( jjjSize )( )(1)1

33、)(,1(),1(max ),1(),( ij ijiiSizejiSize jiSizejiSize n个 作 业 1， 2， ， n要 在 由 2台 机 器 M1和 M2组 成 的 流 水 线 上完 成 加 工 。 每 个 作 业 加 工 的 顺 序 都 是 先 在 M1上 加 工 ， 然 后 在M2上 加 工 。 M1和 M2加 工 作 业 i所 需 的 时 间 分 别 为 ai和 bi。流 水 作 业 调 度 问 题 要 求 确 定 这 n个 作 业 的 最 优 加 工 顺 序 ， 使 得 从第 一 个 作 业 在 机 器 M1上 开 始 加 工 ， 到 最 后 一 个 作 业 在 机

34、 器 M2上加 工 完 成 所 需 的 时 间 最 少 。分 析 ：直 观 上 ， 一 个 最 优 调 度 应 使 机 器 M1没 有 空 闲 时 间 ， 且 机 器M2的 空 闲 时 间 最 少 。 在 一 般 情 况 下 ， 机 器 M2上 会 有 机 器 空 闲和 作 业 积 压 2种 情 况 。设 全 部 作 业 的 集 合 为 N=1， 2， ， n。 SN是 N的 作 业 子集 。 在 一 般 情 况 下 ， 机 器 M1开 始 加 工 S中 作 业 时 ， 机 器 M2还在 加 工 其 它 作 业 ， 要 等 时 间 t后 才 可 利 用 。 将 这 种 情 况 下 完 成S中

35、作 业 所 需 的 最 短 时 间 记 为 T(S,t)。 流 水 作 业 调 度 问 题 的 最优 值 为 T(N,0)。 设 是 所 给 n个 流 水 作 业 的 一 个 最 优 调 度 ， 它 所 需 的 加 工 时 间 为 a(1)+T。 其 中 T是 在 机 器 M2的 等 待 时 间 为 b(1)时 ， 安 排 作 业(2)， ， (n)所 需 的 时 间 。记 S=N-(1)， 则 有 T=T(S,b(1)。证 明 ： 事 实 上 ， 由 T的 定 义 知 TT(S,b(1)。 若 TT(S,b(1)，设 是 作 业 集 S在 机 器 M2的 等 待 时 间 为 b(1)情 况

36、下 的 一 个 最 优调 度 。 则 (1)， (2)， ， (n)是 N的 一 个 调 度 ， 且 该 调 度所 需 的 时 间 为 a(1)+T(S,b(1)a(1)+T。 这 与 是 N的 最 优 调 度矛 盾 。 故 TT(S,b(1)。 从 而 T=T(S,b(1)。 这 就 证 明 了 流 水 作业 调 度 问 题 具 有 最 优 子 结 构 的 性 质 。由 流 水 作 业 调 度 问 题 的 最 优 子 结 构 性 质 可 知 ，),(min)0,( 1 iini biNTaNT )0,max,(min),( iiiSi atbiSTatST 对 递 归 式 的 深 入 分 析

37、 表 明 ， 算 法 可 进 一 步 得 到 简 化 。设 是 作 业 集 S在 机 器 M2的 等 待 时 间 为 t时 的 任 一 最 优 调 度 。 若(1)=i, (2)=j。 则 由 动 态 规 划 递 归 式 可 得 :T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其 中 ， ,max 0,max ,0,maxmax 0,0,maxmax iijiijij ijijij ijijij jiijij abaataabb baatabb baatabb aatbbt 如 果 作 业 i和 j满 足 minbi,aj minbj,ai，

38、则 称 作 业 i和 j满足 Johnson不 等 式 。 交 换 作 业 i和 作 业 j的 加 工 顺 序 ， 得 到 作 业 集 S的 另 一 调 度 ， 它 所需 的 加 工 时 间 为 T(S,t)=ai+aj+T(S-i,j,tji)其 中 ，当 作 业 i和 j满 足 Johnson不 等 式 时 ， 有由 此 可 见 当 作 业 i和 作 业 j不 满 足 Johnson不 等 式 时 ， 交 换 它 们 的加 工 顺 序 后 ， 不 增 加 加 工 时 间 。 对 于 流 水 作 业 调 度 问 题 ， 必 存在 最 优 调 度 ， 使 得 作 业 (i)和 (i+1)满 足

39、 Johnson不 等 式 。 进 一步 还 可 以 证 明 ， 调 度 满 足 Johnson法 则 当 且 仅 当 对 任 意 i2n时 ， 算 法 需 要 (n2n)计 算 时 间 。 由 m(i,j)的 递 归 式 容 易 证 明 ， 在 一 般 情 况 下 ， 对 每 一 个 确 定 的i(1in)， 函 数 m(i,j)是 关 于 变 量 j的 阶 梯 状 单 调 不 减 函 数 。 跳 跃点 是 这 一 类 函 数 的 描 述 特 征 。 在 一 般 情 况 下 ， 函 数 m(i,j)由 其 全部 跳 跃 点 唯 一 确 定 。 如 图 所 示 。对 每 一 个 确 定 的 i

40、(1in)， 用 一 个 表 pi存 储 函 数 m(i， j)的 全 部跳 跃 点 。 表 pi可 依 计 算 m(i， j)的 递 归 式 递 归 地 由 表 pi+1计 算 ，初 始 时 pn+1=(0， 0)。 n=3， c=6， w=4， 3， 2， v=5， 2， 1。x(0,0) m(4,x) x(2,1)m(4,x-2)+1x(0,0) (2,1)m(3,x) (3,2) xm(3,x-3)+2(5,3) x(0,0) (2,1)m(2,x)(3,2) (5,3)xm(2,x-4)+5(4,5) (6,6)(7,7)(9,8) x(0, 0) (2, 1)m(1,x)(3,2)

41、 (5,3)(4,5)(6,6)(7,7) (9,8)x(0,0) (2,1) m(3,x)x (0,0) (2,1)m(2,x)(3,2) (5,3) 函 数 m(i,j)是 由 函 数 m(i+1,j)与 函 数 m(i+1,j-wi)+vi作 max运 算 得到 的 。 因 此 ， 函 数 m(i,j)的 全 部 跳 跃 点 包 含 于 函 数 m(i+1， j)的 跳跃 点 集 pi+1与 函 数 m(i+1， j-wi)+vi的 跳 跃 点 集 qi+1的 并 集 中 。易 知 ， (s,t)qi+1当 且 仅 当 wisc且 (s-wi,t-vi)pi+1。 因 此 ，容 易 由

42、pi+1确 定 跳 跃 点 集 qi+1如 下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另 一 方 面 ， 设 (a， b)和 (c， d)是 pi+1qi+1中 的 2个 跳 跃 点 ，则 当 ca且 db时 ， (c， d)受 控 于 (a， b)， 从 而 (c， d)不 是 pi中的 跳 跃 点 。 除 受 控 跳 跃 点 外 ， pi+1qi+1中 的 其 它 跳 跃 点 均为 pi中 的 跳 跃 点 。由 此 可 见 ， 在 递 归 地 由 表 pi+1计 算 表 pi时 ， 可 先 由 pi+1计算 出 qi+1， 然 后 合

43、 并 表 pi+1和 表 qi+1， 并 清 除 其 中 的 受 控跳 跃 点 得 到 表 pi。 n=5， c=10， w=2， 2， 6， 5， 4， v=6， 3， 5， 4， 6。初 始 时 p6=(0,0)， (w5,v5)=(4,6)。 因 此 ，q6=p6(w5,v5)=(4,6)。p5=(0,0),(4,6)。q5=p5(w4,v4)=(5,4),(9,10)。 从 跳 跃 点 集 p5与 q5的 并 集p5q5=(0,0),(4,6),(5,4),(9,10)中 看 到 跳 跃 点 (5,4)受 控 于 跳跃 点 (4,6)。 将 受 控 跳 跃 点 (5,4)清 除 后 ，

44、 得 到p4=(0,0),(4,6),(9,10)q4=p4(6， 5)=(6， 5)， (10， 11)p3=(0， 0)， (4， 6)， (9， 10)， (10， 11)q3=p3(2， 3)=(2， 3)， (6， 9)p2=(0， 0)， (2， 3)， (4， 6)， (6， 9)， (9， 10)， (10， 11)q2=p2(2， 6)=(2， 6)， (4， 9)， (6， 12)， (8， 15)p1=(0， 0)， (2， 6)， (4， 9)， (6， 12)， (8， 15)p1的 最 后 的 那 个 跳 跃 点 (8,15)给 出 所 求 的 最 优 值 为 m(

45、1,c)=15。 上 述 算 法 的 主 要 计 算 量 在 于 计 算 跳 跃 点 集pi(1in)。 由 于 qi+1=pi+1(wi， vi)， 故 计 算qi+1需 要 O(|pi+1|)计 算 时 间 。 合 并 pi+1和qi+1并 清 除 受 控 跳 跃 点 也 需 要 O(|pi+1|)计 算 时间 。 从 跳 跃 点 集 pi的 定 义 可 以 看 出 ， pi中 的 跳跃 点 相 应 于 xi,xn的 0/1赋 值 。 因 此 ， pi中 跳 跃点 个 数 不 超 过 2n-i+1。 由 此 可 见 ， 算 法 计 算 跳 跃 点集 pi所 花 费 的 计 算 时 间 为从

46、 而 ， 改 进 后 算 法 的 计 算 时 间 复 杂 性 为 O(2n)。 当所 给 物 品 的 重 量 wi(1in)是 整 数 时 ， |pi|c+1，(1in)。 在 这 种 情 况 下 ， 改 进 后 算 法 的 计 算 时 间复 杂 性 为 O(minnc,2 n)。 nni inni OOipO 22|1| 22 n 二 叉 搜 索 树（ 1） 若 它 的 左 子 树 不 空 ， 则 左 子 树 上 所 有 节 点 的 值 均 小 于 它 的 根 节 点 的 值 ；（ 2） 若 它 的 右 子 树 不 空 ， 则 右 子 树 上 所 有 节 点 的 值 均 大 于 它 的 根

47、节 点 的 值 ；（ 3 它 的 左、右 子 树 也 分 别 为 二 叉 排 序 树 4512 533 3724 10061 9078在 随 机 的 情 况 下 ， 二 叉 查 找 树 的 平 均 查 找 长 度和 是 等 数 量 级 的nlog n 查 找 成 功 与 不 成 功 的 概 率n 二 查 找 树 的 期 望 耗 费 n 有 个 节 点 的 二 叉 树 的 个 数 为 ：n 穷 举 搜 索 法 的 时 间 复 杂 度 为 指 数 级11 0 ni ni ii qp ni iiTni iiT ni iiTni iiT qdpk qdpk TE 01 01 )(depth)(dept

48、h1 )1)(depth()1)(depth( ) incost search( n )/4( 2/3nn 0d 1d 2d 3d 4d 5d1k 2k3k 4k 5k 2.80 Total 0.40 0.10 3 0.20 0.05 3 0.20 0.05 3 0.20 0.05 3 0.30 0.10 2 0.15 0.05 2 0.60 0.20 2 0.20 0.10 1 0.15 0.05 2 0.10 0.10 0 0.30 0.15 1 oncontributiy probabilit depth node 54321 05 4321ddddddkkkkk0d 1d 2d 3d

49、4d 5d1k 2k 3k 4k 5k 最 优 二 叉 搜 索 树 Tij的 平 均 路 长 为 pij， 则 所 求 的 最 优 值 为 p1,n。由 最 优 二 叉 搜 索 树 问 题 的 最 优 子 结 构 性 质 可 建 立 计 算 pij的 递归 式 如 下记 wi,jpi,j为 m(i,j)， 则 m(1,n)=w1,np1,n=p1,n为 所 求 的 最 优 值 。 计算 m(i,j)的 递 归 式 为注 意 到 ，可 以 得 到 O(n 2)的 算 法 min ,1,11,1, jkjkkikijkijijiji pwpwwpw niiim jijkmkimwjim jkiji 1,0)1,( ),1()1,(min),( , ),1()1,(min),1()1,(min 11 jkmkimjkmkim jiskjisjki 课后作业n习题 3-1，3-2，3-3，3-4，3-5，3-6，3-9