3 基于python的动态规划实例

本着交流与学习的目的，写下本文，相当于学习笔记与思考，禁止商业用途等侵权行为。本文内容均参考：

王秋芬. 算法设计与分析（python）版[M]. 北京：清华大学出版社，2021.

该书中有更为详细的实例描述和代码过程，配套有单元试题和答案、课件，对入门算法设计与分析的同学大有裨益。更多内容可购买该书进行学习。

20世纪50年代初，美国数学家R. E. Bellman等人在研究多阶段决策过程的优化问题时提出了著名的最优化原理，将多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

其基本思想与贪心法类似，都是将待求解问题分解为更小的、相同的子问题，然后对子问题进行求解，最终产生一个整体最优解。

1. 分析最优解的性质，刻画最优解的结构特征——考查是否适合采用动态规划法。
2. 递归定义最优值（建立递归式或动态规划方程）。
3. 自底向上的方式计算出最优值，并记录相关信息。
4. 根据计算最优值时得到的信息，构造出最优解。

基本要素可表述如下：

• **最优子结构性质：**即问题的最优解包含其子问题的最优解。在分析问题的最优子结构性质时，所用的方法具有普遍性——反证法。首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
• **子问题重叠性质：**该性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
• 自底向上的求解方法

设有 n n n个工件需要在机器 M 1 M_1 M1​和 M 2 M_2 M2​上加工，每个工件的加工顺序都是先在 M 1 M_1 M1​上加工，然后在 M 2 M_2 M2​上加工。 t 1 j , t 2 j t_{1j},t_{2j} t1j​,t2j​分别表示工件 j j j在 M 1 M_1 M1​和 M 2 M_2 M2​上所需的加工时间（ j = 1 , 2 , . . . , n j=1,2,...,n j=1,2,...,n）。问应如何在两机器上安排生茶女，使得第一个工件从在 M 1 M_1 M1​上加工开始到最后一个工件在 M 2 M_2 M2​上加工完所需的总加工时间最短？

将 n n n个工件的集合看作 N = { 1 , 2 , . . . , n } N={1,2,...,n} N={1,2,...,n}，设定 P P P是给定 n n n个工件的一个最优加工顺序方案， P ( i ) P(i) P(i)是该调度方案的第 i i i个要调度的工件 ( i = 1 , 2 , . . . , n ) (i=1,2,...,n) (i=1,2,...,n)。先考虑初始状态，第一台机器 M 1 M_1 M1​开始加工集合 N N N中的 P ( 1 ) P(1) P(1)工件时，第二台机器 M 2 M_2 M2​空闲。随着时间的推移，经过 t 1 P ( 1 ) t_{1P(1)} t1P(1)​的时间，进入一个新的状态：第一台机器 M 1 M_1 M1​开始加工集合 N − P ( 1 ) N-{P(1)} N−P(1)中的 P ( 2 ) P(2) P(2)工件时，第二台机器 M 2 M_2 M2​开始加工 P ( 1 ) P(1) P(1)工件，需要 t 2 P ( 1 ) t_{2P(1)} t2P(1)​的时间才能空闲。以此类推，表达成更一般的形式。当第一台机器 M 1 M_1 M1​开始加工集合 S ( S ⊆ N ) S(Ssubseteq{N}) S(S⊆N)是N的作业子集中的工件 i i i时，第二台机器 M 2 M_2 M2​需要 t t t时间才能空先。在这种状态下，从集合 S S S中的第一个工件开始在机器 M 1 M_1 M1​上加工到最后一个工件在机器 M 2 M_2 M2​上加工结束所耗的时间为 T ( S , t ) T(S,t) T(S,t)。设集合 S S S的最优加工顺序中第一个要加工的工件为 i i i，那么，经过 t 1 i t_{1i} t1i​的时间，进入的状态为第一台机器 M 1 M_1 M1​开始加工集合 S − { i } S-{i} S−{i}中的工件时，第二台机器 M 2 M_2 M2​需要 t ′ t' t′的时间才能空闲下来，这种情况下机器 M 2 M_2 M2​加工完 S − { i } S-{i} S−{i}中的工件所需的时间为 T ( S − { i } , t ′ ) T(S-{i},t') T(S−{i},t′)，其中 t ′ = t 2 i + m a x { t − t 1 i , 0 } t'=t_{2i}+max{t-t_{1i},0} t′=t2i​+max{t−t1i​,0}，则 T ( S , t ) = t 1 i + T ( S − { i } , t 2 i + m a x { t − t 1 i , 0 } ) T(S,t)=t_{1i}+T(S-{i},t_{2i}+max{t-t_{1i},0}) T(S,t)=t1i​+T(S−{i},t2i​+max{t−t1i​,0})。

从上式中可以看出，如果 T ( S , t ) T(S,t) T(S,t)是最小的，那么肯定包含 T ( S − { i } , t 2 i + m a x { t − t 1 i , 0 } ) T(S-{i},t_{2i}+max{t-t_{1i},0}) T(S−{i},t2i​+max{t−t1i​,0})也是最小的。整体最优一定包含子问题最优。

设 T ( S , t ) T(S,t) T(S,t)表示从集合 S S S中的第一个工件开始在机器 M 1 M_1 M1​上加工到最后一个工件在机器 M 2 M_2 M2​上加工结束时所耗的最短时间，则：

当 S = ∅ S=varnothing S=∅时，耗时为 M 2 M_2 M2​闲下来所需的时间，即 T ( S , t ) = t T(S,t)=t T(S,t)=t；

当 S ≠ ∅ Snevarnothing S​=∅时， T ( S , t ) = m i n i ∈ S { t 1 i + T ( S − { i } , t 2 i + m a x { t − t 1 i , 0 } ) } T(S,t)=min_{iin{S}}{t_{1i}+T(S-{i},t_{2i}+max{t-t_{1i},0})} T(S,t)=mini∈S​{t1i​+T(S−{i},t2i​+max{t−t1i​,0})}。

假设在集合 S S S的 n ! n! n!种加工顺序中，最优加工方案为以下两种方案之一：

1. 先加工 S S S中的 i i i号工件，再加工 j j j号工件，其他工件的加工顺序为最优顺序。
2. 先加工 S S S中的 j j j号工件，再加工 i i i号工件，其他工件的加工顺序为最优顺序。

方案1的加工时间为：

T ( S , t ) = t 1 i + T ( S − { i } , t 2 i + m a x { t − t 1 i } , 0 ) T(S,t)=t_{1i}+T(S-{i},t_{2i}+max{t-t_{1i}},0) T(S,t)=t1i​+T(S−{i},t2i​+max{t−t1i​},0)

= t 1 i + t 1 j + T ( S − { i , j } , t 2 j + m a x { t − t 1 i , 0 } − t 1 j , 0 ) =t_{1i}+t_{1j}+T(S-{i,j},t_{2j}+max{t-t_{1i},0}-t_{1j},0) =t1i​+t1j​+T(S−{i,j},t2j​+max{t−t1i​,0}−t1j​,0)

令：

t i j = t 2 j + m a x { t 2 i + m a x { t − t 1 i , 0 } − t 1 j , 0 } t_{ij}=t_{2j}+max{t_{2i}+max{t-t_{1i},0}-t_{1j},0} tij​=t2j​+max{t2i​+max{t−t1i​,0}−t1j​,0} 化简过程中将max展开可便于运算。

​ = t 2 j + t 2 i + m a x { t − t 1 i − t 1 j , − t 1 j , − t 2 i } =t_{2j}+t_{2i}+max{t-t_{1i}-t_{1j},-t_{1j},-t_{2i}} =t2j​+t2i​+max{t−t1i​−t1j​,−t1j​,−t2i​}

同理可得，方案2的加工时间为：

T ′ ( S , t ) = t 1 i + t 1 j + T ′ ( S − { i , j } , t 2 i + m a x { t 2 j + m a x { t − t 1 j , 0 } , 0 } ) T^{'}(S,t)=t_{1i}+t_{1j}+T^{'}(S-{i,j},t_{2i}+max{t_{2j}+max{t-t_{1j},0},0}) T′(S,t)=t1i​+t1j​+T′(S−{i,j},t2i​+max{t2j​+max{t−t1j​,0},0}).

令：

t j i = t 2 i + t 2 i + m a x { t − t 1 i − t 1 j , − t 1 i , − t 2 i } t_{ji}=t_{2i}+t_{2i}+max{t-t_{1i}-t_{1j},-t_{1i},-t_{2i}} tji​=t2i​+t2i​+max{t−t1i​−t1j​,−t1i​,−t2i​}.

比较 T ( S , t ) , T ′ ( S , t ) T(S,t),T^{'}(S,t) T(S,t),T′(S,t) ，可知其大叫取决于 t i j t_{ij} tij​和 t j i t_{ji} tji​的大小。而其大小取决于：

m a x { t − t 1 i − t 1 j , − t 1 j , − t 2 i } max{t-t_{1i}-t_{1j},-t_{1j},-t_{2i}} max{t−t1i​−t1j​,−t1j​,−t2i​}和 m a x { t − t 1 i − t 1 j , − t 1 i , − t 2 i } max{t-t_{1i}-t_{1j},-t_{1i},-t_{2i}} max{t−t1i​−t1j​,−t1i​,−t2i​}的大小，可得： t i j > t j i → T ( S , t ) > T ′ ( S , t ) t_{ij}>t_{ji} rightarrow{T(S,t)>T^{'}(S,t)} tij​>tji​→T(S,t)>T′(S,t)。反之亦然。因此，如果方案1比方案2更优，则：

m a x { t − t 1 i − t 1 j , − t 1 j , − t 2 i } ⩽ m a x { t − t 1 i − t 1 j , − t 1 i , − t 2 j } max{t-t_{1i}-t_{1j},-t_{1j},-t_{2i}}leqslant{max{t-t_{1i}-t_{1j},-t_{1i},-t_{2j}}} max{t−t1i​−t1j​,−t1j​,−t2i​}⩽max{t−t1i​−t1j​,−t1i​,−t2j​}.

两边同乘(-1)，可得：

m i n { t 1 i + t 1 j − t , t 1 j , t 2 i } ⩾ m i n { t 1 i + t 1 j − t , t 1 i , t 2 j } min{t_{1i}+t_{1j}-t,t_{1j},t_{2i}}geqslant{min{t_{1i}+t_{1j}-t,t_{1i},t_{2j}}} min{t1i​+t1j​−t,t1j​,t2i​}⩾min{t1i​+t1j​−t,t1i​,t2j​}.

由上式可知，方案1不比方案2坏的充分必要条件是 m i n { t 1 j , t 2 i } ⩾ m i n { t 1 i , t 2 j } min{t_{1j},t_{2i}}geqslant{min{t_{1i},t_{2j}}} min{t1j​,t2i​}⩾min{t1i​,t2j​}.

同理，方案2不比方案1坏的充分必要条件是 m i n { t 1 i , t 2 j } ⩾ m i n { t 1 j , t 2 i } min{t_{1i},t_{2j}}geqslant{min{t_{1j},t_{2i}}} min{t1i​,t2j​}⩾min{t1j​,t2i​}。由此可得出结论，对加工顺序中的两个工件 i , j i,j i,j，若它们在两台机器上的处理时间满足 m i n { t 1 j , t 2 i } ⩾ m i n { t 1 i , t 2 j } min{t_{1j},t_{2i}}geqslant{min{t_{1i},t_{2j}}} min{t1j​,t2i​}⩾min{t1i​,t2j​}，则工件 i i i先加工，工件 j j j后加工的加工顺序优；反之，工件 j j j先加工，工件 i i i后加工的加工顺序优。

如果加工工件 i , j i,j i,j满足 m i n { t 1 i , t 2 j } ⩾ m i n { t 1 j , t 2 i } min{t_{1i},t_{2j}}geqslant{min{t_{1j},t_{2i}}} min{t1i​,t2j​}⩾min{t1j​,t2i​}，则称其满足Johnson Bellman’s Rule。设最优加工顺序为 P P P，则 P P P的任意相邻的两个加工工件 P ( i ) P(i) P(i)和 P ( i + 1 ) P(i+1) P(i+1)满足 m i n { t 1 P ( i + 1 ) , t 2 P ( i ) } ⩾ m i n { t 1 P ( i ) , t 2 P ( i + 1 ) } , 1 ⩽ i ⩽ n − 1 min{t_{1P(i+1)},t_{2P(i)}}geqslant{min{t_{1P(i)},t_{2P(i+1)}}},1leqslant{i}leqslant{n-1} min{t1P(i+1)​,t2P(i)​}⩾min{t1P(i)​,t2P(i+1)​},1⩽i⩽n−1.

进一步可以证明：最优加工顺序第 i i i和第 j j j个要加工的工件，如果 i < j i

因此，其算法设计步骤如下：

1. 令 N 1 = { i ∣ t 1 i < t 2 i } , N 2 = { i ∣ t 1 i ⩾ t 2 i } N_1={i|t_{1i}
2. 将 N 1 N_1 N1​中的工件按 t 1 i t_{1i} t1i​非减序排序；将 N 2 N_2 N2​中的工件按 t 2 i t_{2i} t2i​非增序排序。
3. N 1 N_1 N1​中的工件接 N 2 N_2 N2​中工件，即 N 1 N 2 N_{1}N_{2} N1​N2​就是所求的满足Johnson Bellman’s Rule的最优加工顺序。

class Jobtype:
    def __init__(self,key,id,N1):  #每个工件包括编号、两台机器上的加工工件的最短时间、工件是否应该在N1中的标志三个字段。
        self.key =  key
        self.id = id
        self.N1 = N1
    def __lt__(self,other):
        return self.key < other.key
    def __eq__(self,other):
        return self.key == other.key
        
def FlowShop(n,a,b): 
    """
    输入
    ************************
    n:n个工件
    a:工件在机器1上的加工时间
    b:工件在机器2上的加工时间
    ************************
    
    输出：
    ************************
    x:最优加工次序
    k:最短总加工时间
    ************************
    """
    job = []#记录n个工件Jobtype
    x= [0 for i in range(n)]#记录最优加工顺序
    for i in range(n):
        if a[i]>b[i]:
            key = b[i]
        else:
            key = a[i]
        N1 = a[i]