电子课件第5章 动态规划.pdf

第5章 动态规划 第5章 动态规划 CHAPTER • 内容提要 • 动态规划中的基本概念和术语 • 最短路径问题 • 最优化原理与动态规划的基本方程 • 动态规划的典型应用案例 5.1 引例 5.1 引例 例5.1 最短路径问题 下面图5.1表示是一个线路网，连线上的数字表示 两点之间的距离（或费用）。试寻求一条由A到E距 离最短（或费用最省）的路径。 12 B1 C1 3 14 2 10 9 D1 5 6 6 5 A B2 10 C2 E 4 5 1 D2 2 13 8 B3 12 C3 图5.1 10 11 5.1 引例 5.1 引例 如果用穷举法，则从A到E一共有3 ×3 ×2 ＝18条 不同的路径，逐个计算每条路径的长度，总共需要进 行4 ×18＝72次加法计算；对18条路径的长度做两两比 较，找出其中最短的一条，总共要进行18－1＝17次比 较。如果从A到C的站点有k个，则总共有3k －1 ×2条路 径，用穷举法求最短路径总共要进行(k＋1)3k －1 ×2次 加法，作3k －1 ×2 －1次比较。当k的值增加时，需要进 行的加法和比较的次数将迅速增加。例如当k ＝10时， 加法次数为433026次，比较39365次。 5.1 引例 5.1 引例 • 以上这种求从A到E 的最短路径问题，可以转 化为三个性质完全相同，但规模较小的子问 题，即分别求从B 、B 、B 到E 的最短路径问 1 2 3 题。 5.1 引例 5.1 引例 记从B (i ＝1,2,3)到E 的最短路径为S(B ) ， i i 则从A到E 的最短距离S(A)可以表示为： ＋ ＋ AB S (B )  2