经典算法之—动态规划
动态规划是一种求解多阶段决策问题的最优化算法。
一．多阶段决策过程
事件的发展过程分为若干个相互联系的阶段。事件的发展总是初始状态开始，依次经过第一阶段、第二阶段、第三阶段、 …，直至最后一个阶段结束。 如图1所示：
图1
二．动态规划术语及性质
为了更好说明问题，我们引入几个术语：
（1）阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。如图1所示V1、V2……。值得注意的是，阶段的划分有时候非常直观，因为可能每一步就被划分为一个阶段；但是有时候阶段划分可能就没那么容易了，此时的阶段可能就不是前面所说的“每一步就是一个阶段了”，通常这时候的阶段包含多步，通常每个阶段的步数都不相同。这一点我们后面将举两个例子（分别是上台阶、最大子序列问题）来看看。
（2）状态：通常是指阶段和阶段之间的状态。在动态规划里面，（这个不太确定，只是自己的经验）状态通常包含两个部分，一个是对上一阶段结果的保存；另一个是对下阶段的决策。
（3）决策：就是下一阶段做出什么样的选择。决策的过程主要通过“状态转移方程”体现出来！
（4）动态规划的无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。
（5）动态规划的最优子结构性质：如果问题的最优解成立，那么对于问题的子问题，最优解的子解仍是该子问题的最优解。
（6）状态转移方程：动态规划的核心。设x(k)、x(k+1)为第k、k+1阶段的状态变量，第k阶段的决策结果为u(k)，从第k阶段到k+1阶段的映射为T。则有x(k+1)=T{x(k),u(k)}。
三．动态规划问题的解决过程
（1）正向推进
（2）逆向推进
在两种推进中都可以使用递归等手段来解决。
四．栗子
（1）上台阶问题，题目叙述如图2：
代码如下：
###########################
#上楼梯问题
#2016年12月17日
#by:zkj
############################
from numpy import randomdef upStairMethods(N): ##从下到上的方式迭代O(N)stairOne = 1; stairTwo = 2; stairN = 0;for i in range(3,N+1):stairN = stairOne + stairTwostairOne = stairTwostairTwo = stairNreturn stairNstairCnt = random.randint(3,10) #随机生成楼梯数量
print("楼梯阶数为:\n",stairCnt)
methods = upStairMethods(stairCnt)
print("上楼梯的方法总有:\n",methods)
（2）最大子序列问题，题目叙述如图3：
代码如下：
####################
#动态规划求最大字段和
#2016.12.13
####################
from numpy import randomdef calSubsquence(array,lenth,tupleArray):array = list(array) ##tuple->listif max(array) < 0: ##动态规划return 0for i in range(1,lenth):if array[i - 1] <= 0:array[i] = array[i]else:array[i] = array[i-1] + array[i] maxIndex = array.index(max(array)) ##找出最大子序列并返回if min(array) >= 0:return tupleArrayelse:for i in range(0,maxIndex+1):if min(array[i:maxIndex+1]) >= 0:return tupleArray[i:maxIndex+1]else:i +=1targetArray = tuple(random.randint(-10,10,10))
print("随机生成的数组为:\n",targetArray)
arrayLenth = len(targetArray)
maxSubsquence = calSubsquence(targetArray,arrayLenth,targetArray)
print("最大子序列为:\n",maxSubsquence,"\n最大子序列之和为:\n",sum(maxSubsquence))
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！