3基于python 的动态规划实例
3 动态规划
本着交流与学习的⽬的，写下本⽂，相当于学习笔记与思考，禁⽌商业⽤途等侵权⾏为。本⽂内容均参考：
王秋芬. 算法设计与分析（python）版[M]. 北京：清华⼤学出版社，2021.
该书中有更为详细的实例描述和代码过程，配套有单元试题和答案、课件，对⼊门算法设计与分析的同学⼤有裨益。更多内容可购买该书进⾏学习。
3.1 基本思想
20世纪50年代初，美国数学家R. E. Bellman等⼈在研究多阶段决策过程的优化问题时提出了著名的最优化原理，将多阶段过程转化为⼀系列单阶段问题，利⽤各阶段之间的关系，逐个求解，创⽴了解决这类过程优化问题的新⽅法——动态规划。
其基本思想与贪⼼法类似，都是将待求解问题分解为更⼩的、相同的⼦问题，然后对⼦问题进⾏求解，最终产⽣⼀个整体最优解。
3.2 求解步骤与基本要素
1. 分析最优解的性质，刻画最优解的结构特征——考查是否适合采⽤动态规划法。
2. 递归定义最优值（建⽴递归式或动态规划⽅程）。
3. ⾃底向上的⽅式计算出最优值，并记录相关信息。
4. 根据计算最优值时得到的信息，构造出最优解。基本要素可表述如下：
**最优⼦结构性质：**即问题的最优解包含其⼦问题的最优解。在分析问题的最优⼦结构性质时，所⽤的⽅法具有普遍性——反证法。⾸先假设由问题的最优解导出的⼦问题的解不是最优的，然后再设法说明在这个假设下可构造出⽐原问题最优解更好的解，从⽽导致⽭盾。
**⼦问题重叠性质：**该性质并不是动态规划适⽤的必要条件，但是如果该性质⽆法满⾜，动态规划算法同其他算法相⽐就不具备优势。
⾃底向上的求解⽅法
⽰例
1 加⼯顺序问题
1.1 问题描述
设有个⼯件需要在机器和上加⼯，每个⼯件的加⼯顺序都是先在上加⼯，然后在上加⼯。分别表⽰⼯件在和上所需的加⼯时间（）。问应如何在两机器上安排⽣茶⼥，使得第⼀个⼯件从在上加⼯开始到最后⼀个⼯件在上加⼯完所需的总加⼯时间最短？
1.2 问题分析
将个⼯件的集合看作，设定是给定个⼯件的⼀个最优加⼯顺序⽅案，是该调度⽅案的第个要调度的⼯件。先考虑初始状态，第⼀台机器开始加⼯集合中的⼯件时，第⼆台机器空闲。随着时间的推移，经过的时间，进⼊⼀个新的状态：第⼀台机器开始加⼯集合中的⼯件时，第⼆台机器开始加⼯⼯件，需要的时间才能空闲。以此类推，表达成更⼀般的形式。当第⼀台机器开始加⼯集合是N的作业⼦集中的⼯件时，第⼆台机器需要时间才能空先。在这种状态下，从集合中的第⼀个⼯件开始在机器上加⼯到最后⼀个⼯件在机器上加⼯结束所耗的时间为。设集合的最优加⼯顺序中第⼀个要加⼯的⼯件为，那么，经过的时间，进⼊的状态为第⼀台机器开始加⼯集合中的⼯件时，第⼆台机器需要的时间才能空闲下来，这种情况下机器加⼯完中的⼯件所需的时间为，其中，则。
n M 1M 2M 1M 2t ,t 1j 2j j M 1M 2j =1,2,...,n M 1M 2n N ={1,2,...,n }P n P (i )i (i =1,2,...,n )M 1N P (1)M 2t 1P (1)M 1N −P (1)P (2)M 2P (1)t 2P (1)M 1S (S ⊆N )i M 2t S M 1M 2T (S ,t )S i t 1i M 1S −{i }M 2t ′M 2S −{i }T (S −{i },t )′t =′t +2i max {t −t ,0}1i T (S ,t )=t +1i T (S −{i },t +2i max {t −t ,0})1i
从上式中可以看出，如果是最⼩的，那么肯定包含也是最⼩的。整体最优⼀定包含⼦问题最优。
1.3 建⽴最优值的递归关系式
设表⽰从集合中的第⼀个⼯件开始在机器上加⼯到最后⼀个⼯件在机器上加⼯结束时所耗的最短时间，则：当时，耗时为闲下来所需的时间，即；
python 定义数组当时，。
1.4 加⼯顺序问题的Johnson-Bellman’ Rule
假设在集合的种加⼯顺序中，最优加⼯⽅案为以下两种⽅案之⼀：
1. 先加⼯中的号⼯件，再加⼯号⼯件，其他⼯件的加⼯顺序为最优顺序。
2. 先加⼯中的号⼯件，再加⼯号⼯件，其他⼯件的加⼯顺序为最优顺序。
⽅案1的加⼯时间为：
令：
化简过程中将max展开可便于运算。
同理可得，⽅案2的加⼯时间为：
.
令：.
⽐较 ，可知其⼤叫取决于和的⼤⼩。⽽其⼤⼩取决于：和的⼤⼩，可得：。反之亦然。因此，如果⽅案1⽐⽅案2更优，则：.
两边同乘(-1)，可得：
.
由上式可知，⽅案1不⽐⽅案2坏的充分必要条件是.
同理，⽅案2不⽐⽅案1坏的充分必要条件是。由此可得出结论，对加⼯顺序中的两个⼯件，若它们在两台机器上的处理时间满⾜，则⼯件先加⼯，⼯件后加⼯的加⼯顺序优；反之，⼯件先加⼯，⼯件后加⼯的加⼯顺序优。
如果加⼯⼯件满⾜，则称其满⾜Johnson Bellman’s Rule。设最优加⼯顺序为，则的任意相邻的两个加⼯⼯件和满⾜.
进⼀步可以证明：最优加⼯顺序第和第个要加⼯的⼯件，如果，则。即满⾜Johnson Bellman’s Rule的加⼯顺序⽅案为最优⽅案。
因此，其算法设计步骤如下：
T (S ,t )T (S −{i },t +2i max {t −t ,0})1i T (S ,t )S M 1M 2S =∅M 2T (S ,t )=t S = ∅T (S ,t )=min {t +i ∈S 1i T (S −{i },t +2i max {t −t ,0})}1i S n !S i j S j i T (S ,t )=t +1i T (S −{i },t +2i max {t −t },0)
1i =t +1i t +1j T (S −{i ,j },t +2j max {t −t ,0}−1i t ,0)
1j t =ij t +2j max {t +2i max {t −t ,0}−1i t ,0}1j =t +2j t +2i max {t −t −1i t ,−t ,−t }
1j 1j 2i T (S ,t )=′t +1i t +1j T (S −′
{i ,j },t +2i max {t +2j max {t −t ,0},0})1j t =ji t +2i t +2i max {t −t −1i t ,−t ,−t }1j 1i 2i T (S ,t ),T (S ,t )′
t ij t ji max {t −t −1i t ,−t ,−t }1j 1j 2i max {t −t −1i t ,−t ,−t }1j 1i 2i t >ij t →ji T (S ,t )>T (S ,t )′
max {t −t −1i t ,−t ,−t }⩽1j 1j 2i max {t −t −t ,−t ,−t }1i 1j 1i 2j min {t +1i t −1j t ,t ,t }⩾1j 2i min {t +t −t ,t ,t }1i 1j 1i 2j min {t ,t }⩾1j 2i min {t ,t }1i 2j min {t ,t }⩾1i 2j min {t ,t }1j 2i i ,j min {t ,t }⩾1j 2i min {t ,t }1i 2j i j j i i ,j min {t ,t }⩾1i 2j min {t ,t }1j 2i P P P (i )P (i +1)min {t ,t }⩾1P (i +1)2P (i )min {t ,t },1⩽1P (i )2P (i +1)i ⩽n −1i j i <j min {t ,t }⩾1P (j )2P (i )min {t }1P (i ),t 2P (j )
1. 令。
2. 将中的⼯件按⾮减序排序；将中的⼯件按⾮增序排序。
3. 中的⼯件接中⼯件，即就是所求的满⾜Johnson Bellman’s Rule的最优加⼯顺序。
N =1{i ∣t <1i t },N =2i 2{i ∣t ⩾1i t }2i N 1t 1i N 2t 2i N 1N 2N N 12
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 .ke
y == 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 ]<b [i ]        job .append (Jobtype (key ,i ,N1))    job .sort ()    j =0    k =n -1    for  i in  range (n ):        if  job [i ].N1:            x [j ]=job [i ].id #将N1中的⼯件放置在数组c 的前端            j += 1        else :            x [k ]=job [i ].id # 将N2中的⼯件放置在数组c 的后端            k -= 1    j = a [x [0]]    k = j + b [x [0]]    for  i in  range (1,n ):#计算总时间        j += a [x [i ]]        if (j < k ):            k = b [x [i ]] + k        else :            k = j + b [x [i ]]    return  x ,k if  __name__ == "__main__":    a = [3,8,10,12,6,9,15]    b = [7,2,6,18,3,10,4]    n = len (a )    x ,k = FlowShop (n ,a ,b )    print ("最优加⼯次序为：")    for  i in  range (n ):        print (x [i ] + 1,end = '  ')12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。