动态规划求期望--原理 POJ2096

June 28, 2014 at 4:10 pm

用DP来求期望的题目已经不只做了一个了,但是一直对求解过程中使用的数学原理不是很明白。昨天发现,使用条件数学期望及全期望公式,或许可以较好地解释这个原理,但可能仍然存在问题,暂时先把它记下来(考虑过使用马尔科夫链来解释其中的状态转移,却觉得又不能把它看作一个随机过程,最终也没能得出结论,数学基础和智商都太差了,没有办法)。 原题地址:http://poj.org/problem?id=2096 题目大意: 题目的意思是把世界上的程序BUG分成n类,一个有无尽多个BUG的程序有s个子系统,一个大神每天随机的发现一个BUG,求发现所有n类BUG至少1个,所有子系统的BUG至少1个所需的天数的期望。由于发现BUG是随机的,所以属于某个类的概率是1/n,属于某个子系统的概率是1/s。 题解: 令S表示条件中描述的所需时间,显然S是一个一维随机变量,可以使用期望的定义来计算,但由于时间可能是无穷的,所以计算无法终结,初步计算就会发现计算过程是很复杂的,也很难找到规律。 这种题目通常就是使用DP来求解的。记(i,j)是已经发现了i种BUG、在j个子系统种发现BUG的状态,记S(i,j)是在已知发现了i种BUG、在j个子系统中发现BUG的前提下,达到目标所需的天数,记DP[i][j]为S(i,j)的期望。显然需要求解的是DP[0][0]。就目前来看,仅仅已知DP[n][s]=0,因为此时已经达到目标。 核心是状态及状态的转移,在(i,j)状态下,新的一天可能会发生这样4种事件: 1.(i,j) -> (i,j) 新发现的BUG在i种j个中, p1=ij/ns 2.(i,j) -> (i+1,j) 新发现的BUG在j个中,但不在i种中 p2=(n-i)j/ns 3.(i,j) -> […]