区块链技术博客
www.b2bchain.cn

动态规划(一)

这篇文章主要介绍了动态规划(一)的讲解,通过具体代码实例进行20158 讲解,并且分析了动态规划(一)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20158

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

目录

  • 通过一个实例认识动态规划
    • 商店打劫
    • 1.暴力递归
    • 2.分析冗余步骤改进为动态规划
    • 动态规划总结
  • 应用实例
    • 斐波那契数列
    • N阶乘:N!
    • 士兵的行走方法

动态规划(Dynamic Programming),名字没有什么特殊意义,关键在于看待问题的思想,而且并不是所有问题都可以用动态规划解决;


公式分两种:通项公式和递推公式,递推公式可以用递归实现


动态规划与递归相关联,如果去除递归中的重复计算,就是动态规划,当然,动态规划也可以直接通过递推的for循环实现

通过一个实例认识动态规划

商店打劫

这是leetcode中的一个典型题目,明显适合动态规划,题目描述:
一群盗贼在一条街上打劫,他们不能连续抢:不能第一家和第二家连着抢,这样会容易引来警察,现在要规划一下,如何安排人员抢劫获得最大收益;这个问题看似难以解决,实际上背后的意思就是给了一列数组,不能连续选择元素,如何取出元素,使取出的元素和最大;

1.暴力递归

首先,不考虑动态规划,先深入想想这个问题,考虑用暴力递归解决(递归不关注效率,递归的重点是体现出一个人解决问题的思想);
既然是盗贼们同时选择数组元素,可以等价为顺序从数组拿出元素,只要元素不连续就行,换句话说就是只让一个盗贼顺序抢劫,但商店不能相邻,注意这个想法对程序实现很重要,因为顺序执行的程序容易实现
现在,从最后一家开始抢劫(其实也可以从第一家,但习惯上从最后开始利于让人感受到问题规模在逐渐缩小),如果这条街连最后一家店都没有就代表没有其他店,所以什么都不能收获,返回0金额;
反之,现在街上有店,现在处在最后一家店,面临两个选择:
1.抢这家店,于是倒数第二家不能抢,下一步就要从倒数第三家开始;
2.不抢这家店,所以下一步要从倒数第二家开始抢;
然后将下一步抢的店作为当前最后一家店,重复上述过程,直到遇到边界条件:抢到没有店可以抢;
如果有一个函数rob可以根据目前的"最后一家店 i d x idx idx"和每个店的金额组成的数组 n u m l i s t numlist numlist,返回最大收益,就得到递推公式:
r o b ( i d x ) = m a x ( n u m l i s t [ i d x ] + r o b ( i d x − 2 ) , r o b ( i d x − 1 ) ) rob(idx)=max(numlist[idx]+rob(idx-2),rob(idx-1)) rob(idx)=max(numlist[idx]+rob(idx2),rob(idx1))
现在可以清晰地用递归实现:

#递归方式搜索 def rob(idx,numlist):     #idx=len(numlist)-1,代表从最后一家开始抢     if idx<0:         return 0     else:         return max(numlist[idx]+rob(idx-2,numlist),rob(idx-1,numlist))       #n家店,每家要做两次选择,时间复杂度为O(2**n),底数为每层的计算量,指数为递归的层数 numlist=[1,2,3] rob(len(numlist)-1,numlist) #输出最大收益:4 

2.分析冗余步骤改进为动态规划

对于n家店,每家都要比较两个选择:抢或不抢,时间复杂度为 O ( 2 n ) O(2^{n}) O(2n),底数为每层的计算量,指数为递归的层数;


这是非常耗时的,递归如果展开看会发现有冗余步骤:
先给出一个格式:
目前在抢店x,下一步只能抢(店y,店z,…);
则有:
n -> (n-2,n-3,n-4,n-5,…)
n-1 -> (n-3,n-4,n-5,n-6,…)
n-2 -> (n-4,n-5,n-6,n-7,…)
比如在抢n和抢n-1时,发现如果抢n仅仅需要多算一步rob(n-2),其他情况[rob(n-3),rob(n-4),ro(n-5),…]均是一样的;


现在希望算法没有一个步骤是重复计算的,所以可以考虑把重复计算的结果保存起来,用到时直接return,现在大致看出了一个特点:
动态规划=递归+空间换时间(开辟数组保存中间最优结果);
数组设计需要注意一个细节:对于没有计算过的情况,值一般设为-1,动态规划实现如下,假设numlist=[1,2,3,2,1,6]

import numpy as np #开辟数组,-1代表到该idx店,后续最优结果还没计算过 #注意result应该在globals()层共享  numlist=[1,2,3,2,1,6]  result=-1*np.ones(len(numlist),dtype=np.int)  #共n个状态,每个状态只算一遍,而且算完就保存到数组,下次需要时直接return,所以时间复杂度为O(n) def dprob(idx,numlist):     #边界条件     if idx<0:         return 0     #如果result[idx]>=0代表已经算过     elif result[idx]>=0:         return result[idx]     else:         result[idx]=max(numlist[idx]+dprob(idx-2,numlist),dprob(idx-1,numlist))         return result[idx]       maxmoney=dprob(len(numlist)-1,numlist) maxmoney,result 

可以看出除了省时,动态规划的优势还体现在保留了每一步的最优结果:
动态规划(一)

动态规划总结

当遇到一个问题时,习惯将原问题 N N N拆解为子问题 N − 1 N-1 N1,逐一求解合并回原问题 N N N
DP的应用范围
1.动态规划的本质应该是递归,递归常用于处理离散问题,所以动态规划不适合连续问题;一般来说,常用DP的离散问题关键字有:最优,最大,最小,最长,计数;
2.容易设计状态的问题(比如01背包问题);
3.有最优子结构:可以从 N − 1 N-1 N1可推出 N N N


最优子结构:
1.子问题最优决策可以导出原问题最优决策;
2.无后效性;如果抢了 i d x idx idx,就不能抢 i d x − 1 idx-1 idx1,这是明显有后效性的,但改成 n u m l i s t [ i d x ] + r o b ( i d x − 2 ) numlist[idx]+rob(idx-2) numlist[idx]+rob(idx2)后意味着 i d x − 2 idx-2 idx2 i d x − 2 idx-2 idx2之后的店都能抢劫,这就做到了无后效性;


DP的设计步骤
1.设计暴力算法,找到冗余;
2.设计并存储状态;
3.改进为递归式(状态转移方程);
4.或者自底向上计算最优解(递推:for循环),之前的实现是自顶向下的方式(递归);
注意不管是自顶向下还是自底向上,都依赖于状态方程的递推公式;
递推实现动态规划的rob
现在,我将动态规划改成递推形式:

#将之前的dprob改写为自底向上的递推式 import numpy as np  numlist=[1,2,3]  def dprob(numlist):     #不需要递归,可以将result设置到函数的locals()空间     result=np.zeros(len(numlist),dtype=np.int)          #若直接跳过最后一家,来第一家抢     result[0]=numlist[0]     #若直接跳过最后一家,来第二家抢     result[1]=max(numlist[1]+0,result[0])          #for循环实现递推     for idx in range(2,len(numlist)):         result[idx]=max(numlist[idx]+result[idx-2],result[idx-1])          #返回的应该是从最后一家开始抢的情况     return result[len(numlist)-1]  dprob(numlist)  #输出最大金额:4 

应用实例

斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,其计算公式为:
F ( 0 ) = 0 , F ( 1 ) = 1 , F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1,F(n)=F(n1)+F(n2)
1.递归实现
先暴力递归:

#递归实现斐波那契数列 #下标从0开始 #0、1、1、2、3、5、8、13、21、34 def fib(n):     if n<=1:         if n==0:             return 0         return 1     else:         return fib(n-1)+fib(n-2) fib(5)  #输出5 

2.开辟数组改成动态规划
开辟数组保存最优子结果,改进为动态规划:

#改为动态规划 """ 暴力递归 F(n)为斐波那契数列第n个 if n>=2 F(n)=F(n-1)+F(n-2) otherwise F(1)=1,F(0)=0 """ import numpy as np  #n为要算的下标,下标从0开始 n=5 F=-1*np.ones(n+1,dtype=np.int) F[0]=0 F[1]=1  def dpfib(n):     if F[n]>=0:         return F[n]     else:         F[n]=dpfib(n-1)+dpfib(n-2)         return F[n]  dpfib(n),F  #输出(5, array([0, 1, 1, 2, 3, 5])) 

3.换成递推形式
直接用for循环来自底向上计算数组:

#改成递推式 import numpy as np  #n为要算的下标,下标从0开始 n=5 F=-1*np.ones(n+1,dtype=np.int)  def dpfib(n):     F[0]=0     F[1]=1          for i in range(2,n+1):         F[i]=F[i-1]+F[i-2]     return F[n]      dpfib(n),F #(5, array([0, 1, 1, 2, 3, 5])) 

N阶乘:N!

阶乘相对于前面的问题,显得更加清晰与直接;
阶乘的计算公式:
n ! = 1 × 2 × 3 × 4… ( n − 1 ) × n n!=1times 2times 3times 4…(n-1)times n n!=1×2×3×4...(n1)×n
同样的,先递归实现:

# N阶乘 def factorial(n):     if n<1:         return 1     else:         return n*factorial(n-1)      factorial(3) #6 

使用递推动态规划实现:

#递推形式的动态规划改进阶乘 import numpy as np  n=3 result=-1*np.ones(n+1) result[0]=1  def dpfactorial(n):     for i in range(1,n+1):         result[i]=i*result[i-1]     return result[n]  dpfactorial(3) #6 

士兵的行走方法

在一个 M × N M times N M×N的棋盘上,士兵要从左下角走到右上角,只能向上或者向右走一步,计算一共有多少种走法;
这属于计数问题,容易想到是否可以用动态规划处理;所以先分析一下问题,求出一个递推公式;
问题分析
动态规划(一)可以看到,假设棋盘是 2 × 3 2 times 3 2×3的,士兵位于右上角(1,3)位置时,可以推断他上一步要么从(1,2)开始,要么从(2,3)开始,所以根据规则(只能向上或向右走)可以得到两个子棋盘 2 × 2 2 times 2 2×2 1 × 3 1 times 3 1×3,所以 2 × 3 2 times 3 2×3棋盘的走法数等于两个子棋盘的走法数之和;
现在令 F ( m , n ) F(m,n) F(m,n)表示 M × N M times N M×N棋盘的走法数量,则得到递推公式:
F ( m , n ) = F ( m − 1 , n ) + F ( m , n − 1 ) F(m,n)=F(m-1,n)+F(m,n-1) F(m,n)=F(m1,n)+F(m,n1)
另外,对于单行或单列的棋盘,必然只有一种走法
递归实现

#先暴力搜索实现 """ F(m,n)表示走法数量 当m,n都大于1:F(m,n)=F(m-1,n)+F(m,n-1),否则只有一种走法 """ def numway(m,n):     if m==0 or n==0:         #相当于没有棋盘         return 0     elif m==1 or n==1:         return 1     else:         return numway(m-1,n)+numway(m,n-1)  numway(2,3)  #3 

动态规划改进

#使用动态规划实现 import numpy as np  m=2 n=3 result=-1*np.ones((m,n))  result[:,0]=1 result[0,:]=1  def dpnumway(m,n):     if m==0 or n==0:         return 0     elif m==1 or n==1:         return 1     #用(m-1,n-1)索引是因为数组下标从0开始     elif result[m-1,n-1]>=0:         return result[m-1,n-1]     else:         #因为下标从0开始的原因         result[m-1,n-1]=dpnumway(m-1,n)+dpnumway(m,n-1)         return result[m-1,n-1]  print(dpnumway(2,3)) result 

动态规划(一)

本文转自互联网,侵权联系删除动态规划(一)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 动态规划(一)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们