动态规划详解讲稿.ppt

《动态规划详解讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划详解讲稿.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划详解动态规划详解动态规划详解动态规划详解第一页，讲稿共三十四页哦动态规划概述 动态规划概述动态规划概述动态规划概述动态规划概述动态规划动态规划动态规划动态规划（Dynamic ProgrammingDynamic Programming），在），在），在），在20 20 世纪世纪世纪世纪5050年代由美国数学家年代由美国数学家年代由美国数学家年代由美国数学家Richard BellmanRichard Bellman（理查德（理查德（理查德（理查德 .贝尔曼）发明，作为贝尔曼）发明，作为贝尔曼）发明，作为贝尔曼）发明，作为多阶段决策过程最优化多阶段决策过程最优化多阶段决策过程最优化多阶

2、段决策过程最优化的一种通用方法，对最优化问题提出的一种通用方法，对最优化问题提出的一种通用方法，对最优化问题提出的一种通用方法，对最优化问题提出最优性原则最优性原则最优性原则最优性原则，从而创建最优化问题，从而创建最优化问题，从而创建最优化问题，从而创建最优化问题的一种新算法设计技术的一种新算法设计技术的一种新算法设计技术的一种新算法设计技术动态规划，它是一种重要的应用数学工具。动态规划，它是一种重要的应用数学工具。动态规划，它是一种重要的应用数学工具。动态规划，它是一种重要的应用数学工具。至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，至少在计算机科学圈子里，人们不仅用它解决特

3、定类型的最优化问题，至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题，而最终把它作为一种而最终把它作为一种而最终把它作为一种而最终把它作为一种通用的通用的通用的通用的算法设计技术，即包括某些非最优化问题。算法设计技术，即包括某些非最优化问题。算法设计技术，即包括某些非最优化问题。算法设计技术，即包括某些非最优化问题。多阶段决策过程最优化多阶段决策过程最优化多阶段决策过程最优化多阶段决策过程最优化：现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。现

4、实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出复杂度很高、计算量很大的问题（如求最佳子集的组合问题

5、），要找出一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了降低求解问题的难度，把求解过程分为降低求解问题的难度，把求解过程分为降低求解问题的难度，把求解过程分为降低求解问题的难度，把求解过程分为一系列阶段一系列阶段一系列阶段一系列阶段，各个阶段依次按照，各个阶段依次按照，各个阶段依次按照，各个阶段依次按照最优性原则计算，最后阶段计算得到最优性原则计算，最后阶段计算得到最优性原则计算，最后阶段计算得

6、到最优性原则计算，最后阶段计算得到最优解最优解最优解最优解。包括。包括。包括。包括 分段分段分段分段、求解求解求解求解 两大步。两大步。两大步。两大步。注：不能段化的问题不能用动态规划法求解。注：不能段化的问题不能用动态规划法求解。注：不能段化的问题不能用动态规划法求解。注：不能段化的问题不能用动态规划法求解。第二页，讲稿共三十四页哦最优性原则阶段阶段阶段阶段 1 1阶段阶段阶段阶段 2 2.阶段阶段阶段阶段 n n求解算法求解算法求解算法求解算法求解算法求解算法求解算法求解算法求解算法求解算法求解算法求解算法动态的含义动态的含义动态的含义动态的含义：求解算法施加的状态是变化的。：求解算法施加

7、的状态是变化的。当前状态只与其直接前趋状态有关，对其直接当前状态只与其直接前趋状态有关，对其直接前趋状态施加求解算法，成为当前状态。前趋状态施加求解算法，成为当前状态。最优性原则最优性原则最优性原则最优性原则 (Principle of Optimality)：一个最优问题一个最优问题一个最优问题一个最优问题任何实例任何实例任何实例任何实例的最优解，是由该实例的最优解，是由该实例的最优解，是由该实例的最优解，是由该实例的的的的子实例子实例子实例子实例的最优解组成的。的最优解组成的。的最优解组成的。的最优解组成的。对特定问题该原则对特定问题该原则不一定满足（罕见），有必要检查其适用性。不一定满足

8、（罕见），有必要检查其适用性。子实例组成父实例，父实例分解为子实例。子实例组成父实例，父实例分解为子实例。对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波那契序列的动态规划算法，它们属于非最优化问题的动态规划法。那契序列的动态规划算法，它们属于非最优化问题的动态规划法。动态规划法的特点动态规划法的特点动态规划法的特点动态规划法的特点：1.分阶段（级）决策。对最优化问题，用最优性原则设计。分

9、阶段（级）决策。对最优化问题，用最优性原则设计。2.一般采用一般采用自顶向下分析自顶向下分析自顶向下分析自顶向下分析（规模减小），（规模减小），自底向上计算自底向上计算自底向上计算自底向上计算（规模增加）。（规模增加）。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。第三页，讲稿共三十四页哦数塔 数塔数塔数塔数塔问题问题问题问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上设有一三角形数塔如图。求一条

10、自塔顶到塔底的路径，该路径上 节点值之和最大节点值之和最大节点值之和最大节点值之和最大。分段分段分段分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。无法分段的问题，不能用动态规划法求解。无法分段的问题，不能用动态规划法求解。无法分段的问题，不能用动态规划法求解。无法分段的问题，不能用动态规划法求解。求解求解求解求解：动态规划法求解。自底向上计算，各实例计算满足最优性原则，：动态规划法求解。自底向上计算，各实例

11、计算满足最优性原则，：动态规划法求解。自底向上计算，各实例计算满足最优性原则，：动态规划法求解。自底向上计算，各实例计算满足最优性原则，如实例如实例如实例如实例1818的子实例为的子实例为的子实例为的子实例为1212和和和和7 7，max(12+6,7+6)=18max(12+6,7+6)=18。5 5 级级级级4 4 级级级级3 3 级级级级2 2 级级级级1 1级级级级18 27 39 3218 27 39 3267 46 6567 46 6578 7378 739191131311118 87 740401414262615158 824246 67 7131312121111第四页，讲

12、稿共三十四页哦数塔问题：动态规划法与穷举法效率比较vv 数塔：动态规划法与穷举法的时间效率比较数塔：动态规划法与穷举法的时间效率比较数塔：动态规划法与穷举法的时间效率比较数塔：动态规划法与穷举法的时间效率比较w w输入规模输入规模输入规模输入规模：为便于分析，选择数塔层数：为便于分析，选择数塔层数：为便于分析，选择数塔层数：为便于分析，选择数塔层数k(k0)k(k0)；w w基本操作基本操作基本操作基本操作：节点值求和运算；：节点值求和运算；：节点值求和运算；：节点值求和运算；增长函数增长函数增长函数增长函数：加法次数与：加法次数与：加法次数与：加法次数与 k k 的关系；的关系；的关系；的关

13、系；w w效率类别效率类别效率类别效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底）：没有最佳、最差情况；（都要从塔顶计算到塔底）：没有最佳、最差情况；（都要从塔顶计算到塔底）：没有最佳、最差情况；（都要从塔顶计算到塔底）w w增长率（次数）增长率（次数）增长率（次数）增长率（次数）：各层节点数升序：各层节点数升序：各层节点数升序：各层节点数升序：1,2,3,4,1,2,3,4,5 5,6,7,8,9,10,.,6,7,8,9,10,.节点总数节点总数节点总数节点总数 n n 升序：升序：升序：升序：1,3,6,10,1,3,6,10,1515,21,28,36,45,55,.,21,28

14、,36,45,55,.层数层数层数层数k k（顶为（顶为（顶为（顶为1 1）：）：）：）：1,2,3,4,1,2,3,4,5 5,6,7,8,9,10,.,6,7,8,9,10,.路径总数路径总数路径总数路径总数 t t 升序：升序：升序：升序：2,2,4,8,4,8,1616,32,.,t=,32,.,t=2 2k-1k-1,k1,k11.1.穷举法穷举法穷举法穷举法：T(k)=(k-1)2T(k)=(k-1)2k-1k-1，k1 k1 （指数级指数级指数级指数级）本例本例本例本例k=5k=5，每条路径上，每条路径上，每条路径上，每条路径上5 5个节点做个节点做个节点做个节点做4 4次加法，

15、共次加法，共次加法，共次加法，共6464次加法。次加法。次加法。次加法。2.2.动态规划法动态规划法动态规划法动态规划法：（：（：（：（层节点数层节点数层节点数层节点数 =层数层数层数层数）自底向上计算，自底向上计算，自底向上计算，自底向上计算，k k层加法总数为层加法总数为层加法总数为层加法总数为k-1k-1层节点数层节点数层节点数层节点数22，有效率计算式：，有效率计算式：，有效率计算式：，有效率计算式：T(k)=2(k-1+.+3+2+1)=k(k-1),k1 T(k)=2(k-1+.+3+2+1)=k(k-1),k1 （平方级平方级平方级平方级）本例加法总数本例加法总数本例加法总数本例

16、加法总数 2(4+3+2+1)=202(4+3+2+1)=20次，比次，比次，比次，比6464次少很多。次少很多。次少很多。次少很多。第五页，讲稿共三十四页哦非最优化问题实例 非最优化问题实例非最优化问题实例非最优化问题实例非最优化问题实例vv 求中国象棋马的路径求中国象棋马的路径求中国象棋马的路径求中国象棋马的路径 问题问题问题问题：在：在：在：在mnmn棋盘上，求马从棋盘上，求马从棋盘上，求马从棋盘上，求马从P P点跳到点跳到点跳到点跳到QQ点的所有路径。点的所有路径。点的所有路径。点的所有路径。6 5 4 3 2 16 5 4 3 2 16 5 4 3 2 16 5 4 3 2 16 5

17、 4 3 2 16 5 4 3 2 1可用回溯法和递归法求解，可用回溯法和递归法求解，可用回溯法和递归法求解，可用回溯法和递归法求解，但递归法效率但递归法效率但递归法效率但递归法效率很低，栈空间占用很大。很低，栈空间占用很大。很低，栈空间占用很大。很低，栈空间占用很大。第六页，讲稿共三十四页哦最小代价子母树 最小代价子母树最小代价子母树最小代价子母树最小代价子母树 问题：问题：问题：问题：n(n1)n(n1)堆沙子，重量向量堆沙子，重量向量堆沙子，重量向量堆沙子，重量向量 W=(wW=(w1 1,.w,.wn n)。要将它们归并为。要将它们归并为。要将它们归并为。要将它们归并为1 1堆，堆，堆

18、，堆，归并规则：每次只能将相邻归并规则：每次只能将相邻归并规则：每次只能将相邻归并规则：每次只能将相邻2 2堆归并为堆归并为堆归并为堆归并为1 1堆，经过堆，经过堆，经过堆，经过 n-1 n-1 次归并后，次归并后，次归并后，次归并后，最终归并为一堆。总代价为归并过程中最终归并为一堆。总代价为归并过程中最终归并为一堆。总代价为归并过程中最终归并为一堆。总代价为归并过程中新产生的新产生的新产生的新产生的沙堆质量之和，沙堆质量之和，沙堆质量之和，沙堆质量之和，这个代价最小的归并树称为最小代价子母树。这个代价最小的归并树称为最小代价子母树。这个代价最小的归并树称为最小代价子母树。这个代价最小的归并树

19、称为最小代价子母树。分析分析分析分析：属于最优化问题，目标为总代价最小。：属于最优化问题，目标为总代价最小。：属于最优化问题，目标为总代价最小。：属于最优化问题，目标为总代价最小。分段分段分段分段：显然需要：显然需要：显然需要：显然需要 n-1 n-1 次归并才能将次归并才能将次归并才能将次归并才能将 n n 堆归并为堆归并为堆归并为堆归并为 1 1 堆。自然地可以将每次堆。自然地可以将每次堆。自然地可以将每次堆。自然地可以将每次 归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。归并划分为一个阶段，成为多阶段决策问题，尝试动态规划

20、法。归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。求解求解求解求解：（此处采用：（此处采用：（此处采用：（此处采用自底向上自底向上自底向上自底向上的分析，找规律较简洁）的分析，找规律较简洁）的分析，找规律较简洁）的分析，找规律较简洁）当当当当 n=2 n=2 时：仅一种归并法即时：仅一种归并法即时：仅一种归并法即时：仅一种归并法即2 2合合合合1 1。当当当当 n=3 n=3 时：有时：有时：有时：有2 2种归并方法，第一种归并方法如图，种归并方法，第一种归并方法如图，种归并方法，第一种归并方法如图，种归并方法，第一种归并方法如图，前前前前1 1堆堆堆堆后后后后2 2堆。堆。堆。堆。

21、13137 78 815152828f(i,j)从第从第 i 堆到第堆到第 j 堆的代价和。堆的代价和。g(i,j)从第从第 i 堆到第堆到第 j 堆的重量和。堆的重量和。f(1,3)=15+28=4343（最优结果）（最优结果）=f(2 2,3 3)+g(1 1,3)序号序号序号序号 1 1 2 3 2 33 3级级级级2 2级级级级1 1级级级级13137 78 8161621214 41818第七页，讲稿共三十四页哦最小代价子母树(续1)n=4n=3n=3时：第二种归并方法，时：第二种归并方法，时：第二种归并方法，时：第二种归并方法，前前前前2 2堆堆堆堆后后后后1 1堆。堆。堆。堆。n

22、=4时：有时：有3大类归并法。大类归并法。前前前前1 1堆堆堆堆后后3堆、堆、前前前前2 2堆堆堆堆后后2堆、堆、前前前前3 3堆堆堆堆后后1堆。堆。因因3堆有堆有2种归并法，所以一共种归并法，所以一共5小类归并法。小类归并法。前前前前1 1堆堆堆堆第第1种情况：种情况：7 78 8161631311515序号序号序号序号 1 1 2 3 4 2 3 413134444f(1,4)=15+31+44=9090 =f(2,4)f(2,4)+g(1,4)w不变不变 =f(2 2,3 3)+g(2,4 4)+g(1 1,4)若若f(2,4)越小，则越小，则f(1,4)就越小。就越小。13137 78

23、 820202828f(i,j)从第从第 i 堆到第堆到第 j 堆的代价和。堆的代价和。g(i,j)从第从第 i 堆到第堆到第 j 堆的重量和。堆的重量和。f(1,3)=20+28=4848 =f(1 1,2 2)+g(1,3 3)序号序号序号序号 1 1 2 3 2 33 3级级级级2 2级级级级1 1级级级级4 4级级级级3 3级级级级2 2级级级级1 1级级级级第八页，讲稿共三十四页哦最小代价子母树(续2)n=4n=4 n=4 时：前时：前时：前时：前1 1堆的第堆的第堆的第堆的第2 2种情况。种情况。种情况。种情况。7 78 816162424313113134444序号序号序号序号

24、1 1 2 3 4 2 3 4f(1,4)=24+31+44=9999 =f(2,4)f(2,4)+g(1,4)w不变不变 =f(3 3,4 4)+g(2 2,4)+g(1 1,4)若若f(2,4)越小，则越小，则f(1,4)就越小。就越小。n=4 n=4 时：前时：前时：前时：前2 2堆情况。堆情况。堆情况。堆情况。7 78 816162424202013134444序号序号序号序号 1 1 2 3 4 2 3 4f(1,4)=20+24+44=8888 =f(1,2)+f(3,4)f(1,2)+f(3,4)+g(1,4)若若f(1,2)+f(3,4)越小，越小，f(1,4)就越小就越小4

25、4级级级级3 3级级级级2 2级级级级1 1级级级级3 3级级级级2 2级级级级1 1级级级级第九页，讲稿共三十四页哦最小代价子母树(续3)n=4n=4 n=4 时：前时：前时：前时：前3 3堆的第堆的第堆的第堆的第1 1种情况。种情况。种情况。种情况。7 78 816162020282813134444n=4 n=4 时：前时：前时：前时：前3 3堆的第堆的第堆的第堆的第2 2种情况。种情况。种情况。种情况。序号序号序号序号 1 1 2 3 4 2 3 4f(1,4)=20+28+44=9292 =f(1,3)f(1,3)+g(1,4)w不变不变 =f(1 1,2 2)+g(1,3 3)+g

26、(1,4 4)若若f(1,3)越小，则越小，则f(1,4)就越小。就越小。7 78 816161515282813134444序号序号序号序号 1 1 2 3 4 2 3 4f(1,4)=15+28+44=87 87 最优最优最优最优 =f(1,3)f(1,3)+g(1,4)w不变不变 =f(2 2,3 3)+g(1 1,3)+g(1,4 4)若若f(1,3)越小，则越小，则f(1,4)就越小。就越小。4 4级级级级3 3级级级级2 2级级级级1 1级级级级4 4级级级级3 3级级级级2 2级级级级1 1级级级级第十页，讲稿共三十四页哦最小代价子母树(续4)n=4将将将将 n=4 n=4 归纳

27、为归纳为归纳为归纳为 3 3 大类情况：大类情况：大类情况：大类情况：f(1,4)=f(1,4)=minmin f(2,4),f(1,2)+f(3,4),f(1,3)f(2,4),f(1,2)+f(3,4),f(1,3)+g(1,4)+g(1,4)前前前前1 1堆堆堆堆 前前前前2 2堆堆堆堆 前前前前3 3堆堆堆堆将将将将n=4 n=4 计算式推广，对于任意的计算式推广，对于任意的计算式推广，对于任意的计算式推广，对于任意的 n(n1)n(n1)，归纳出如下公式：，归纳出如下公式：，归纳出如下公式：，归纳出如下公式：f(1,n)=f(1,n)=minf(2,n),minf(2,n),f(1,

28、2)+f(3,n)f(1,2)+f(3,n),f(1,3)+f(4,n)f(1,3)+f(4,n),.,f(1,n-1),.,f(1,n-1)+g(1,n)g(1,n)前前前前1 1堆堆堆堆 前前前前2 2堆堆堆堆 前前前前3 3堆堆堆堆 .前前前前n-1n-1堆堆堆堆上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法上式称为动态方程，即用方程给出的动态规划算法。很多动态规划算法不能用方程形式给出，只能是描述性的。不能用方程形式给出，只能是描述性的。不能用方程

29、形式给出，只能是描述性的。不能用方程形式给出，只能是描述性的。第十一页，讲稿共三十四页哦F(1,n)F(1,n)在在在在(13,7,8,16,21,4,18)(13,7,8,16,21,4,18)上的结果上的结果上的结果上的结果第十二页，讲稿共三十四页哦/w1.n:n/w1.n:n堆沙子的质量序列堆沙子的质量序列堆沙子的质量序列堆沙子的质量序列/g1.n;1.n:gi,j=/g1.n;1.n:gi,j=/f1n:1n:fI,j/f1n:1n:fI,j表示第表示第表示第表示第i i层从第层从第层从第层从第j j个位置开始个位置开始个位置开始个位置开始i i堆沙子的最小归并代价堆沙子的最小归并代价

30、堆沙子的最小归并代价堆沙子的最小归并代价,并约定并约定并约定并约定f1,i=0f1,i=0procedure mincpt(w)procedure mincpt(w)beginbegin 计算计算计算计算gi,j=gj,i=gi,j=gj,i=fi,j fi,j 0(1 i n,1 j n);0(1 i n,1 j n);for for i 2 to ni 2 to n do do /i/i表示层次表示层次表示层次表示层次,也是归并沙子的堆数也是归并沙子的堆数也是归并沙子的堆数也是归并沙子的堆数,在上图中在上图中在上图中在上图中,表示行号表示行号表示行号表示行号 for for j 1 to

31、n-i+1j 1 to n-i+1 do do/表示列号表示列号表示列号表示列号 beginbegin min fi-1,j;min fi-1,j;for k i-1 step-1 untill 1for k i-1 step-1 untill 1 do do if if minfk,j+fi-k,j+kminfk,j+fi-k,j+k then then /min f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)/min f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)min fk,j+fi-k,j+k;min fk,j+fi-k,j+k;fi

32、,j gj,i+j-1+min;fi,j gj,i+j-1+min;end;end;return(fn,1);return(fn,1);endp;endp;第十三页，讲稿共三十四页哦递推求解中的交叠子问题vv 递推求解中的交叠子问题递推求解中的交叠子问题递推求解中的交叠子问题递推求解中的交叠子问题 （非最优化问题）（非最优化问题）（非最优化问题）（非最优化问题）实例实例实例实例：计算裴波那契数的递归版本。：计算裴波那契数的递归版本。：计算裴波那契数的递归版本。：计算裴波那契数的递归版本。递推式：递推式：递推式：递推式：n 1 n 1，F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+

33、F(n-2)F(0)=0,F(1)=1 F(0)=0,F(1)=1例如，例如，例如，例如，F(5)F(5)计算过程用计算过程用计算过程用计算过程用 递归树递归树递归树递归树 表示：表示：表示：表示：F(5)F(5)F(4)F(4)F(3)F(3)F(2)F(2)F(3)F(3)F(1)F(1)F(2)F(2)F(1)F(1)F(0)F(0)F(0)F(0)F(1)F(1)F(2)F(2)F(1)F(1)F(0)F(0)F(1)F(1)树中可以看出，计算树中可以看出，计算树中可以看出，计算树中可以看出，计算F(5)F(5)时要重复计算时要重复计算时要重复计算时要重复计算F(2)F(2)、F(3)

34、F(3)显然降低时间效率。此即交叠子问题，显然降低时间效率。此即交叠子问题，显然降低时间效率。此即交叠子问题，显然降低时间效率。此即交叠子问题，F(5)F(5)分为分为分为分为两个子问题两个子问题两个子问题两个子问题 F(4)F(4)和和和和 F(3)F(3)，F(4)F(4)包含了包含了包含了包含了F(3)F(3)。动态规划法：自底向上计算动态规划法：自底向上计算依次计算依次计算F(0),F(1),F(2),.,F(n)一次一次一次一次，各次计算结果存入数组，各次计算结果存入数组，最后一个元素就是最后一个元素就是F(n)。用一个。用一个单循环即可简单实现。单循环即可简单实现。第十四页，讲稿共

35、三十四页哦单起点最短路径问题 单起点最短路径问题单起点最短路径问题单起点最短路径问题单起点最短路径问题 （区别于完全最短路径问题）（区别于完全最短路径问题）（区别于完全最短路径问题）（区别于完全最短路径问题）概念概念概念概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点 的最短路径，此即单起点（单源）最短路径问题。的最短路径，此即单起点（单源）最短路径问题。的最短路径，此即单起点（单源）最短路径问题。的最短路径

36、，此即单起点（单源）最短路径问题。完全最短路径完全最短路径完全最短路径完全最短路径 问题问题问题问题要求找到从要求找到从要求找到从要求找到从每个顶点每个顶点每个顶点每个顶点到其他到其他到其他到其他所有顶点所有顶点所有顶点所有顶点之间的最短路径。之间的最短路径。之间的最短路径。之间的最短路径。分段分段分段分段：顶点集分为顶点集分为顶点集分为顶点集分为k k个不相交子集个不相交子集个不相交子集个不相交子集V Vd d ,1dk,k2,1dk,k2,级内顶点不相邻。级内顶点不相邻。级内顶点不相邻。级内顶点不相邻。任一条边任一条边任一条边任一条边 (u,v)(u,v)，u u V Vd d，v v V

37、 Vd+md+m，m1m1。令。令。令。令|V|V1 1|=|V|=|Vk k|=1|=1。从源点到收从源点到收从源点到收从源点到收点依次编号点依次编号点依次编号点依次编号V V1 1V V2 2V V3 3V V4 4V V5 51 12 23 34 45 56 67 78 89 91010分级分级分级分级 k=1 k=2 k=3 k=4 k=5k=1 k=2 k=3 k=4 k=5图示求解过程：红色数字为实例求解结果（最优性原则）图示求解过程：红色数字为实例求解结果（最优性原则）图示求解过程：红色数字为实例求解结果（最优性原则）图示求解过程：红色数字为实例求解结果（最优性原则）本本本本例例

38、例例：带带带带权权权权有有有有向向向向图图图图源源源源点点点点收收收收点点点点计算方向计算方向计算方向计算方向8 84 4121210108 81919171713131616第十五页，讲稿共三十四页哦对于一个有对于一个有对于一个有对于一个有k k级的动态规划级的动态规划级的动态规划级的动态规划,需要列出从需要列出从需要列出从需要列出从s s到到到到t t的每一条路上的的每一条路上的的每一条路上的的每一条路上的k-k-2 2次判定结果次判定结果次判定结果次判定结果.其中第其中第其中第其中第i i级判定是利用最优化原理级判定是利用最优化原理级判定是利用最优化原理级判定是利用最优化原理 确定确定确

39、定确定V Vi+1i+1中的哪一中的哪一中的哪一中的哪一个顶点在可能得到的最佳线路上个顶点在可能得到的最佳线路上个顶点在可能得到的最佳线路上个顶点在可能得到的最佳线路上.设设设设D(i,j)D(i,j)是从顶点集是从顶点集是从顶点集是从顶点集V Vi i中的点中的点中的点中的点j j到到到到t t的一条最小耗费路线的一条最小耗费路线的一条最小耗费路线的一条最小耗费路线,cost(i,j),cost(i,j)是这条路线的耗费是这条路线的耗费是这条路线的耗费是这条路线的耗费.由后向前推算由后向前推算由后向前推算由后向前推算,得得得得:cost(i,j)=minC(j,l)+cost(i+1,l)c

40、ost(i,j)=minC(j,l)+cost(i+1,l)C(j,l):C(j,l):表示顶点集表示顶点集表示顶点集表示顶点集V Vi i中的顶点中的顶点中的顶点中的顶点j j到顶点集到顶点集到顶点集到顶点集V Vi+1i+1中的点中的点中的点中的点l l的耗费的耗费的耗费的耗费cost(i+1,l):cost(i+1,l):表示顶点集表示顶点集表示顶点集表示顶点集V Vi+1i+1中的点中的点中的点中的点l l到目标点到目标点到目标点到目标点t t的耗费的耗费的耗费的耗费第十六页，讲稿共三十四页哦cost(3,5)=min(4+cost(4,8),8+cost(4,9)=cost(3,5)

41、=min(4+cost(4,8),8+cost(4,9)=min(4+8,8+4)=12 min(4+8,8+4)=12/第三层中第三层中第三层中第三层中,顶点顶点顶点顶点5 5到终点的耗费到终点的耗费到终点的耗费到终点的耗费cost(3,6)=min(9+cost(4,8),6+cost(4,9)=cost(3,6)=min(9+cost(4,8),6+cost(4,9)=min(9+8,6+4)=10 min(9+8,6+4)=10/取顶点取顶点取顶点取顶点9 9cost(3,7)=min(5+cost(4,8),4+cost(4,9)=cost(3,7)=min(5+cost(4,8),

42、4+cost(4,9)=min(5+8,4+4)=8 min(5+8,4+4)=8 cost(2,2)=min(10+cost(3,5),9+cost(3,6)=cost(2,2)=min(10+cost(3,5),9+cost(3,6)=min(10+12,9+10)=19 min(10+12,9+10)=19cost(2,3)=min(6+12,7+10,10+8)=17 cost(2,3)=min(6+12,7+10,10+8)=17 cost(2,4)=min(3+10,8+8)=13 cost(2,4)=min(3+10,8+8)=13/取顶点取顶点取顶点取顶点6 6cost(1,1

43、)=min(4+19,2+17,3+13)=16 cost(1,1)=min(4+19,2+17,3+13)=16/取顶点取顶点取顶点取顶点4 4第十七页，讲稿共三十四页哦由由由由cost(1,1)=3+cost(2,4)cost(1,1)=3+cost(2,4)记下结点记下结点记下结点记下结点4 4由由由由cost(2,4)=3+cost(3,6)cost(2,4)=3+cost(3,6)记下结点记下结点记下结点记下结点6 6由由由由cost(3,6)=6+cost(4,9)cost(3,6)=6+cost(4,9)记下结点记下结点记下结点记下结点9 9即即即即D(1,1)=4,D(2,4)

44、=6,D(3,6)=9,D(4,9)=10D(1,1)=4,D(2,4)=6,D(3,6)=9,D(4,9)=10所以得到线路所以得到线路所以得到线路所以得到线路:1,4,6,9,101,4,6,9,10第十八页，讲稿共三十四页哦/最短路径算法最短路径算法输入输入:图的顶点编号表图的顶点编号表,各顶点的邻接表各顶点的邻接表,边的耗费函数边的耗费函数C(i,j)C(i,j)表表.输出输出:从从s s到到t t的一条最小耗费路线及其耗费的一条最小耗费路线及其耗费cost(1,s),cost(1,s),即即cost(1)cost(1)procdure FGRAPHprocdure FGRAPHbeg

45、inbegin for i1 to n do costi 0;for i1 to n do costi 0;for j n-1 step-1 to 1 do for j n-1 step-1 to 1 dobeginbegin 设顶点设顶点r r使使(j,r)(j,r)E,E,且且C(j,r)+costrC(j,r)+costr最小最小;/耗费时间耗费时间(n+E)(n+E)cost jC(j,r)+costr;cost jC(j,r)+costr;Djr Djr;/记下最短路径经历的顶点记下最短路径经历的顶点 End;End;p11;p11;/找最小耗费路线找最小耗费路线pkn;pkn;fo

46、r j2 to k-1 dofor j2 to k-1 dopjDpj-1;pjDpj-1;endp;endp;第十九页，讲稿共三十四页哦最优二叉查找树 最优二叉查找树（最优最优二叉查找树（最优最优二叉查找树（最优最优二叉查找树（最优BSTBST）前面我们已经讲过前面我们已经讲过前面我们已经讲过前面我们已经讲过BSTBST的相关算法及特性，本节介绍什么是最优的相关算法及特性，本节介绍什么是最优的相关算法及特性，本节介绍什么是最优的相关算法及特性，本节介绍什么是最优 BSTBST，以及用动态规划算法来构造以及用动态规划算法来构造以及用动态规划算法来构造以及用动态规划算法来构造 BSTBST。vv

47、 最优最优最优最优 BST BST 概念概念概念概念w w问题的提出问题的提出问题的提出问题的提出：基于统计先验知识，我们可统计出一个数表（集合）中：基于统计先验知识，我们可统计出一个数表（集合）中：基于统计先验知识，我们可统计出一个数表（集合）中：基于统计先验知识，我们可统计出一个数表（集合）中 各元素的各元素的各元素的各元素的查找概率查找概率查找概率查找概率，理解为集合各元素的，理解为集合各元素的，理解为集合各元素的，理解为集合各元素的出现频率出现频率出现频率出现频率。比如中文输入法。比如中文输入法。比如中文输入法。比如中文输入法 字库中各词条（单字、词组等）的字库中各词条（单字、词组等）

48、的字库中各词条（单字、词组等）的字库中各词条（单字、词组等）的先验概率先验概率先验概率先验概率，针对用户习惯可以自动，针对用户习惯可以自动，针对用户习惯可以自动，针对用户习惯可以自动 调整词频调整词频调整词频调整词频所谓动态调频、所谓动态调频、所谓动态调频、所谓动态调频、高频先现高频先现高频先现高频先现原则，以减少用户翻查次数。原则，以减少用户翻查次数。原则，以减少用户翻查次数。原则，以减少用户翻查次数。这就是这就是这就是这就是最优二叉查找树问题最优二叉查找树问题最优二叉查找树问题最优二叉查找树问题：查找过程中键值比较次数最少，或者说：查找过程中键值比较次数最少，或者说：查找过程中键值比较次数

49、最少，或者说：查找过程中键值比较次数最少，或者说 希望希望希望希望用最少的键值比较次数找到每个关键码（键值）用最少的键值比较次数找到每个关键码（键值）用最少的键值比较次数找到每个关键码（键值）用最少的键值比较次数找到每个关键码（键值）。为解决这样的。为解决这样的。为解决这样的。为解决这样的 问题，显然需要对集合的每个元素赋予一个特殊属性问题，显然需要对集合的每个元素赋予一个特殊属性问题，显然需要对集合的每个元素赋予一个特殊属性问题，显然需要对集合的每个元素赋予一个特殊属性 查找概率。查找概率。查找概率。查找概率。w w最优最优最优最优 BSTBST：最优最优最优最优BSTBST整棵树的整棵树的

50、整棵树的整棵树的平均键值比较次数平均键值比较次数平均键值比较次数平均键值比较次数最小。最小。最小。最小。BST BST 好处是查找效率高，好处是查找效率高，好处是查找效率高，好处是查找效率高，平均查找效率属于平均查找效率属于平均查找效率属于平均查找效率属于lognlogn型，最坏为线性（完全不平衡）。型，最坏为线性（完全不平衡）。型，最坏为线性（完全不平衡）。型，最坏为线性（完全不平衡）。第二十页，讲稿共三十四页哦举例说明：解最优BST问题的蛮力策略（穷举法）vv 举例说明：解最优举例说明：解最优举例说明：解最优举例说明：解最优BSTBST问题的蛮力策略（穷举法）问题的蛮力策略（穷举法）问题的