[第六章动态规划1.ppt

第六章 动态规划 信工计算机系2008 6.1 资源分配问题 假设资源总数为m份，工程个数为n。给每项工程投 入的资源不同，所获得的利润也不同。要求把总数 为m的资源，分配给n个工程，以获得最大利润分配 方案。 数学描述 假设用函数Gi(k) (1≤i≤n,0≤k≤m)表示将k份资 源分配给工程i获得的利润。 设工程i分配xi份资源。资源分配问题数学描述为： fi(x)的计算 解资源分配问题实例 有8个份额的资源，分配给3个工程，其利润函数如 下表。 计算过程 计算过程 计算过程 计算过程 计算最优解： 最大利润opt = 140 第3个工程分配资源x3*=d3(p) = 4 份 第2个工程分配资源x2*= d2(p-x3*) = 4 份 第1个工程分配资源x1*= d1(p-x3*-x2*) = 0 份 最优解X*=(0,4,4) 时间复杂性： 初始化：O(m) 计算f2(x),f3(x),…,fn(x): O(nm2) 计算opt,k,p: O(nm) 回溯：O(n) 时间复杂性：O(nm2) 关于资源分配求解过程 动态规划的一般决策过程示意图 动态规划最优解的确定 从Sk,kn向前回溯可得到最优解或最优决策序列 {P1,k1，P2,k2，…，Pk,kn}。即 动态规划函数 各阶段赖以决策的策略或目标，称为动态规划函 数。 资源分配问题动态规划函数 — fi(x) 动态规划函数可以递归定义，或用递推公式 表达。 动态规划算法的设计步骤 找出最优解的性质，并刻画其结构特征；fi(x) 递归的定义最优值; fi(x) = max{Gi(k)+fi-1(x-k)} 以自底向上的方式计算最优值；表格 根据计算最优值时得到的信息，构造最优解。回溯 动态规划算法的基本要素 可用动态规划求解的问题应具有以下两个基本要 素： 最优子结构 问题的最优解包含了其子问题的最优解。 动态规划算法，利用问题的最优子结构性质，自底向上的方式递归地从子问题的最优解构造出整个问题的最优解。 动态规划算法的基本要素 重叠子问题 在用动态规划递归地自底向上求解问题时，每次产生的子问题不是新问题，有些被反复计算多次。动态规划算法利用这些子问题的重叠性质，对每个子问题只计算一次，将结果保存在表格中，后续计算只需查找表格，从而节省时间。 资源分配问题重叠子问题示意图 初始化：cost[i]= INT_MAX; path[i] = -1 0≤in cost[n-1] = 0; i = n-1 若i=0，转(4)；否则转(3) i--;根据式(6.1)和(6.2)计算cost[i]、path[i];转(2) i=0;route[i]=0; 若route[i]=n-1，终止；否则，转(6) i++；route[i] = path[route[i-1]]；转(5) 时间复杂性： 邻接矩阵：初始化：O(n)；计算cost，循环n-1次，每次访问邻接表一行，O(n2)；计算route，O(k)；故为O(n2) 考虑邻接表存储的时间复杂性。 分别求从城市i出发的哈密尔顿回路，最后求n条回 路的最小值。 4个城市1、2、3、4，邻接矩阵如下表。 解：以从城市1出发为例，求哈密尔顿回路，其它城 市同理。 第一阶段 d(1,{2,3,4}) = min{c12+d(2,{3,4}),c13+d(3,{2,4}), c14+d(4,{2,3})} 第二阶段 d(2,{3,4}) = min{c23+d(3,{4}),c24+d(4,{3})} d(3,{2,4}) = min{c32+d(2,{4}),c34+d(4,{2})} d(4,{2,3}) = min{c42+d(2,{3}),c43+d(3,{2})} 第3阶段 d(3,{4}) = c34 + d(4,ф) = 2 + 3 = 5 {3,4,1} d(4,{3}) = c43 + d(3,ф) = 5 + 6 = 11 {4,3,1} d(2,{4}) = c24 + d(4,ф) = 3 + 3 = 6 {2,4,1} d(4,{2}) = c42 + d(2,ф) = 7 + 5 = 12 {4,2,1}