动态规划¶

前面介绍的线性规划,整数规划的决策变量都是静态的,在求解过程中都是以集合的形式被统一考虑的,但是,很多时候的决策问题的决策变量并不能同时考虑,决策按照时间会分为多阶段,决策变量需要分批,分期处理.面对这种多阶段决策问题,就有了所谓动态规划这一种数学方法.

动态规划把决策按照时间分批,把一个多阶段决策问题变成一个个相互联系的单阶段决策问题,并且求解这个决策序列.

下面介绍动态规划的基本概念:

动态规划的基本概念¶

在多阶段决策问题中,我们需要在每一个阶段做出相应的决策,决策记做\(u_k\),所有决策的序列我们把它称作一个策略,显然,动态规划的目的在于寻找最优策略.

在每个阶段中,都存在着状态变量输入\(s_k\)和输出\(s_{k+1}\)以及指标函数\(v_k\),通过指标函数值评价这个策略带来的决策效益大小:

\[ v_k=v_k(s_k,u_k) \]

输出是输入和决策的函数,这个函数被称作状态转移方程:

\[ s_{k+1}=T_k(s_k,u_k) \]

具体的图示如下:

图示

\[ \begin{aligned} &u_k\\ &\downarrow\\ s_k\rightarrow &\text{阶段k}\rightarrow s_{k+1}\\ &\uparrow\\ &v_k=v_k(s_k,u_k) \end{aligned} \]

动态规划实例¶

背包问题¶

一个爬山者,它的背包的容量是\(C\),设总共有\(n\)件物品可以被他装入背包中,物品\(j\)的使用价值是\(c_j\),重量为\(p_j\),问,在不超出背包容量的前提下,他该如何选择物品?

我们定义一个0-1决策变量\(x_j\)来代表\(j\)物品是否被他放入背包中,那么问题可以描述为:

\[ \begin{aligned} \min z=\sum_{j=1}^n c_jx_j \\ s.t. \sum_{i=1}^n p_jx_j\le C \end{aligned} \]

这其实是一个静态规划问题,完全可以用整数规划来进行求解,但是,我们也可以按照物品\(k\)被放入的顺序进行时间划分,然后使用动态规划求解这个问题.

对于前\(k\)个物品和容量为\(w\)背包,其能装入的最大价值为\(V(k,w)\),那么我们对第\(k+1\)件物品展开讨论,如果他没有被放入,那么其价值就和之前一样,如果他被放入,那么背包的容量相应会减少\(p_k\),于是得到状态转移方程:

\[ V(k+1,w)=\max\{V(k,w),V(k,w-p_k)+c_k\} \]

\(V(k+1,w)\)代表前\(k+1\)件物品和容量为\(w\)的背包所能包含的最大价值.

注意到0个物品的情况为为\(V(0,w)=0\)

我们要求的是\(V(n,C)\)

我们提供动态规划的两种方法

一种使用递归函数方法如下

# 重量数组

weight=[5,4,6,3]

#价值数组

value=[10,40,30,50]

#定义最优解数组

t=[0 for _ in range(4)]

def V(k,w):
    if k==0:
        return 0
    else:
        if weight[k-1] <= w:
            if V(k-1,w)>V(k-1,w-weight[k-1])+value[k-1]:
                #t.insert(0,0)
                #在比较大小的时候就会重复调用这个t的添加操作,所以不能这么做
                #解决办法是定义一个数组,每次的重复调用函数会得到相同的操作,这样就行了.
                t[k-1]=0
                return V(k-1,w)
            else:
                t[k-1]=1

                return V(k-1,w-weight[k-1])+value[k-1]


        else:
            t[k-1]=0
            return V(k-1,w)

a=V(4,10)

print(a)
print(t)

运行结果为:

90
[0, 1, 0, 1]

这种想法比较简单粗暴,但是,我们可以发现,在比较的过程中就会重复调用函数,所占据的资源较多,复杂度较高,下面我们给出一种使用dp表的方法

# 重量数组

weight=[5,4,6,3]

#价值数组

value=[10,40,30,50]

n=4

C=10


def f(weight,value,C,n):
    # 定义一个dp表,来代表所有可能出现的情况,第几行就代表几个物品构成的实例,列就代表背包的容量从0遍历到w
    dp=[[0]*(C+1) for _ in range(n+1)]

    # 定义一个判断表,表示该物品是否被选中
    judge=[[0]*(C+1) for _ in range(n+1)]

    #开始遍历列表内的所有情况
    for i in range(1,n+1):
        for j in range(1,C+1):
            if j>=weight[i-1]:
                if dp[i-1][j]>=dp[i-1][j-weight[i-1]]+value[i-1]:
                    dp[i][j]=dp[i-1][j]
                    judge[i][j]=False
                else:
                    dp[i][j]=dp[i-1][j-weight[i-1]]+value[i-1]
                    judge[i][j]=True


            else:
                dp[i][j]=dp[i-1][j]
                judge[i][j]=False

    return dp[n][C],judge

# 回溯这个判断表
a=[]

j=C

total_value,judge=f(weight,value,C,n)

for i in range (n,0,-1):
    if judge[i][j]:
        a.append(i-1)
        j=j-weight[i-1]

print(total_value,a)

运行结果为:

90 [3, 1]

秘书问题¶

招聘方录用一位前来应聘的秘书,现在,总共有\(n\)为应聘者,招聘方面试第\(i\)个人的时候,必须立即决定录用还是不录用,如果录用,本场面试结束,后面的等待的应聘者都可以滚蛋,如果不录用,则按照顺序继续面试下一位面试者.

现在问,招聘者该以什么样的策略,使得录用到的秘书的相对位次的期望值尽可能的小?

我们把第\(i\)位面试者的绝对名次记做\(A_i\),\(A_i\)在面试官的眼中可能取到任何值,把他在前i位面试者中的相对位次记做\(y_i\),显然,面试官只能根据这个相对位次来决定是否录用这名面试者.如果录用他,那么相应的它的绝对名次的条件期望值为:

\[ E(A_i|y_i=j)=\sum_{k=1}^n E(A_i=k|y_i=j)=\sum_{k=1}^n kP(A_i=k|y_i=j) \]

注意到:

\[ P(A_i=k|y_i=j)=\frac{P(y_i=j|A_i=k)P(A_i=k)}{P(y_i=j)} \]

\[ \begin{aligned} &P(y_i=j)=\frac{1}{i} \\ &P(A_i=k)=\frac{1}{n}\\ &P(y_i=j|A_i=k)=\frac{C_{k-1}^{j-1}C_{n-k+1-1}^{i-1-j+1}}{C_{n-1}^{i-1}} \end{aligned} \]

所以会有:

\[ E(A_i|y_i=j)=\frac{j}{C_n^i}\sum_{i=1}^n C_k^j C_{n-k}^{i-j} \]

根据组合恒等式可以得到:

\[ \sum_{i=1}^n C_k^j C_{n-k}^{i-j}=C_{n+1}^{i+1} \]

所以:

\[ E(A_i|y_i=j)=\frac{i+1}{n+1}j \]

定义\(U(i,j)\)为面试\(A_i\)时,面试官能够录取到最小位次期望值.

在面试官面试第\(i\)名面试者的时候,如果决定录用他,那么面试终止,得到的期望就如上面所示,但是如果面试官决定不录用他,这个时候他还没有面试下一位面试者,所以,第\(i+1\)位面试者的相对位次就有可能是\(1,2, \ldots i+1\)中的任何一个数,他们的概率都是相等的.

如果第\(i+1\)位选手的位次是\(k\),那么当面试官面试第\(i+1\)位面试者能够获得的最小位次期望就是:

\[ U(j,i)=U(k,i+1),k=1,2, \ldots i+1 \]

所以,会有:

\[ U(j,i)=\sum_{k=1}^n \frac{1}{i+1}U(k,i+1) \]

故,状态转移方程为:

\[ U(j,i)=\min\{\frac{i+1}{n+1}j,\frac{1}{i+1}\sum_{k=1}^n U(k,i+1)\} \]

边界条件:第n个人必定被录取,所以会有:

\[ U(j,i)=j \]

如果面试官从第一个人开始就采用动态规划,那么他能得到的最小位次期望为:\(U(1,n)\),也是我们要求的.