认识动态规划

2023-11-11

你的打赏是我奋笔疾书的动力!​


概念篇

线性规划:下图给出了模型

 

    其中目标函数和约束条件里面的不等式函数都是关于xi的线性函数。这类问题都有一些不错的求解方式。

 

整数规划:若在线性模型中,变量限制为整数,则称为整数线性规划,即为整数规划,可见整数规划狭义上考虑的是线性问题。

 

    然而今天,我们不谈线性规划的这种求最优的问题,之后会专门开辟一个题目来谈,我们今天只谈“风月(闷骚)”。

动态规划:解决多阶段决策问题的一种方法。

 

    其研究对象有:最短路径问题,资源分配(投资)问题,生产计划问题,背包问题,设备更新问题,库存问题......

 

    解决问题的特点:在多阶段决策过程中,解决的动态过程可以按照时间先后分为各个阶段,每个阶段的状态既相互联系又相互区别;每个阶段都要进行决策,决策的目的是使整个过程的决策达到最优效果。最优性原理:最优策略的子策略必为最优。动态规划具有最优性原理这一性质。

 

遍动态规划算法设计的大致的四个步骤:

 

  1. 描述最优解的结构
  2. 递归定义最优解的值
  3. 按自底向上的方式计算最优解
  4. 由计算出的结果构造一个最优解

例题篇

 

    以上为拗脑的概念,相信大家在各种博客里的描述见得不少前篇一律,没啥好看的,但是有一点,例子见得少,这些概念不一定都能明白,老生常谈一下,下面引入各大高校奉为经典的求最短路径的例题。可能是因为它好讲吧,但是美国人著述的算法导论上的开篇例子却不一样。没有例子的理解,我觉着都是干吼般的咆哮,吼过之后还是空虚寂寞加阴冷。

例1: 如下图,求A到F的最短路径的例题:

     根据动态规划的一般解题步骤有:

 

 

  1. 我们考虑这样一个命题,如若考虑从A到F的最短路径,那么该路径上各点到U的也是最短路径。
  2. 设A到F的最短距离为dA,B1点到F的最短距离为dB1,……依次类设,姑有:   

 

        dA = min{4+dB1,5+dB2}

        dB1 = min{2+dC1,3+dC2,6+dC3}

        dB2 = min{7+dC4,8+dC2,7+dC3}

        dC1 = min{5+dD1,8+dD2}

        ……

    3. 自底向上的方式计算最优解dA:

        dE1 = 4,dE2 = 3,

        dD1 = min{3 + dE1,5 + dE2} = 7

        dD2 = min{6 + dE1,2 + dE2} = 5   (D2,E2)

        dD3 = min{1 + dE1,3 + dE2} = 5

        dC1 = min{5 + dD1,8 + dD2} =12

        dC2 = min{4 + dD1,5 + dD2} =10  (C2,D2)

        dC3 = min{3 + dD2,4 + dD3} =8

        dC4 = min{8 + dD2,4 + dD3} =9

        dB1 = min{2 + dC1,3 + dC2,6 + dC3} = 13 (B1,C2)

        dB2 = min{7 + dC4,8 + dC2,7 + dC3} = 16

        dA = min{4+dB1,5+dB2}=17    (A,B1)

    4. 构造最优路径如上(A,B1,C2,D2,E2)

 

例2:把正数a分成n个部分,使其乘积最大。

设 Pn(a) 是 a分成n个部分其乘积的最大值,则:
P1(a) = a
P2(a) = max{x* P1(a-x)}= max{x*(a-x)},0<=x<=a
求导取其极值点x=a/2
故,p2=(a/2)^2
Pn (a) = max{x* Pn-1(a-x)} ,0<=x<=a
用数学归纳法征得,x=a/n, Pn (a)=(a/n)^n
这里的x是连续变量

例3:如下图,灰色长条代表从某时间开始到某时间结束的任务,灰色长条上的红色数字代表完成任务后的报酬,黑色数字代表任务序号,任务不能重叠,求如何选择任务使得酬劳最多?

 

    设OPT(i)为前i个任务的最多报酬,则有如下递推式:

    

    其中prev(i)是选择做当前任务后的前一个不重叠的任务序号,OPT(prev(i)) 为前prev(i)个任务的最多报酬,先来看看prev(i)的所指,有如下:

 

    图中推知,考虑前8个任务和前6个任务的最多报酬时,都有可能需要前5个任务的最多报酬,这样就出现了重叠子问题的现象。

    现在针对每一个i,根据递推式来考虑OPT(i)的值,如下图(蓝色是选择的任务序号):

 

    这个例子有个重叠子问题的概念,为了使重叠子问题不重复计算,我们会把重叠子问题的最优解缓存起来,以便处理其他子问题的时候直接使用,不用再次计算。动态规划程序设计上一般不会选择递归的方式。而是用空间来降低时间复杂度。

 

例4:如图数组,如何选择不相邻的元素,使得加起来和最大?

    设OPT(i)为前i个元素加起来的最大和,则有如下图推知OPT(i):(会有重叠子问题,+代表选择该项,-表示不选)

 

    且有有如下递推式:

    

 

    递归的初值(出口)有:

    

 

    代码表示有:

 

1.      递归函数

arr = []
def rec_opt(arr,i){
		if i==0:
			return arr[0]
		elif I == 1:
			return max(arr[0],arr[1])
		else :
			A= rec_opt(arr,i-2)+arr[i]
			B= rec_opt(arr,i-1)
            return max(A,B)}
	rec_opt(arr,6)
}

2.      非递归函数

def dp_opt(arr):
	opt=np.zeros(arr.length);
    opt[0]=arr[0]
    opt[1]= max(arr[0],arr[1])
	for I in range(2,len(arr)):
		A=opt(arr,i-2)+arr[i]
		B=opt(arr,i-1)
		Opt[i]=max(A,B)
	Return arr[arr.length-1]
dp_opt(arr)

 

例5:如下一组数:

 

问:是否存在某些元素有加起来等于S的可能组和?

 

    设 subset(arr[i],S) 表示前i项存在在某些元素有加起来等于S的可能组合,则自底而上推导如下图:

 

    且有有如下递推式:

 

    递归的初值(出口)有:

    

 

    代码表示有:

    1. 递归函数

 

    2. 非递归函数,分析各阶段状态值subset(arr[i],S[j])如下图:

 

例6:资源配置(投资)问题,设有资源a,分配给n个项目,设gi(xi)为分配资源xi给项目i所得的利润,求如何分配资源使得利润最大化?例如有7万元投资到A,B,C三个项目,其利润如下表:

 

    目标函数: max z = g1(x1)+g2(x2)+ g3(x3)+…+ gn(xn)

    约束条件:x1+x2+…+xn=a,xi>=0,i=1,2,3,……

    若gi(xi)是xi的线性函数,则是一般的线性规划问题,可以按照线性规划的求解方法求解。无论它是不是线性函数,我们现在用多阶段决策的动态规划来解决。最关键的一步是设。

 

    设fi(x)表示以资源数量x分配给前i个项目所得的最大利润。则问题求解的就是fn(a)对应例子就是求f3(7)

    i=1:f1(x)=max{g1(x)},表示以资源数量x分配给第一个项目A所得的最大利润,其中,0<x<=a

    1<i<=n:有如下递推式:

    fi(x)=max{gi(y)+fi-1(x-y)},其中,y表示资源数x中分配给第i个项目的资源数,x-y表示资源数x中分配给前i-1个项目的资源数,即:0<=y<=x。fi-1(x-y)当然表示资源数x中的x-y个资源分配给前i-1个项目所得的最大利润。以上的资源x,y个资源都指x,y万元的人民币

         第一步 考虑f1(x)中的x取值不同,第一个项目A所得的最大利润:

 

    第二步,考虑再加入第二个项目B,f2(x)中的x取值不同,前2个项目A,B所得的最大利润,此时有递推式:f2(x)=max{g2(y)+f1(x-y)} 0<x<=a,0<=y<=x

 

    f2(7)=max={ g2(0)+f1(7),g2(1)+ f1(6),g2(2)+ f1(5),g2(3)+ f1(4),g2(4)+ f1(3) ,g2(5)+ f1(2) ,g2(6)+ f1(1) ,g2(7)+ f1(0)}=max{0.35,0.42,0.4,0.42,0.38,0.38,0.40,0.34}=0.42

    同理算得:f2(1)=0.12, f2(2)=0.23,f2(3)=0.27, f2(4)=0.32, f2(5)=0.34, f2(6)=0.37

    第三步,考虑再加入第三个项目C,f3(x)中的x取值不同,前3个项目A,B,C所得的最大利润,此时有递推式:f3(x)=max{g3(y)+f2(x-y)} 0<x<=a,0<=y<=x

 

    故有,f3(7)=max{g3(y)+f2(7-y)}=0.52,即7万元分配给三个项目A,B,C所得的最大利润为0.52万,分别投资1,3,3万元

显然,此题也有递归和非递归的2种程序设计。

 

例7:完全背包问题。背包限重a,有n种物品各若干,其重量和单价已知,问题是如何装使得总价最大?

    设单位重量为ai,单价为ci,xi表示装物品i有xi件,i=1,2,3……

    目标函数: max z = c1*x1+ c2*x2+c3*x3+…+cn*xn

    约束条件: x1*a1+ x2*a2+ x3*a3+…+xn *an <=a,xi>=0且为整数,i=1,2,3,……

 

    若a=5,3中物品的重量和单价如下:

 

    则有:

 

    可以看到这是一个整数规划问题,可以用分支界定法,和割平面法来解决。

 

    以下关注动态规划的解法:

    设fi(x)为总重量不超过x,包中只装有前i中物品的最大总价,a>=x>=0,i=1,2,3…则问题的求解变为求fn(a)即:总重量不超过a,包中装有n中物品的最大总价

    i=1:  f1(x)=max{ c1*y },y*a1<=x,y表示装第1个物品的件数

    逐一加入第3,4,…,n件物品来考量不超过x,包中只装有前i中物品的最大总价,就是一个递推的过程,所以有如下递推式:

    fi(x)= max{ ci*y+ fi-1(x-y*ai)} , x<=a, y<= floor(x/ai), 1<i<=n

    计算过程如下:

    f1(x)=c1*floor(x/a1),x<=a

    f2(x)= max{ c2*y+ f1(x-y*a2)}, f1(x-y*a2)= c1*floor((x-y*a2)/a1), x<=a, y<= floor(x/a2)

    …

    fn(x)= max{ cn*y+ fn-1(x-y*an)}, x<=a, y<= floor(x/an)

    上例中就是求f3(5)= max{ c3*y + f2(5-y*a3)}, x<=5,0<= y<= floor(5/a3),c3,a3带入其递推式有:f3(5)= max{ 12*y + f2(5-y*5)}, x<=5,0<=y<= floor(5/5)=1,y=0,1

    f3(5)=max{f2(5),12+f2(0)}

    f2(5)= max{ 5*y + f1(5-y*2)}, y<= floor(5/2)=2,y=0,1,2

    故f2(5)=max{f1(5),5+f1(3),10+f1(1)},

    而f1(x)=8*floor(x/3),x<=5,y<=floor(x/3) y=0,1

    则f1(1)=f1(2)=0, f1(3)=f1(4)=f1(5)=8

    故f2(5)=max{8,13,10}=13,

    而f2(0)= max{ 5*y + f1(0-y*2)}, y<= floor(0/2)=2,y=0

    故f2(0)=f1(0)=0

    故f3(5)=max{13,12}=13 即,第3个物品装0个,第2个物品装1个,第1个物品装1个,可装的最大总价13

 

    考虑递归算法:

int[] a = new int[]{3,2,5};//单重
int[] c = new int[]{8,5,12};//单价

Result {
	double v; //总重量不超过x,包中只装有前i中物品的最大总价
	int num;//第i中物品所装的件数
    int i;// 物品序号
}

Result f(double x,int i){
		int limit = floor(x/a[i]);
        if(i==0){
            return new Result(c[i]*limit,limit,0);
         }
        int y = 0;
        double max = t = 0.0d;
		while(y<= limit){
			if(max < t = c[i]*y+ f (x-y*a[i],i-1).v){
				max  = t;
			}
			y++;
        }
	return new Result(max,num,i);
}

    我们可以看到本例的解法还能用于重量是连续实数的情况,即大可不必限制在离散整数范围内,若并本例中的背包重量,单位重量以及单价都是整数的话,那么我们在求解的过程中一定不会出现非整数,为什么?从上面推fi的递推式max{ ci*y + fi-1(x-y*ai)} , x<=a, y<= floor(x/ai)可知,运算的操作有floor,ci*y,x-y*ai,max,这些运算的值都是整数,即fi不可能是非整数。那么,我们就可以所有的fi缓存起来供递推式自调用,所以就有一种非递归的方式来实现这个例子。另外若重量,单位重量以及单价有一样是非整数的话,背包九讲里还有O(an)这个时间复杂度吗?还有非递归的方式吗?

 

例8 0-1背包,借用上例题干,但每种物品要么不装要么只能装一件,同问在不超过包的负载量a的约束条件下,可以装出的最大总价。

    还是设fi(x)为总重量不超过x,包中只装有前i中物品的最大总价。则其递推式有:

    fi(x)= max{ fi-1(x),ci+ fi-1(x-ai)} , x<=a, 1<i<=n

    f1(x)=c1(x>=a1)or 0(x<a1),

    其实本例和例3,例4有些相像,都是在选与不选的全覆盖式条件上做决策。若本例的重量是实数的话,也是不能用非递归实现的。把x=5带入f3(x)自地往上推将上去,就可求得本问题的解。推略。

例9最长公共子序列,解略。

 

总结篇

    好,现在来看一下大师们总结的一些概念,一个是最优子结构,另一个是重叠子问题,这俩概念是动态规划的本质特点。万事开头难,说的就是动态规划的第一步,第一步就是定义最优解的结构,使得解的子结构也最优,这也是重要的一步,例如定义fi(x)为总重量不超过x,包中只装有前i中物品的最大总价,它具有最优子结构,即1<i<=n的每一个i和每一个x组合,都代表一个最优的子结构或者说最优的子问题。和重叠子问题关联的概念还有,状态,状态转移方程。当我们不采用递归的方式设计程序时,那我们的思考的就是让这些最优子问题的值缓存起来,以供让其他的最优子问题调用决策,这些最优子问题的值就是状态,而状态转移方程就是用于决策的递推式,例7中fi(x)取不同的i和不同的x都是某一阶段的状态,至于阶段其实也很好理解,例7中f3(5)这是第一阶段的状态,f3(!5)也可以算作第一阶段,但是f3(!5)这些状态在例7中毫无用处,所以第一阶段就只有f3(5)这一个用到的状态,为了求的最终问题f3(5),根据递推式,需要先求得f2(5),f2(0)这俩状态,这属于第二阶段的状态,我们看出来阶段的分段是根据物品的种类来划分,所以f1(x)属于第三阶段。至此,有了重叠子问题,状态和状态转移方程的理解,我们也就明白了一些文章把第一步定义最优解的结构叫定义状态

    分数背包。例7中若重量,单位重量以及单价有一样是非整数的话,可以称作非整数背包,那我们可以称做分数背包吗?

 

转载请注明出处

参考:

https://www.bilibili.com/video/av16544031?from=search&seid=16579408987279019650

清华大学计算机工程与科学系的组合数学课本

学堂在线运筹学

你的打赏是我奋笔疾书的动力!

支付宝打赏:

微信打赏:

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

认识动态规划 的相关文章

  • 大数据技术——VMbox的安装和网络配置

    大数据实训案例 实验报告 题目 大数据实验环境搭建 姓名 xxx 学号 xxxxxxx 实验日期 2023 x x 一 实验目的 1 掌握Linux操作系统的安装和使用方法 2 掌握hadoop的安装和使用方法 二 实验平台 操作系统 Ub
  • [USACO08FEB]修路Making the Grade

    题目链接 走这里 题目分析 考虑绝对值的几何意义 显然 b 里的数一定在 a 里出现过 离不离散化问题不大 用下标作第二位状态就行 设 dp i j 表示第 i 个数 高度为 a j 时的最优解 方程见代码 代码 include

随机推荐

  • Spring第38篇:定时器详解(@Scheduled & @EnableScheduling)

    Spring中 Scheduled EnableScheduling 这2个注解 可以用来快速开发定时器 使用特别的简单 如何使用 用法 1 需要定时执行的方法上加上 Scheduled注解 这个注解中可以指定定时执行的规则 稍后详细介绍
  • OSS实现文件上传

    本文主要讲解mall整合OSS实现文件上传的过程 采用的是服务端签名后前端直传的方式 文章目录 OSS OSS中的相关概念 OSS的相关设置 开通OSS服务 创建存储空间 跨域资源共享 CORS 的设置 服务端签名后前端直传的相关说明 流程
  • python3 GUI- 登陆界面

    python3 GUI 登陆界面 from tkinter import root Tk def Show root1 Tk if En get user and En1 get 123 Label root1 text 登陆成功 bg G
  • 全新防火墙6.0 DHCP线路上网配置

    一 组网需求 外网接口使用DHCP 内网为192 168 1 0 24网段 实现基本上网功能 二 网络拓扑 三 配置要点 1 配置接口 wan1口 务必勾选 从服务器重新得到网关 这样dhcp地址获取成功后设备会自动生成默认路由 无需手动配
  • 详细记录Pycharm配置已安装好的Conda虚拟环境

    当安装好conda环境之后 想要在Pycharm中使用 那么就要在Pycharm中导入 我这里使用的pycharm professional 2023 2这个版本 下面是详细步骤 1 打开File gt Settings 2 找到Proje
  • 从0开始搭建高仿华为云教育课堂官网(一)创建项目和搭建导航栏

    之前上过一些华为云的前端教育课程 最终考核是以vue为基础搭建一个华为云教育课堂的官网 网址如下 https classroom devcloud huaweicloud com home 下面记录一下搭建网站的全过程 使用vuecli 4
  • android 杀死三方app

    这是杀死后台应用 并且非保护程序 非系统程序 1 ActivityManager am ActivityManager context getSystemService Context ACTIVITY SERVICE Log i kill
  • JQuery 判断访问的浏览器是pc还是手机

    摘要 以下代码用于JQuery判断访问的浏览器的类型 判断访问类型是电脑还是手机 author 2017年9月27日 function var mobile flag isMobile true为PC端 false为手机端 if mobil
  • c语言求一个字符数的补码,C语言-数据类型(原码、反码、补码)

    1 原码 在数值前直接加一符号位的表示法 例如 符号位 数值位 7 原 0 0000111 B 7 原 1 0000111 B 注意 a 数0的原码有两种形式 0 原 00000000B 0 原 10000000B b 8位二进制原码的表示
  • 编译CGAL

    抛弃CMake 长期以来 我一直以为编译CGAL是一项十分艰巨的任务 直到有一天 我决定彻底抛弃繁复的CMake 转而使用简简单单的QMake 这才发现 编译CGAL是如此简单的一个事儿 注 本文所指的CGAL是指CGAL4 14及之后的版
  • Web服务器群集:Tomcat配置https证书

    目录 一 理论 1 SSL 2 HTTPS协议和HTTP协议的区别 3 https证书配置 4 tomcat强制使用https 二 实验 1 https证书配置过程 2 tomcat强制使用https 三 总结 一 理论 1 SSL 1 概
  • 应用RFID技术的智慧图书馆系统带来了哪些便利?

    RFID技术是一种非接触式的自动识别技术 它通过射频信号自动识别目标对象并获取相关数据 识别工作无须人工干预 可工作于各种恶劣环境 RFID技术可识别高速运动物体并可同时识别多个标签 操作快捷方便 RFID技术主要由三个部分组成 标签 由耦
  • 最流行的自动化测试工具,总有一款适合你(附部分教程)

    前言 在自动化测试领域 自动化工具的核心地位毋庸置疑 本文总结了最顶尖的自动化测试工具和框架 这些工具和框架可以帮助组织更好地定位自己 跟上软件测试的趋势 这份清单包含了开源和商业的自动化测试解决方案 1 Selenium Selenium
  • App Tamer for Mac(CPU智能控制管理) v2.8.1

    App Tamer 是一款针对 macOS 平台的软件 它可以帮助用户有效地管理和控制正在运行的应用程序 通过优化 CPU 使用率 减少电池消耗和降低系统负载 App Tamer 提供了更加流畅和高效的计算体验 App Tamer mac软
  • 程序员下班儿后如何提升自己?

    作为一个程序员 下班后提升自己是非常重要的 以下是GPT提供的一些建议 1 学习新技术 技术行业发展迅速 不断学习新技术是保持竞争力的关键 了解行业趋势 选择合适的新技术进行学习和实践 2 参与开源项目 积极参与开源项目可以提高自己的编码能
  • 【MATH6005-Introduction to Python and MATH6181-Python & Forecasting】

    提示 文章写完后 目录可以自动生成 如何生成可参考右边的帮助文档 Mid module Assignment Assignment 1 TASK1 Function prototype Function Behavior atributes
  • vue实现浏览器桌面通知

    浏览器桌面通知 当浏览器最小化 或者切换到其他标签页不在当前系统页面 或在其他页面时依然可以显示通知 使用前注意 生产环境地址必须为https协议 开发环境可以用localhost IP地址 且必须允许显示通知才能显示桌面通知 存在兼容性问
  • golang urfave/cli 命令包

    官方文档 https godoc org github com urfave cli 提供了一个命令行框架 go get github com urfave cli import github com urfave cli 导入包 cli
  • GET和POST之间的主要区别

    1 GET是从服务器上获取数据 POST是向服务器传送数据 2 在客户端 GET方式在通过URL提交数据 数据在URL中可以看到 POST方式 数据放置在HTML HEADER内提交 3 对于GET方式 服务器端用Request Query
  • 认识动态规划

    你的打赏是我奋笔疾书的动力 概念篇 线性规划 下图给出了模型 其中目标函数和约束条件里面的不等式函数都是关于xi的线性函数 这类问题都有一些不错的求解方式 整数规划 若在线性模型中 变量限制为整数 则称为整数线性规划 即为整数规划 可见整数