10动态规划.pdf

: .

v 12345 f12345
1 2 8 5 1 10 1 2 10 15 16 26
2 5 9725 2 719???
3 6 6 2 1 2 3 13 ? ? ? ?
4 9 6387 4 22????
5 9 9 9 4 3 5 31 ? ? ? ?最优路径问题
‹ f[2][3] = max(f[1][3],f[2][2]) + v[2][3]
v 12345 f12345
1 2 8 5 1 10 1 2 10 15 16 26
2 5 9725 2 71926? ?
3 6 6 2 1 2 3 13 ? ? ? ?
4 9 6387 4 22????
5 9 9 9 4 3 5 31 ? ? ? ? : .
动态规划
北京大学计算机系
代亚非 : .
动态规划
北京大学计算机系
代亚非 : .
本章重点
‹ 动态规划思想
– 自底向上
– 分治
– 解决冗余
‹ 动态规划基本概念
– 阶段与状态
– 决策与策略