动态规划算法
动态规划算法是经典的最优值寻找算法，不同于贪心算法(局部最优，只考虑下一步最好的选择)，每步都会考虑是否全局最优。为了便于理解，这里将通过理论与实际案例相结合来介绍。
一、基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
三、适用的情况
能采用动态规划求解的问题的一般要具有3个性质：
(1)最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
下面看一个例子。
四、多段图最短路径规划
问题：该图*有9个节点，通过1，...9标出，s是起点，t是终点，相邻点的箭头表示可以到达，连接权重表示距离，现在需要从s出发，找出一条到t的最短路线。
分析：我们将2,3,4,5四个点记为A界，6,7,8记为B界，只会从每个界经过一个点，也就是说包括s和t，经过的点一共有4个。那么，现在从终点t反推，假设这么一条路线已经找到，那么必定会经过A界某个点，假设是3这个点，那么从3到终点t肯定也是最近的，我们把3到t的所有情况计算出来，选择一条最近的即可，现在从终点反推到起点。
计算B到t的所有可能路径长度，即6,7,8到t的长度，6 -> t的路径是4，7 -> t的路径是2，8 -> t的路径是5，记为：d(6,t) = 4, d(7,t) = 2, d(8,t) = 5；
计算A到t的所有可能路径，对于节点2，有3种选择，2 -> 6 -> t，2 -> 7 -> t，2 -> 8 -> t，对应路径长度分别为：4 + 4 = 8; 2 + 2 = 4；1 + 5 = 6; 那么，d(2, t) = 4，在节点2旁边用红色字体4标出。只记最小距离，因为假设到了节点2，肯定会走短的距离，所以只保存最短距离即可。
同理，3到t的距离有3 -> 6 ->t，3 -> 7 -> t，长度分别为：2 + 4 = 6; 7 + 2 = 9；那么d(3, t) = 6，用在图中节点3旁边用用红色字体6标出标记；同理节点4到t最短距离d(4,t) = 16，节点5到t最短距离d(5,t) = 12。
最后，就是加上s到A这段距离最小值，记为最短线路。
d(s,t) = min(d(s,2) + d(2,t), d(s,3) + d(3,t), d(s,4) + d(4,t), d(s,5) + d(5,t))
= min(9 + 4,6 + 6,3 + 16,2 + 12)
=12
即，走路线 s -> 3 -> 6 -> t，距离最短。
一般我们采用动态规划算法解决问题时，首先要明确问题是否具有最优子结构，然后找出问题最优子结构的递推关系式，例如多段图最短路径规划问题
中的递推公式可表述如下：
cost(s,t) = min{ c(t,l) + cost(s+1,l) }，l∈Vt+1，(t,l)∈E，E为多段图的边集，Vs+1为第s+1段中的点集
其中cost(s,t)表示的是第s段的第t个顶点到终点t的路径长度的最短值，l为第s+1段中的某个顶点，然后c(t,l)为顶点t到l之间的连接权值，即距离值。
0/1背包问题
动态规划算法中比较经典的一个问题是0/1背包问题，0/1背包问题即是有一堆物品和一个背包，物品有质量和价值两个属性，背包有容量限制，问如何
装这些物品使得背包所能获得的总价值最大，且所装物品的总质量不会超过背包的容量限制。通俗点说就是对于一个物品，我们选择要不要将它放入背
包中，0即表示不放入，1即表示放入，最终对所有物品是否放入背包会构成一个决策仅含0或1的决策序列，这个决策序列能够满足背包装物品的总重
量不会超过背包容量的限制。0/1背包问题对应了一个整数规划问题如下：
0/1背包问题具有最优子结构，其递推关系式可表示为：
其中m[k][c]表示当背包容量为c时，对第k个物品是否放入背包中进行决策后（是否放入）对应的背包的最优总价值。解释上述的递推关系式即是，当前
背包容量为c，现在要放入第k个物品，此时有两种可选策略，一种是不放入，一种是放入。不放入则此时的价值与对第k-1个物品是否放入的决策的价
值是一致的，且背包容量维持为c不变；而如果选择放入，则此时放入物品后的背包总容量要减掉第k个物品的重量，而总价值为对前面k-1个物品进行
决策后的价值加上第k个物品的价值所得的总价值。
可以通过一个实例的推演来理解这个问题：假设有3个物品，质量分别为(w1,w2,w3)=(2,3,4)，价值分别为(p1,p2,p3)=(1,2,5)，背包容量为6。按顺序
放入物品，下文中的X即是当前背包容量，此时对于m[0][X]，满足：
对于m[1][X]，满足：
对于m[2][X]，满足：其中当3≤X<5时，max{1,0+2}中的1是放入第一个物品后的价值，而0+2意味着此时选择放入第二个物品，则无论第一个物品无法
放入，因为已经超过了背包的容量范围。
对于m[3][X]，满足：
从上面的推演可以看出，每对一个新物品是否加入背包进行决策，都需要考虑前面的物品是否加入背包的决策的最优情况，最终背包问题的最优解综合
了所有物品是否加入背包的最优决策。而针对每一个物品是否放入的决策都保存在m[][]这个二维数组中，因此每次计算新问题的时候都不需要在对子问
题进行重复计算，只是直接调用m[][]中对应的数组项即可。
背包问题Python代码
import numpy as np
def solve(vlist,wlist,totalWeight,totalLength):
resArr = np.zeros((totalLength+1,totalWeight+1),dtype=np.int32)
for i in range(1,totalLength+1):
for j in range(1,totalWeight+1):
if wlist[i] <= j:
resArr[i,j] = max(resArr[i-1,j-wlist[i]]+vlist[i],resArr[i-1,j])
else:
resArr[i,j] = resArr[i-1,j]
return resArr[-1,-1]
if __name__ == '__main__':
v = [1,2,5]
w = [2,3,4]
weight = 6
n = 3
result = solve(v,w,weight,n)
print(result)猜你喜欢
上一篇： 动态规划算法
下一篇： 数独游戏_java_深搜+回溯