- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
其它及计算f3(x)同理，结果如下表：
计算过程
0
f1(x)
1 4
2 26
3 40
4 45
5 50
6 51
7 52
8 53
0
d1(x)
f2(x) d2(x) f3(x)
0
0 0 0
1
5 1 5 1
2
26 0 26 0
3
40 0 40 0
4
60 4 80 4
5
70 5 90 5
6
86 4
7
8
100 110 4 5
假设用邻接矩阵C={cij}存储网。
货郎担问题的动态规划函数
分别求从城市i出发的哈密尔顿回路，最后求n条回 路的最小值。
记d ( j ,V )表示从顶点j出发，经V中各顶点一次，最终 回到顶点j的最短路径的长度。 动态规划函数— d ( j ,V )
最优值：d(i,V-{i})
货郎担问题动态规划函数的递归表示
6.1 资源分配问题
假设资源总数为m份，工程个数为n。给每项工程投 入的资源不同，所获得的利润也不同。要求把总数 为m的资源，分配给n个工程，以获得最大利润分配 方案。
数学描述
假设用函数Gi(k) (1≤i≤n,0≤k≤m)表示将k份资 源分配给工程i获得的利润。 设工程i分配xi份资源。资源分配问题数学描述为：
求资源的最优分配方案。
计算过程
解：初始： f1(x) = G1(x) d1(x) = x
opt = max{f1(x),0≤x≤8} = 53
k=1 p=8
计算过程
f 2 (0) G2 (0) f1 (0) 0 d 2 (0) 0 opt 53
f 2 (1) max{ G2 (0) f1 (1), G2 (1) f1 (0)} 5 d 2 (1) 1 opt 53 f 2 (2) max{ G2 (0) f1 (2), G2 (1) f1 (1), G2 (2) f1 (0)} 26 d 2 ( 2) 0 opt 53 f 2 (3) max{ G2 (0) f1 (3), G2 (1) f1 (2), G2 (2) f1 (1), G2 (3) f1 (0)} 40 d 2 (3) 0 opt 53
初始化：cost[i]= INT_MAX; path[i] = -1 0≤i<n 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) 其中，数组route存放从0到n-1的最短路径。
0 k x
0 xm
上述解资源分配所采用的算法：动态规划
6.2 动态规划的基本思想
动态规划也称多阶段决策，由状态和决策组成。从 初始状态开始，根据各阶段决策使状态转移，到达 最终状态。
动态规划的一般决策过程示意图
S0
P1
S1
P2
S2
Sn-1
Pn
Sn
设状态Si = {si,1,si,2,…,si,r}。 Sn是最终状态集。S1,..,Sn中至少有一个状态是最 优状态(最优值)，假设为Sk,kn。
5 C (cij ) 6 3
3 6 7 2 3 4 2 7 5
计算过程
解：以从城市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})}
算法分析
时间复杂性： 初始化：O(m) 计算f2(x),f3(x),…,fn(x): O(nm2) 计算opt,k,p: O(nm) 回溯：O(n) 时间复杂性：O(nm2)
关于资源分配求解过程
f1 ( x) f i ( x) f i 1 ( x) f n ( x) f i 1 ( x) max {Gi 1 (k ) f i ( x k )}
计算过程
path[1] = 4 cost[0] = min{4+cost[1],5+cost[2],8+cost[3]} = 15 最优值 path[0] = 1 回溯求最优解： route[0] = 0 route[1] = 1 route[2] = 4 route[3] = 6 最优解：0146
动态规划算法的基本要素
重叠子问题 在用动态规划递归地自底向上求解问题时，每 次产生的子问题不是新问题，有些被反复计算 多次。动态规划算法利用这些子问题的重叠性 质，对每个子问题只计算一次，将结果保存在 表格中，后续计算只需查找表格，从而节省时 间。
资源分配问题重叠子问题示意图
f3(0) f3(1) f3(2) f3(3) f3(4)
d (i, V {i}) min {cij d ( j ,V {i, j})}
jV {i}
d ( j , V ) min{c jk d (k ,V {k})}
kV
d (k , ) cki
k i
动态规划解货郎担问题实例
4个城市1、2、3、4，邻接矩阵如下表。
动态规划解多段图最短路径算法分析
时间复杂性： 邻接矩阵：初始化：O(n)；计算cost，循环 n-1次，每次访问邻接表一行，O(n2)；计算 route，O(k)；故为O(n2)
考虑邻接表存储的时间复杂性。
6.4 货郎担问题
假设n个城市，分别用 1 ~ n的数字编号。货郎担问 题 是在有向网G V , E ，V {1， 2， ..., n}, E {e ij ,1 i, j n（ } e ij上权表示城市i到城市j的距离）中寻找一条 路径最短的哈密尔顿回 路（经过每个顶点一次 ）。
则称这样的图为多段图 。令 V1 Vk 1，称s V1为源点，
多段图的最短路径问题，是求从源点s到收点t的最 小花费的通路。 设用邻接矩阵C={cij}存储图G。
多段图最短路径问题的动态规划函数
按子集顺序，对多段图各顶点编号。假设源点为 0，收点为n-1。
假设数组元素cost[i]存放从顶点i出发到收点t的最短 路径长度。假设数组元 素path[i]存放使cost[i]取最小 的路径上前方顶点标号 。 动态规划函数— cost[i]
opt max{ s.t.
G ( x )}
i i i 1
n
x
i 1
n
i
m
设其最优解为X* =(x1*,x2*,...,xn*)。
资源分配问题求解
记f i (x)表示将x份资源分配给前i个工程获得的最大 利润。记d i (x)表示使f i ( x)最大时，分配给第i个工 程的资源份额。
(1)
动态规划解多段图最短路径问题实例
6 4 0 5 1 8 5 2 7 6 3 9 8 9 5 4 4 5 6
计算过程
解： cost[6] = 0 cost[5] = 4+cost[6] = 4 path[5] = 6 cost[4] = 5+cost[6] = 5 path[4] = 6 cost[3] = min{8+cost[4],9+cost[6],9+cost[5]} =9 path[3] = 6 cost[2] = min{5+cost[3],7+cost[5]} = 11 path[2] = 5 cost[1] = min{6+cost[3],6+cost[4]} = 11
计算过程
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} d(2,{3}) = c23 + d(3,ф) = 2 + 6 = 8 {2,3,1} d(3,{2}) = c32 + d(2,ф) = 4 + 5 = 9 {3,2,1}
0 k x
0 xm
解资源分配问题实例
有8个份额的资源，分配给3个工程，其利润函数 如 下表。 x 0 1 2 3 4 5 6 7 8
G1(x) 0 G2(x) 0 G3(x) 0
4 5 5
26 15 15
40 40 40
45 60 80
50 70 90
51 73 95
52 74 98
53 75 100
0 k x
0 xm
d 2 ( x) 使f 2 ( x)达最大值的k d 3 ( x) 使f 3 ( x)达最大值的k d i ( x) 使f i ( x)达最大值的k
f 3 ( x) max {G3 (k ) f 2 ( x k )}
0 k x
f i ( x) max {Gi (k ) f i 1 ( x k )}
