lec3
- 格式：pdf
- 大小：248.21 KB
- 文档页数：13
6.231 动态规划
讲座3
概要
•确定性状态有限动态规划问题•后向最短路径算法
•前向最短路径算法
•最短路径举例
•其它最短路径算法
确定性(状态有限)动态规划问题
•状态<==> 节点
•控制<==> 弧
•控制序列(开环)<==> 从初态到终态的路径
•a k ij：k时刻从状态i ∈S k到状态j∈S k+1的转移代价
•a N it ：状态i ∈S N的终端代价
•控制序列代价<==> 相应路径的代价( 可以看成路径的长度)
前向和后向DP 算法
•DP 算法
最优代价为J 0(s )，等于从s 到t 的最短路径长度。
•观测：从s 到t 的最优路径是从t 到s 的最优路径“反问题”，其中弧的长度不变，方向相反。
•前向DP 算法(=后向DP 算法的反问题)：
最优代价是：
•将看作从初始状态s 到状态j 的最优到达代价。
11()min ()N k
N it i
S J t a J i −∈⎡⎤=+⎣⎦ ()k J j
前向动态规划算法说明
•没有随机性问题的前向动态规划算法。
•数学上，对于随机性问题，我们不能把自己局限于开环序列，所以最短路径观点无效。
•从概念上讲，在不确定性出现时，状态x k的“最优到达代价”的概念没有意义，因为不能保证（对于问题1）到达任何给定状态。
•相反，即使在随机性问题中，任何状态x k的“最优余留代价”的概念很有意义。
通用的最短路径问题
•{1,2,... ,N,t}:图中的节点(t：终点)
•a ij ：从节点i到节点j的代价
•寻找一条从节点i到节点t的最短路径（代价最小）
•假设：所有循环路径具有非负长度，最优路径不超过N步•我们将问题描述成一个正好N步的问题，但是允许从节点i到它自己的退化移动，其代价为a ii =0。
J k(i)=从i到t的N-k步的最优代价
J0(i)：从i到t的最优路径的代价
•动态规划算法：
状态估计/隐藏马尔可夫模型
•转移概率为p ij 的马尔可夫链
•
状态转移是不可见的•
对每一步转移，我们得到一个（独立的）观测值•
r (z;i,j ): 当状态从i 到j 转移时，观测值为z 的概率•轨迹估计问题：给定观测序列Z N ={z 1, z 2,...,z N }，什么是“最象的”状态转移序列[在上
使p (X N |Z N )最大化的序列]。
01{,,...,}ˆˆˆˆN N X x x x =
快速算法
•我们有
其中p(X
,Z N )和p(Z N )是(X N,Z N)和Z N发生的非条件概率
N
•p(X N|Z N )最大化和ln (p(X N|Z N ))的最大化等价
•我们有
,...,x N}上，所以问题等价于在所有可能的序列{x
最小化：
•这是一个最短路径问题
最短路径的通用算法
•有很多非动态规化的最短路径算法，可以用来解决确定性有限状态问题。
•如果可以避免计算每个状态的最优余留代价，这些方法比动态规划更受欢迎。
•这是大型状态空间的基本问题，很多组合优化问题就是此类问题。
标记修正方法
•给定：起点s，终点t，长度a ij 0
•思想是逐步解决从起点s到每个其它节点i的最短路径
•注意：
—d i (i的标记):已找到的最短路径长度(初始d s=0,d i=∞,i≠s时)—UPPER:目的地的标记值d t
—开放集列表:包含当前活动的节点，它们是进一步测试的候选节点(初始时，开放集={s})
标记修正算法：
第一步(节点移出)：从开放集中移出节点i和它的每个子节点j，转第二步。
第二步(节点插入测试)：如果d
i +a ij<min{d j,UPPER}, 置
d j=d i+a ij ，并且置i为j的父节点。
另外，如果j≠t,且j不在开
放集中则将j放入开放集中；如果j=t，则设置UPPER的d
t 为
新的值d
i
+a it 。
第三步(结束测试)：开放集为空则结束，否则转第一步。
≥
图示/举例
•给定：起点s ，终点t ，长度a ij ≥0
•d i (i 的标记):已经找到的最短路径长度(初始d s =0,d i =∞,i ≠s 时)。
标记d i 明显与从s 到i 的路径有关。
•UPPER:目的地的标记值d t
•开放集列表:包含“活动”节点(初始时开放集={s })
?i ij UPPER d a +<?
i ij j d a d +<开放集 ?
()
i ij j d a d s i j s j +<→→→路径比当前
路径更好吗？UPPER ?()
i ij
s i j s t +<→→→路径可能是较短
路径的一部分吗？j i ij
d d a =+令插入
移出
注意某些节点从不进入开放集（OPEN)
标记修正方法的有效性
命题：如果至少存在一条从原点到终点的路径，则标记修正算法终止时的UPPER 值等于s 到t 的最短距离。
证明：
(1)每次一个节点j 进入开放集，它的标记减少，且等于从s 到j 的某条路径的长度。
(2)不同长度路径的数量是有限的，所以一个节点能进入开放集的次数也是有限的，算法结束。
(3)令(s,j 1,...,j k ,t )为最短路径，d*为最短距离。
如果在结束时UPPER >d*，经过算法运算，UPPER 仍将大于所有路径(s,j 1,...,j k ,t ,m =1, ...,k )的长度。
因此，节点j k 在d jk 等于s 到j k 的最短距离时永远不会进入开放集,同理，节点j k -1在d jk -1等于s 到j k -1的最短距离时永远不会进入开放集。
如此一直到j 1 ，从而出现矛盾。
