关于动态规划求解策略的进一步说明 采用枚举法:若问题的决策序列由n次决策构成,而每次 决策有p种选择,则可能的决策序列将有p个 利用动态规划策略的求解过程中保存了所有子问题的最优 解,而舍去了所有不能导致问题最优解的次优决策序列 动态规划:可能有多项式的计算复杂度。 2021/2/20
2021/2/20 21 关于动态规划求解策略的进一步说明 ➢ 采用枚举法：若问题的决策序列由n次决策构成，而每次 决策有p种选择，则可能的决策序列将有p n个。 ➢ 利用动态规划策略的求解过程中保存了所有子问题的最优 解，而舍去了所有不能导致问题最优解的次优决策序列 ➢ 动态规划：可能有多项式的计算复杂度
42多段图问题 1.问题的描述 ●在多段图中求从s到t的一条最小成本的路径,可以看 作是在k-2个段作出某种决策的结果。 第i次决策决定1中的哪个结点在这条路径上,这里 1≤i≤k-2; 最优性原理对多段图问题成立 2021/2/20
2021/2/20 22 4.2 多段图问题 1. 问题的描述 ● 在多段图中求从s到t的一条最小成本的路径，可以看 作是在k-2个段作出某种决策的结果。 ● 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1≤i≤k-2； ● 最优性原理对多段图问题成立
2.向前处理策略求解 设P(i)是一条从V中的结点到汇点t的最小成本路径 cOST(j是这条路径的成本 1)向前递推式 COST(i,j=min c(, D)+CosT(i+l,D) (j)∈E 2)递推过程 ★第k-1段 ,t)S,t>∈E COST(k-1,]) <J,t>gE 2021/2/20
2021/2/20 23 2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 ★ 第k-1段 c(j,t) <j,t>∈E COST(k-1,j) = ∞ ( , ) min { ( , ) ( 1, )} ( , ) 1 COST i j c j l COST i l j l E l vi = + + + j,t E
pi+1 2021/2/20 4
2021/2/20 24 l1 l2... lpi+1 … t j Vi Vi+1
V2 4 2 6 6 5 7 3 2 3 10 12 4 6 8)0→ 11 8 5段图 2021/2/20
2021/2/20 25 1 2345 678 9 10 11 12 9732 4 2 2 7 11 11 8 1 4 563 5 6 425 V 1 V2 V3 V4 V5 5段图