动态规划范文

时间:2023-03-11 12:01:43

动态规划

动态规划范文第1篇

【关键词】动态规划;矩阵连乘问题;最优子结构;递归算法;重叠子问题

1.动态规划

动态规划[1]是运筹学的一个分支,是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法――动态规划。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用,例如库存管理、资源分配、设备更新、排序、装载等问题。

动态规划是一种将复杂的问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。

1.1 基本思想

动态规划算法的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。适合于用动态规划法求解的问题,经分解得到的子问题往往不是相互独立的,可以用一个表来记录所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,从而得到多项式时间算法。[2]

1.2 求解问题特征

动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和子问题重叠性质。

1.2.1 最优子结构

原问题的最优解包含着其子问题的最优解,这种性质称为最优子结构性质。在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

1.2.2 子问题重叠

递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次,这种性质称为子问题的重叠性质。动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。

1.3 设计步骤

3.总结

动态规划方法中每步所作的选择往往依赖于相关子问题的解,因而只有在解出相关子问题后才能做出选择所以动态规划,算法通常是以自底向上的方式解各子问题的解进而求出原问题的解。动态规划是一种很灵活的算法设计方法,在动态规划算法的设计中,类似的技巧还有很多。要掌握动态规划的技巧,有两条途径:一是要深刻理解动态规划的本质,这也是为什么一开始就探讨它的本质的原因;二是要多实践,不但要多应用,还要学会从应用中探寻规律,总结技巧。运用动态规划算法解决的还有很多现实问题,如背包问题、最长公共子序列问题、凸多边形最优三角剖分问题、电路布线等问题,在本文中没有介绍。动态规划算法虽然复杂,但只要掌握它的本质特征并多加练习,就可以灵活运用,并加以扩展,来提高程序的时效性。

参考文献

[1]百度百科.http://

[2]王晓东.计算机算法设计与分析(第四版)[M].北京:电子工业出版社,2012.

[3]王晓东.计算机算法设计与分析(第四版)[M].北京:电子工业出版社,2012.

动态规划范文第2篇

关键词:动态规划;编程;技巧

中图分类号:J954 文献标识码:A 文章编号:1007-9599 (2012) 16-0000-02

首先,第一类动态规划的题目。这类问题往往直接采用递推的方式从前往后一步步记录下每一步的结果,最后得出问题的解就可以了。我们来看一个例子:

“数字三角形问题”。问题的大意是:给定一个由n行数字组成的数字三角形,如下面所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。

5(行数)

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

这道题很明显要用动态规划算法求解。假设我们要求第i行的最大值,怎么求呢?可能有的人会找每一行最大的数,但这样是行不通的,因为我们要找到一条路径,也就是上一行与下一行选的数必须不能隔数字。那怎么办呢?我们如果要找第i行的最大值,可以从第i-1行来找。对于第i行的每一个数字,通过选第i-1行中符合题目要求的数字,求出到该数的路径的最大值。我们最后求出的第n行的最大值中求出最大的即可。

附上代码(c语言):

#include

int main()

{

int n,i,j,max;

int num[120][120];

int sum[120][120];

scanf("%d",&n);

for(i=1;i

{

for(j=1;j

{

scanf("%d",&num[i][j]);

}

}

sum[1][1]=num[1][1];

for(i=2;i

{

for(j=1;j

{

if(j==1)

{

sum[i][j]=sum[i-1][j]+num[i][j];

}

else if(j==i)

{

sum[i][j]=sum[i-1][j-1]+num[i][j];

}

else

{

if(sum[i-1][j-1]>sum[i-1][j])

{

sum[i][j]=sum[i-1][j-1]+num[i][j];

}

else

{

sum[i][j]=sum[i-1][j]+num[i][j];

}

}

}

}

max=0;

for(i=1;i

{

if(sum[n][i]>max)

{

max=sum[n][i];

}

}

printf("%d\n",max);

return 0;

}

其次,第二类动态规划算法。这类动态规划算法往往不像第一种那么直接往后递推就可以了。这类问题往往要借助于前面求解过的子问题,而且不一定是刚刚求解过的子问题。其实这类问题有点分治法的意思,但是可以记录下已经求解过的子问题的结果,不必再在后面的问题中求解一遍。我们来看一个典型的例子——“0-1背包问题”:

题目大意是,有一个背包容量为v,还有若干个宝物,第i个宝物的价值为v[i],容量为w[i]。试设计一个算法,在背包容量范围内,把总价值最大的宝物总和加入到背包内。数据输入实例:

4(宝物个数) 6(背包容量)

1 4 (第一个宝物的容量和价值,下同)

2 6

3 12

2 7

这个问题怎么分析呢?我们假设已经装到第i个宝物了,容量为m时最大价值为f[m]。那么这时最大的价值为多少呢?如果第i个宝物装到了背包中,那么这时价值为f[m—w[i]]+v[i],如果不装呢,价值仍为f[m]。取其中最大值。这里求数组f的各个元素时,我们可能需要前面求过的子问题。

附上代码(c语言):

#include

int main()

{

int dp[13000],n,m;

int w[3500],d[3500],i,j;

scanf("%d%d",&n,&m);

for(i=1;i

{

scanf("%d%d",&w[i],&d[i]);

}

memset(dp,0,sizeof(dp));

for(i=1;i

{

for(j=m;j>=w[i];j--)

{

if(dp[j]

{

dp[j]=dp[j-w[i]]+d[i];

}

}

}

printf("%d\n",dp[m]);

return 0;

}

最后,我们来看第3类动态规划问题。这类动态规划牵涉到了数据结构的内容,对我们这部分的学习以及抽象出算法模型的能力有比较大的要求。我们必须先对这部分的数据结构有自己的理解和体会,然后才能用算法的知识求解这类问题。我们来看一个问题:

“加分2叉树”。 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:

subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数

若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;

(1)tree的最高加分

(2)tree的前序遍历

【输入格式】

多组测试数组,对于每组:

第1行:一个整数n(n

第2行:n个用空格隔开的整数,为每个节点的分数(分数

【输出格式】

第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。

第2行:n个用空格隔开的整数,为该树的前序遍历。

【输入样例】

5

5 7 1 2 10

【输出样例】

145

3 1 2 4 5

这个问题就用到了2叉树的知识。我们首先得对树有一定的了解,必须了解树的各种遍历方式,先序遍历,中序遍历,后序遍历。

先序遍历,也叫先根遍历,遍历的顺序是,根,左子树,右子树

中序遍历,也叫中根遍历,遍历的顺序是,左子树,根,右子树

后序遍历,也叫后跟遍历,遍历的顺序是,左子树,右子树,根

然后我们来分析这道题。

设节点d为最优的根节点,那么可以把这棵树分成[1,d-1]和[d+1,n],这颗树的加分为子树[1,d-1]的加分与子树[d+1,n]加分的乘积与d的加分的和,而[1,d-1]和[d+1,n]的加分也可也一定是最优加分,所以这个题具有最优子结构,那么可以用动态规划。

设f[k,j]为子树k到j的最高加分,求f[k,j]的最优值,就要求f[1,d-1]和f[d+1,n]的最优加分,那么枚举根节点p,则有

f[k,j]的最优值=f[k,p-1]*f[p+1,j]+v[p](k

规划方程为f[k,j]=max{f[k,p-1]*f[p+1,j]+v[p]}(k

但是,根据题目,左子树或右子树可以为空,即当k=p或p=j,于是对此特殊处理,求出这种情况下的加分,再进行比较。最后,我们根据数据的中序遍历求出先序遍历。(由于篇幅,就不附加代码了)。

动态规划范文第3篇

关键词:动态规划;模板匹配;特征距离矩阵

DOIDOI:10.11907/rjdk.171142

中图分类号:TP312

文献标识码:A 文章编号:1672-7800(2017)06-0037-03

0 引言

在计算机领域,常需要将实验数据与预先设定好的模板进行匹配。图像处理领域中的图像检索、图像分割、图像拼接、图像检测、视频编码等,就需要运用到模板匹配技术。模板匹配技术在图像处理领域的具体应用可以简单分为两大类:基于特征点的匹配技术、基于像素灰度的匹配。基于特征点的匹配往往被更高级的机器视觉类任务采用,而在图像处理中,基于特征的匹配方法由于抽取的点、线、特征子等特征容易受到视角变换、遮挡等问题的干扰,会影响到最终匹配结果的质量,同时特征抽取方法的时间复杂度较高,对于实时性是一个挑战。基于像素灰度的模板匹配方法,只需要设定好匹配的模板尺寸与遍历方式,算法简洁、稳定性高,适合图像处理与计算机视觉问题中的底层预处理。但其也存在一些缺点,如噪声、光照引起的灰度变化,且运算数据量大,基于像素灰度的匹配算法也无法避免图像数据与模板匹配过程可能带来的高复杂度问题。

迄今为止,模板匹配技术已经被广泛应用到图像处理的实际问题中,并取得了一系列成果。例如,王倩倩[1]将模板匹配问题应用到藻类图像的识别问题中,李厚军[2]将模板匹配问题应用到眉毛的识别问题中,陈莹[3]将模板匹配方法用于增强微光图像,王正等[4]将模板匹配引入到图像编码中的调色板更正上,提高了图像编码效率,王志衡,郭超等[5]将模板匹配方法应用到了新闻图像字母行切分之中,张盼盼[6]等将模板匹配方法应用到了数字识别过程中,陈宁等[7]将该方法应用到集装箱识别与匹配的问题中。然而,采用上述方法在面临大数据量的数据时,也存在复杂度较高的问题。因此,如何进一步优化模板匹配问题有待进一步研究解决。

动态划方法(Dynamic Programming)早期诞生于运筹学,是一种迭代求解最优的方法。近年来,动态规划方法作为算法设计策略中求解最优子结构的一种重要思想,被广泛引入到计算机问题求解之中。动态规划求解计算机问题的基本思想是,将待求解问题分解成若干个结构相同的子问题,在求解过程中保存已求解子问题的答案并在后续求解过程中,有效利用之前求解的答案协助当前问题求解。由于后续问题在求解过程中已经遇到了需要之前已经求过的子问题,因此大大提高了求解效率[8-11]。可以简单地将动态规划算法分为基于线性的动态规划算法、基于树形的动态规划算法、基于区域的动态规划算法、基于背包的动态规划算法。具体采用何种动态规划方法应针对具体问题作具体分析,例如,有学者[12-13]在语音识别与动作识别等具体领域尝试采用动态规划算法尝试优化求解。但往往只是将动态规划算法应用到某一具体问题,尚未对图像处理中的模板匹配问题进行动态规划算法实现。

综上,鉴于动态规划方法的自身特性及当前图像处理在解决模板匹配问题上的不足,本文提出了一种采用动态规划解决模板匹配的方法,首先给出图像数据与模板的匹配问题,并对该问题进行符号化和相应的理论分析,此后采用动态规划的方法解决模板匹配问题,并对传统动态规划解决方法在时间复杂度上进行改进。相较于传统模板匹配方法,采用本文提出的方法可以将时间复杂度减少一个数量级。

1 问题分析与解决

图像模板匹配算法的过程可以简单归纳为:首先采用某一尺度的模板遍历所有数据(例如整幅图像),此后计算模板与模板在整个图像中所对应区域的匹配程度,最后在数据中找到与模板匹配程度最高的区域。对于一幅图像数据S而言,若图像的尺寸大小为H*W,模板T的尺寸为P*P,模板匹配算法需要在图像数据上进行遍历,并计算模板与模板覆盖区域的匹配程度,将模板覆盖到一个图像区域并计算匹配度的过程约定为一个动作。设有一组试验动作序列:V=(V0,V1,…,VM) 和一组模板动作序列T=(T0,T1,…,TN),(M>N),两组序列都满足动作的时间顺序,这里试验动作数据中的每个动作都必须出现在匹配路径中,而模板动作序列不做此要求。计算模板与图像对应位置的匹配程度,可以根据需求采取不同的度量方式,如欧式距离、光度距离与几何距离等。模板的移动可以采用Zigzag的方式实现。则上述模板匹配可以得到有效的距离矩阵,可以在该距离矩阵的基础上设计动态规划优化解决方案。这里,假设试验动作数为M=15,模板动作数为N=10。

1.1 问题符号化及分析

为了方便地表达该问题,采用3个矩阵进行存储和计算,如图1所示。一个是矩阵A,用来存放原始数据;一个是矩阵B,用来存放计算过程的局部最优值;一个是矩阵R,用来记录局部最优值所对应的路径。

1.2 问题解决

1.2.1 局部最优值计算

对于上述问题,采用动态规划思想进行解决,其基本思路如下:首先,试验动作从V0开始,由于它是第一个试验动作,前面没有其它动作,因而无论它选择哪一个模板,都可看成是当前的最优值;然后,考查第二个试验动作V1,如果V1选择的模板动作是T0,那么试验动作V0选择的模板只能是T0,这时它的最小值为a0,0+a1,0,同时在矩阵R中r0,0位置记录该局部最优值所对应的模板序号;如果V1选择的模板动作为T1,那么试验动作V0可以选择的模板是T0或T1,显然,只有取a0,0和a0,1中的最小值,与a1,1相加后可得V1在选择模板动作T1时的最优值,同时在矩阵R中r0,1位置记录该局部最优值所对应的模板序号;如果V1选择的模板动作为T2,那么试验动作V0可以选择的模板就可以是T0、T1或T2,这时,需要取a0,0、a0,1、a0,2中的最小值,与a1,2相加后可得V1在选择模板动作T2时的最优值,同时在矩阵R中r0,2位置记录该局部最优值所对应的模板序号;如果V1选择的模板动作为Tj,j=3,…9,则依次类推。

其中,k的最大值是第M层叶结点的个数。度为p的树中第i层至多有pi-1个节点(i>1),该问题求解的树的度p=3,则第M=15层至多有3M-1=315-1个结点,试验中k的最大值为16,通过分析可以得出该问题的时间复杂度为O(16*M)。

综上分析,文中给出的算法在求模板匹配的最优解时,其对应的时间复杂度为O(MN)+O(KM),即max(O(MN),O(KM))。若从p叉树的生成角度考虑,算法的时间复杂度为O(MN)+O(nodes),即max(O(MN),O(nodes))。

3 结语

针对传y模板匹配算法在应用图像处理问题时遇到的时间复杂度过高等问题,对数据与模板匹配的过程进行优化,提出了一种基于动态规划算法加以实现的方法,算法的时间复杂度为max(O(MN),O(KM))。利用本算法,可以将模板匹配过程的复杂度大大减小,也不需要对数据进行过多处理,而且程序编写简单,各方面比原算法和目前已有文献中提到的改进算法都有很大提高。

可以看出,未来无论是计算机处理领域的模板匹配问题,还是日常生活生产中经常遇到的“试验数据和事先存储好的模板动作进行匹配”及类似问题,本文所提出的算法都具有一定应用前景。

参考文献:

[1]王倩倩.基于聚类的模板匹配显微细胞图像分割算法的研究[D].重庆:重庆大学,2015.

[2]李厚军.快速模板匹配方法及其在眉毛识别中的应用[D].北京:北京工业大学,2015.

[3]陈莹.基于FPGA的微光图像增强和模板匹配研究[D].北京:中国科学院大学,2014.

[4]王正,陶品,冯立新,温江涛,杨士强.基于模板的调色板方法[J].计算机辅助设计与图形学学报,2016,28(7):1146-1151.

[5]王志衡,郭超.基于模板匹配的新闻图像字幕行切分算法[J].北京邮电大学学报,2016,39(3):49-53.

[6]张盼盼,张颖颖.模板匹配与八邻域分析法在数字细化预处理中的应用及比较[J].软件导刊,2016,15(5):210-211.

[7]陈宁,王胜,黄正文.基于特征匹配的集装箱识别与定位技术研究[J].图学学报,2016,37(4):530-536.

[8]THOMAS H CORMEN,CHARLES E LEISERSON.Introduction to algorithms[M].Second Edition.Massachusetts:The MIT Press,2001.

[9]王晓东.计算机算法设计与分析[M].第2版.北京:电子工业出版社,2005.

[10]徐孝凯,贺桂英.数据结构(C语言描述)[M].北京:清华大学出版社,2004.

[11]唐策善,李龙澍,黄刘生.数据结构――用C语言描述[M].北京:高等教育出版社,2003.

[12]魏星,周萍.改进型蚁群算法的语音动态规划研究[J].仿真应用研究,2011,228(5):402-409.

动态规划范文第4篇

【关键词】数学模型 动态规划 多阶段投资决策

一. 引言

多阶段决策问题是投资者在连续的几个投资阶段中每个阶段里都进行投资, 其目的是使得到最后一个投资阶段结束时, 投资者进行多次投资的收益总和尽可能大, 这些投资阶段之间是相互关联的, 面对众多的投资项目, 如何合理的安排资金成为决策部门关心的焦点, 而动态规划方法的关键在于正确写出基本递推关系式, 首先将问题的过程分成几个相互联系的阶段, 恰当的选取状态变量和决策变量及定义最优值函数, 从而把一个大问题化成一族同类型的子问题, 然后逐个求解, 即从边界条件开始, 逐阶段递推求优, 在每个子问题求解过程中均利用了它前面的子问题的最优结果, 依次进行, 最后一个子问题所得到的最优解就是整个问题的最优解.

二. 动态规划在多阶段投资组合中的应用

1.案列介绍

假设某公司决定将60万元投资4个工厂, 该公司希望通过合理分配资金确定最优组合,使所获得的投资收益最大, 经调查各个工厂所获得收益和投资额如图所示.

投资额与收益额 (单位: 万元)

2.建立动态规划模型

由于动态规划问题的特殊性, 我们将它看作一个多阶段决策问题, 分阶段来解决, 为此, 我引入以下各参数:

(1)s――投资总额

(2)n――投资组合中的项目数

(3)uk――决策变量,分配给第K个项目的资金

(4)sk――状态变量,分配给前k个工厂的资金

(5)sk-1=sk-uk――分配给前k-1个工厂的资金

(6)gk(uk)――阶段目标函数,对第 个项目投资 所获得的收益

(7)fk(s)――目标函数,以数量为 的资金分配给前 个工厂所得到的最大利润值

当k=1时,

当1

3. 利用动态规划模型求解

第一阶段: 求f1(s) , 则

第二阶段: 求 ,

最优策略为(40,20), 此时最大利润值f2(60)=120万元.

同理可得其他f2(u2)及最优策略

第三阶段: 求f3(u3),

同理可求得其他f3(u3)的值

第四阶段: 求f4(60), 即问题最优策略

所以最优策略为(20,0,30,10), 最大利润为160万元.

4.模型的意义分析

本文针对多阶段资产投资问题, 以最终的总收益尽可能大为决策目标的资产投资组合问题的一个多阶段动态规划决策模型, 利用动态规划的顺序法求得多阶段投资的整休最优投资组合.

参考文献:

[1]胡元木,白峰. 动态规划模型在股票投资组合中的应用, 山东社会科学, 2009;09(39).

[2]刘锐.基于动态规划的企业投资决策模型 科学技术与工程, 2009; 09(22).

动态规划范文第5篇

[关键词] 物流配送 动态规划 优化

一、问题的提出

物流配送是物流管理活动的一项核心技术。要高效地完成配送任务就得对配送路线进行合理安排。目前,出现了较多关于物流配送的研究,如物流网络及其优化、物流配送的动态规划算法等。

但上述的研究仅将配送路径最短作为目标函数,有其局限性且过于简化。在实际的运作中,货物经过每层配送时中,并非只是简单地流经、通过,而是要进行存储、装卸、转运等必要的运作,这就产生了不可忽视的费用(统称为存转费)。故物流配送是一个多层次运作,不光考虑运输费用,还要关注存贮费用,且两者必须统筹兼顾。

二、物流配送优化模型

物流配送的运营方式从本质上讲是运输、存转、运输、存转……循环交替的复杂的多阶段过程。故可以利用动态规划的思维来考虑问题。

该动态规划可分为N个阶段,第i(1≤i≤N)个阶段可供选择的状态(分销商)有Si个,任意阶段i的状态和目标状态之间的费用关系可以用费用矩阵M(r)(共有Si×Si+1个)来表示,每个元素表示阶段i的状态mi和阶段i的目标状态mi+1之间的费用消耗。特别地,规定表示第i阶段目标状态的存转费。如果mi到mi+1没有配送路线的设计,则可认为其间的费用为a∞(mi,mi+1)。则物流配送优化模型为一个二元函数:min F=K+C (K为总运输费,C为总存转费)。

三、模型求解

依据动态规划思维及贝尔曼最优化原理,则模型的求解可化为特殊的矩阵运算。其求解思想是:将存转费转化到运输费当中去,再利用矩阵运算进行问题的求解。

定义1阶段i的状态到阶段i+1的目标状态之间的费用在经过阶段i+1时的状态t(同时也是阶段i的目标状态)时第i阶段目标状态的存转费的转化为:

存转费的前向化:

存转费的后向化:

定义2阶段i的状态到阶段i+1的目标状态之间的费用在经过阶段i+1时的状态t(同时也是阶段i的目标状态)时为:

定义3阶段i到阶段i+1的的费用矩阵可以通过如下的计算求得:

M(i)M(i+1)=

定理 多个连续阶段i,i+1,L,j的费用矩阵的复合关系记为。

四、实例分析

上图是一个简单的有向网络图。具体的计算过程如下:

1.存转费的转化。(本文采用存转费前向化方法)

则有:

2.费用矩阵为:

3.利用逆序解法,有

同理有:

可见,图中的最小费用为51,而且最优的配送路线为A,B1,C3,D2,E。

五、结束语

本文提出的基于矩阵运算的最小费用配送路线求解方法,为决策者提供了一种新的优化方案。另外,还可以进一步研究多品种、分批量的配送优化等问题。

参考文献:

[1]石永泽:物流技术应用讲座[J].物流技术,1996,(5)

[2]刘虹孙金梅陈德运:一种基于供应链管理的动态规划算法[J].哈尔滨理工大学学报,2003.(4)

动态规划范文第6篇

【关键词】目标成本 动态规划模型 顾客满意度

供应链成本管理引入目标成本,旨在控制供应链单个节点企业在满足目标成本约束的前提下为顾客提供满意度最高的商品,这是供应链成本控制关注的核心问题,而目前国内外关于供应链成本控制的研究大多集中在供应链目标成本法,供应链利润最大化和供应链成本缩减等方面,很少考虑到顾客的满意度是否达到最大。本文试图在供应链目标成本已经分解的前提下,用动态规划模型控制供应链单个节点企业内部目标成本的达成过程,使其成本控制在目标成本以内的同时,实现最大化顾客满意度以及最大化企业输出价值(徐龙秀,2010)。

一、 目标成本达成的动态规划模型

动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解(刘博,2004)。它是一种逆向求解方法,即从最后状态出发,在目标的约束下,逐步转移到最初状态,逐级地选择最优控制,并逐级计算最优性能指标,适用于求解多阶段最优决策。动态规划模型的五要素包括:状态集、决策集、状态转移方程、报酬函数和指标函数(汪颖,2007;徐龙秀,2010)。

而目标成本的达成过程存在不同的阶段,每个阶段又有不同的状态,这要求企业在动态的目标成本达成过程中进行多阶段决策,依次采取一系列措施来解决整个过程的最优化问题,所以,在目标成本的达成过程中引入动态规划方法是可行且必要的。

(一)动态规划模型建立的基础

供应链成本控制系统的概念模型已经建立,如图1所示,共分为四个层次:第一层,供应链总成本分解到各节点企业;第二层,企业内部总成本分为管理费用()、销售费用()、制造总成本()和财务费用();第三层,把第二层中的制造总成本分解为工料成本()和制造费用();第四层,把第三层中的工料成本分解为材料成本()和工资成本()。其中, 至 仅指企业参与本条供应链所产生的费用,而不是企业内部产生的所有费用。具体的供应链成本控制系统自上而下是目标成本分解的过程,自下而上是目标成本达成的过程。

动态规划模型的前提还有,供应链的总目标成本已经根据顾客愿意支付的产品价格和行业目标利润确定,供应链总成本也已经根据目标成本法完成了从第一层到第四层的逐层分解,设要控制的节点企业分解得到的目标成本为。动态规划模型的目的是使节点企业在达成目标成本的前提下,实现顾客满意度的最大化,也就是节点企业输出的最大化。

(二)动态规划模型的建立

为提供顾客满意的产品,多个节点企业共同构成供应链,供应链上承载着一系列的价值活动,每项价值活动都由特定的节点企业完成,而完成价值活动会产生一定的成本费用,最终输出令顾客满意的产品或服务(徐龙秀,2010)。由于考虑的是单个供应链节点企业的成本控制问题,即该企业在满足目标成本约束的条件下,输出最大化顾客满意度的产品,因此该动态规划模型只需要考虑供应链控制系统的第二至第四层。

当逆推到k=1时,指标函数是和的函数,由于节点企业分解得到的目标成本为,在目标成本的约束下,即,,可首先求得决策变量,然后再根据状态转移方程可求得决策变量和,这样就可得到各层的最优费用分配,以使单个节点企业在满足目标成本约束的前提下,达到输出顾客满意度最大的产品。如果把该模型用于供应链的所有节点企业,就可使得整个供应链输出值最大化,使顾客满意度最大化。

二、 实例应用

企业A作为供应链的核心企业经过市场调查,欲开发一款新产品,供应链结构已经用TOPSIS方法构建完成,共由五个节点企业组成。新产品的目标成本已经根据供应链成本控制系统层层分解,分解得到的目标成本值如图2所示。

由上表可知,为了使该节点企业在满足目标成本约束条件下实现最大化输出、最大化顾客满意度,需要继续投入制造费用259.25元,同时应当缩减期间费用1 013.75元。

三、结论

本文在供应链成本控制模型的基础上,分析供应链单个节点企业内部的成本费用与企业输出质量――顾客满意度之间的关系,用动态规划模型控制供应链节点企业内部目标成本的达成过程,使单个节点企业的输出达到最优,也就是顾客的满意度最大。动态规划模型可以使节点企业在达成目标成本的同时,实现顾客的满意度最大,可以实现供应链降低成本和提高顾客满意度的双重目的。但在量化输出质量函数时存在一定的困难,有待进一步研究。

(韩庆兰教授系博士生导师;黄凤为硕士研究生)

参考文献

[1] Taoyong Su,Xinghui Lei. Research on supply chain cost reduction based on process and time analysis[J].IEEE International Conference on Industrial Engineering and Engineering Management,2008:1625-1629.

[2] 杜红,冯明.基于作业的目标成本法在供应链成本控制中的应用[J].北京:建筑经济,2006(12):59-62.

[3] 陈丽华,颜涛,等.供应链成本分析和资源优化配置模型[J].北京:中国管理科学,2004(12):473-477.

[4] 韩庆兰.供应链成本控制模型的构建研究[J].长沙:中南大学学报(社会科学版),2004(3): 312-316.

[5] 杜栋.管理控制学[M].北京:清华大学出版社,2006.

[6] 韩庆兰,徐龙秀.基于约束的供应链节点企业选择[J].北京:商场现代化,2010(16):39-40.

[7] 徐龙秀. 供应链资源最优配置下的成本控制研究[D].长沙:中南大学硕士论文,2010-11-01.

[8] 汪颖.单体型和基因型问题的优化模型和算法[J].大连理工大学博士论文,2007-10-01.

动态规划范文第7篇

关键词:动态规划技术;配电网;恢复供电;电力系统;故障

为了实现配电网恢复供电,全面提升配电网供电水平,应提高动态规划技术的利用效率,扩大该技术在配电网运行中的实际应用范围,促使电力生产效益最大化目标得以实现。因此需要结合配电网的实际概况,充分发挥动态规划技术优势,找出配单网恢复供电的最佳路径,从而为其正常工作提供保障,保持我国电力行业良好的生产效益及社会效益,提高电网供电质量的同时满足用户用电的多样化需求。

1 配电网故障区域恢复供电的最佳路径分析

为了实现配电网恢复供电,确保配电网能够处于正常的运行状态,应选择其故障区域恢复供电的最佳路径,即发生故障时配电网络重构。这样的工作机制价值在于:能够在最短的时间内使非故障区域保持正常供电,为后续配电网供电生产计划顺利实施提供保障。同时,通过故障情况下配电网络重构的有效操作,能够使线路负载容量控制在合理的范围内,降低线损率,减少供电企业不必要的经济损失。

当期形势下配网自动化研究领域对快速实现故障隔离、快速恢复配电网故障区域供电关注较多,开展了一系列的有关配电网恢复供电最佳路径的研究工作,一定程度上为配电网故障的有效处理及预防提供了参考信息。因此,需要深入分析配电网故障区域恢复供电最佳路径,确保各种技术支持下配电网故障发生时能够在最短的时间内恢复供电,保持其良好的生产效益。

现阶段在配电网故障区域恢复供电路径研究过程中关注的是城市交通网络中的最短路径问题。在研究这类问题过程中,可将其划分为单元最短路径算法与基于启发式搜索最短路径算法进行研究。单元最短路径算法的相关内容包括以下方面:

(1)基于GIS空间查询语言方面的最短路径。结合该研究方法的实际概况,可知其目前依旧停留于理论阶段,并未在实践活动中得到真正的运用。像MAX中的空间查询语言,虽然研究人员在完备性方面进行了充分的论证,对范围、时态查询进行了应用分析,但在实践生产中未进行充分利用,需要研究人员加大对这种路径的研究力度。与此同时,在开展GIS空间研究工作的过程中,一定条件下也可关注其他最短路径手段研究,但研究中应根据不同的应用背景及应用领域,选择有效的GIS空间查询语言方面的最短路径,满足实际生产活动的各种需求。某配电网恢复供电方案内容如表1所示。

(2)基于功能模块思想路径。运用动态规划技术实现配电网恢复供电,也应考虑基于功能模块思想路径的合理运用。根据不同的分类方法,布置相应的功能模块,实现对单元最短路径问题的高效处理。像神经网络法、人工智能支持下的启发式搜索算法等,适用于不同的应用背景及应用领域,在空间或者时间复杂程度中有所反映。通过对基于功能模块思想路径研究工作开展,能够为配电网故障区域恢复供电中单元最短路径问题处理提供参考信息。

运用启发式搜索最短路径算法研究单元最短路径问题时,应充分考虑这种方法中所包含空间有效方向的可控参数法。在这种参数法的支持下,能够对相关系数进行有效调节,促使有效方向上路径选择的有效性,促使单元最短路径问题处理能够达到预期效果,为配电网故障区域快速恢复供电提供保障。

2 配电网故障区域恢复供电最佳路径选择方法分析

结合当前配电网故障区域恢复供电路径选择研究及实践活动状况,可知其最佳路径选择问题处理复杂,主要在于其需要解决的是多目标最佳路径问题。因此,在开展配电网非故障区域恢复供电最佳路径选择的过程中,应注重综合分析。具体表现在以下方面:

(1)配电网故障区域选择恢复供电路径时,应确保馈线负荷设置有效性,满足相关的技术规范要求。当配电网供电质量不断提高时,恢复供电时间将会缩短。同时,配电网正常供电时应减少其开关控合次数,不断降低线损率,有利于保持配电网良好的供电水平。某配电网故障恢复软件总体结构示意图如图1所示。

(2)作为运筹学的重要组成部分,动态规划技术在实现配电网恢复供电最短路径方面明确相关的要求。这种技术在求解决策过程中最优问题应用方面有着一定的优势:通过将多个阶段的过程问题按照合理的方式转化为单阶段问题,通过依次求解的方式进行解决,实现问题的高效处理。

比如,在研究复杂配电网络时,由于其中包含多个电源点、分支点及联络开关使得配电网故障区域恢复供电最佳路径选择难度加大,此时,可通过动态规划技术的合理运用,将故障区域恢复供电最优路径视为故障区域各联络开关及电源点,通过解决不同电源点出发到所有联络开关之间的最短路径问题,能够实现配电网恢复供电,将复杂的多目标路径问题通过转化为单阶段问题进行处理,提高实际问题处理效率。

3 结束语

市场经济体制改革步伐的不断加快,对电力系统运行中配电网供电水平提出了更高的要求,需要电力技术人员能够加强动态规划技术的合理运用,找出配电网恢复供电的最佳路径及相关的路径选择方法,满足配电网正常供电的实际需求,促使其能够长期处于稳定、高效的运行状态。与此同时,应不断完善配电网络相关的各种技术规范,加强配电网运行状况的深入分析及运行状态的严格把控。

参考文献

[1]王熙.基于负荷曲线和多技术的含微电网配电网动态供电恢复[D].重庆大学,2014(03).

[2]张瑶瑶.智能配电网的灾害评估及应灾恢复方法研究[D].东北大学,2014(05).

[3]冉 泉.智能配电网自愈控制技术研究[D].西南交通大学,2015(03).

动态规划范文第8篇

关键词:动态规范 路径图 多阶段决策

一、动态规划简介

动态规划是运筹学的一个分支,它是解决多阶段决策过程的最优化的一种数学方法。美国数学家贝尔曼(R.Bellman)等人在1951年根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相关联的单阶段问题,然后逐个加以解决,从而创建了解决最优化问题的一种新的方法。动态规划的方法在工程技术、企业管理、工农业生产及军事部门中都有广泛的应用,并且获得了显著的效果。可以用来解决最优路径问题、资源分配问题、设备更新问题、生产调度问题、库存问题、装载问题、排序问题、货郎担问题、采购与销售问题、限期采购问题、生产过程最优控制问题等。

二、建立动态规划模型的步骤

动态规范模型在日常生产、生活中应用广泛,建立动态规范模型一般遵循以下步骤:

(1)将问题的过程划分成恰当的阶段(一般按时间或空间的先后顺序);

(2)正确选择状态变量SK ,使它既能描述过程的演变,又要满足无后效性;

(3)正确设立决策变量uk ,明确每阶段的允许决策集合Dk(Sk );(通常选择所求解问题的关键变量作为决策变量)

(4)根据第K阶段的状态变量和决策变量正确写出状态转移方程

(5)正确写出指标函数

指数函数应满足下面三个性质:①是定义在全过程和所以子过程上的数量函数; ② 要具有可分离性,并满足递推关系。③函数对变量 Vk+1,n要严格单调。

(6)写出动态规划的基本方程包括边界条件。

(7)求解模型。

三、用路径图求解动态规划问题应用举例

用动态规划的方法求解实际问题通常可以按上面的步骤来建立模型,有部分问题可以化为(最短)路径问题,用路径图能直观的理解上面的算法。

如某建筑公司新购置了四台挖掘机,准备分给甲、乙、丙三个公司,事先请专家调查了各分公司的经营情况,并对各种分配方案进行了经济效益的估计,见下表,其中机器数为0时的收益,是指已有的经营收益,问应如何分配这四台机器,使总的收益为最多?

本题用动态规划的常规方法建模求解可参看[1],下面采用本文要讲的路径图的方法来求解,更直观易懂。

具体解答过程如下:

解:由于有三个公司,所以划分为三个阶段,状态变量 表示第k阶段初分配者手中拥有的机器总数,决策变量 表示第k阶段分配给第k个用户的机器数,状态转移方程为: Sk+1=sk-uk

阶段指标函数: vk(sk,uk)=gk(uk)表示k阶段公司k利用所分到的资源(机器)产生的收益;最优值函数fk(sk) 表示将机器数sk 分配给公司k到公司丙所获得的最大收益:

表示状态变量所取的值,状态连线上小于5的数字表示决策变量所取的值,[数字]表示该阶段的指标值(收益), 表示该状态到最后一个公司的最大收益,粗线条表示最优策略路径,从上图很容易看出最大收益为164万元,最优策略是:u1=3,u2=0,u3=1 ,即分给甲3台,乙不分,丙1台时,总收益164万元最大。

结束语:

对于最段路径问题、资源分配问题、生产与存储计划问题,只要阶段不是太多,状态变量的取值不超过6个,一般可以采用路径图直观的求解出模型的解。

参考文献:

[1]岳宏志,蔺小林,运筹学[M],东北财经大学出版社,2012.8.

[2]姜启源,谢金星,叶俊. 数学建模(第四版)[M],北京:高等教育出版社,2011.

动态规划范文第9篇

【关键词】动态规划;水资源优化配置;MATLAB

0.引言

动态规划是解决多阶段决策过程最优化问题的一种方法,该方法是由美国数学家贝尔曼(R.Bellman)等人在20世纪50年代提出。他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原理,并成功解决了生产管理、资源分配等方面的许多实际问题,从而建立了运筹学的分支——动态规划[1]。MATLAB是一个功能强大的用于矩阵运算的数值计算软件,是决策系统优化计算和设计的有力工具,将MATLAB运用到动态规划中可以达到计算简便的目的[2]。现在利用MATLAB解决动态规划问题的程序不少,但是,如何充分利用MATLAB的特点来优化程序确实一个值得深思的问题。

1.MATLAB程序设计

MATLAB有2种工作方式:一是交互式的命令工作方式,直接在Command Window中输入指令求解。另一种是M脚本文件的工作方式,这种工作方式用来解决指令较多和所用指令结构较为复杂的问题[3]。

由于动态规划问题的特殊性,其涉及的实际问题均需要反复的计算求解,所以在使用MATLAB语言编程中采用最多的是循环结构。MATLAB提供了2种实现循环结构的语句——for语句和while语句[4]。

2.应用实例

有一引水渠,其设计最大流量为6m3/s,为甲、乙、丙、丁4个地区供水。据统计,在给四个地区供水时,不同的供水量产生的效益见表1(效益单位为万元)。那么,如何分配供水量可以使产生的总效益最大。(本实例取自文献[5])

表1 供水量与增产效益的关系

2.1逆序法计算

采用逆序法表格计算,可以得到最优分配方案有3个,分别是(1,2,1,2),(1,2,2,1),(2,2,1,1),最大效益为19万元。

2.2 MATLAB编程计算

2.2.1思路分析

由于本例较为简单,所以不采用M脚本文件的工作方式,直接在Command Window中输入指令即可。

Step1.输入参数

建立A、B、C、D 4个数组,分别来储存供给甲、乙、丙、丁4个地区不同水量时产生的效益。考虑到在动态规划时,某个城市的供水量可以为0,对应的效益也为0,所以A、B、C、D四个数组都应该加入一个元素0。这里采用单下标表示法,分别用i、j、k、

l表示数组A、B、C、D中元素的下标。A(3)=2,表示当i=3时,A中元素为2,即向A供水2m3/s。Step2.找出所有可行解,储存其分配方法和对应的效益,要找出所有的可行解,最简便的的方法是采用循环结构枚举。

①确定循环条件:

循环的限制条件应该是最大设计流量。由于最大设计流量是6 m3/s,现在任意假设一例分配方法以确定循环条件。假设所有的水量全部供给了丁,即l=7,那么此时可有i=j=k=1,得i+j+k+l=10。由于无论是那种分配方法都要满足最大设计流量的限制,所以i+j+k+l=10即为循环条件。由于循环次数是已知的,所以采用for语句循环。

②储存分配方法:

建立一个二维数组E,采用全下标的方法将分配方法存入其中,每一行为一种分配方式。

③储存效益:

建立一个数组d,常用单下标的方式将所有分配方法对应的效益存入其中。

Step3.确定最大效益的值

所有方案的效益都存储在数组d中,所以传统的方法就是采用循环结构遍历数组d中的所有元素以找到最大值。但是在编程中应该尽量避免使用循环结构。因为在循环结构中,要反复进行存储变量间的“存放”操作和算符调用操作,消耗计算时间。MATLAB中为用户提供了大量的现成函数,尽可能多的采用现成函数编程可以使所编程序更可靠、更快速、可读性更好[6]。

①采用循环结构确定最大效益

程序如下:

MAX=d(1);

for n=1:length(d)

if d(n)>MAX

MAX=d(n);

end

end

②采用max函数确定最大效益

由于max(X)求的是数组X中各列的最大值,所以应该先对数组d转置。

程序如下:

MAX=max(d')

可以清楚的看到,采用matlab中现成的max函数比用循环结构更好,不仅使程序的输入得到了简化,同时也使程序的可读性更好。

Step4.确定最大效益所对应的分配方法

数组E中的横坐标和数组d中的下标是一一对应的,即数组E中横坐标为a的行产生的总效益储存在数组d中下标为a的元素中。所以可以采用循环遍历的方法,找到数组d中所有值等于MAX的元素的下标n,在把数组E中对应的第n行输出,即可得到最优分配方法。当然,我们也可以利用matlab中现成的函数find来代替这个循环结构。

①采用循环结构确定最大值

程序如下:

for n=1:length(d)

if d(n)==MAX

E(n,:)-1

end

end

②采用find函数确定最大值

程序如下:

n=find(d==MAX);

E(n,:)-1

2.2.2完整MATLAB程序

为了突出MTALAB语言编程在动态规划中的优越性,这里分别在程序的开头和结尾加入tic和ti=toc,以记录下程序运行需要的时间。但应当注意的是,ti的值受到电脑配置、matlab版本和该程序是否首次运行等因素的影响。

优化后的完整程序如下:

clear all

tic

m=1;

A=[0 3 5.5 7.5 9 10 10];

B=[0 3 6 8 9.5 10.5 11];

C=[0 4 6.5 8.5 9 9 9];

D=[0 3.5 6 7.5 8.5 9 9];

for i=1:7

for j=1:7

for k=1:7

for l=1:7

if i+j+k+l==10

d(m)=A(i)+B(j)+C(k)+D(l);

E(m,1)=i;

E(m,2)=j;

E(m,3)=k;

E(m,4)=l;

m=m+1;

end

end

end

end

end

MAX=max(d')

n=find(d==MAX);

E(n,:)-1

ti=toc

按回车后可以得到以下结果:

MAX =

19

ans =

1 2 1 2

1 2 2 1

2 2 1 1

ti =

0.0255

运行结果表示有三个最优水资源分配方案,即(1,2,1,2)、(1,2,2,1)、(2,2,1,1),最大效益为19万元,程序运行时间为0.0255 s。

2.2.3小结

从本例可以看出,运用MATLAB解决动态规划问题比逆序法更具有可操作性。因为实际工作中要解决的问题往往比本例复杂得多,运用MATLAB编程可以避免繁琐的人工计算。同时,相比之前学者的程序而言,优化后的程序尽量回避了循环结构,充分利用了MATLAB中现成的函数,不仅使程序可读性更好,输入更简便,还大大提高了程序运行速度。经笔者测试,若是采用没有优化的方案编程,程序运行时间为0.0401s,相比之下,优化后的程序运行速度提高了36%,程序代码也由原来的36行减少到了27行。在实际工作的运用中,特别是在复杂的实例中,这种优点将得到更大的体现。

3.结语

本文结合一简单实例,详细说明了MATLAB编程的思路与方法,并给出了程序优化方案。从本例的计算结果可以看出,运用MAYLAB编程解决动态规划问题是实际可行的,而优化后的程序在运算速度、可读性等方面都有提高,这为解决实际工作中的动态规划问题提供了新的思路。但是,如何利用MATLAB的向量化计算特点来做到更深层次的优化还值得更多的思考与探讨。 [科]

【参考文献】

[1]孙赵杰.运筹学[M].北京:机械工业出版社,2006.

[2]赵云,王希云.基于MATLAB的动态规划常用算法的实现[J].太原师范大学学报(自然科学版),2008,7(4):26-30.

[3]刘卫国.科学计算与MATLAB语言[M].北京:中国铁道出版社,2000.

[4]楼顺天.MATLAB程序与语言[M].西安:西安电子科技大学出版社,1997.

[5]左兼金.水利水电施工组织管理与系统分析[M].北京:水利水电出版社,1993.

动态规划范文第10篇

动态规范是算法里一种非常重要的方法,是求解决策过程最优化的数学方法。动态规划自问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其他方法求解更为方便。

本文通过对经典的01背包问题的求解,从动态规划的角度进行阐述,通过案例对该算法的计算过程进行了直观的描述,并对该算法进行了一定的优化,最后指出该算法的优缺点。

[关键词]背包 动态规划 时间复杂度 空间复杂度

[中图分类号]TP31[文献标识码]A[文章编号]1009-5349(2010)05-0121-03

前言

背包问题是一个经典的动态规划模型,很多关于算法的教材都把它作为一道例题,该问题既简单又容易理解,而且在某种程度上还能够揭示动态规划的本质。

将具有不同重量和价值的物体装入一个有固定载重量的背包,以获取最大价值,这类问题被称为背包问题。

背包问题可以扩展出很多种问题,而01背包问题是最常见、最有代表性的背包问题。

一、问题描述

给定一个载重量为M的背包及n个物体,物体i的重量为wi、价值为pi,1≤i≤n,要求把这些物体装入背包,使背包内的物体价值总量最大。此处我们讨论的物体是不可分割的,通常称这种物体不可分割的背包问题为01背包问题。

二、基本思路

01背包问题的特点是:每种物体只有一件,可以选择放或者不放。假设:xi表示物体i被装入背包的情况,xi=0,1。当xi=0时,表示物体没有被装入背包;当xi=1时,表示物体被装入背包。根据问题的要求,有如下的约束方程(1)和目标函数(2):

三、利用动态规划法求解01背包问题

(一)动态规划算法的基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

(二)算法设计

假定背包的载重量范围为0~m。类似于资源分配那样,令optpi(j)表示在前i个物体中,能够装入载重量为j的背包所得的最大价值,j=1,2,……,m。显然,此时在前i个物体中,有些物体可以装入背包,有些物体不能装入背包。于是,可以得到下面的动态规划函数:

(4)式表明:把前面i个物体装入载重量为0的背包,或者把0个物体装入载重量为j的背包,得到的价值都为0。(5)式表明:当第i个物体的重量大于背包的载重量时,装入前i个物体得到的最大价值,与装入前i-1个物体得到的最大价值一样,即第i个物体没有装入背包。(6)式表明:当第i个物体的重量小于背包的载重量时,如果第i个物体装入背包,背包中物体的价值,等于把前i-1个物体装入载重量为j-wi的背包所得到的价值与第i个物体的价值pi之和;如果第i个物体没有装入背包,则背包中物体的价值,等于把前i-1个物体装入载重量为j的背包,却不装入第i个物体所取得的价值。显然,这两种装入方法,在背包中所取得的价值不一定相同,因此,取这两者中的最大值,作为把前面i个物体装入载重量为j的背包所取得的最优价值。

该算法可分为n阶段:

第一阶段,只装入一个物体,计算在不同载重量的背包情况下,所取得的最大价值;

第二阶段,装入前两个物体,按(5)式和(6)式计算在不同载重量的背包情况下,取得的最大价值;

……

第n阶段,装入前n个物体,按(5)式和(6)式计算在不同载重量的背包情况下,取得的最大价值,而在背包载重量为M时,所得结果就是我们想要的结果。

为了确定具体哪个物体装入背包,从optpn(m)的值向前倒推。有如下递推关系式:

(7)式表明:如果optpi(j)大于optpi-1(j),则物体i被装入背包;如果optpi(j)等于optpi-1(j),表明i物体未被装入背包。按照该关系式,i从n到1依次类推,直到确定第一个物体是否被装入背包为止,就能确定装入背包的具体物体。

(三)存储结构

该算法需要将每一个物体的重量和价值分别存储起来,并针对不同载重量的背包对物体分别计算,故考虑使用数组来实现。对于物体i,用weight[i]来表示重量、用p[i]表示价值,解向量用x[i]表示物体i是否被放入,上面提到的optpi(j)则用二维数组相应的optp[i][j]来表示,物体个数n,背包载重量为m。

(四)算法实现

initial knapsack_dynamic(initial optp[][],weight[],p[],x[],n,m)

{

initial i,j,value;

//根据(4)式初始化第0列及解向量X

//解向量初始值设置为false,表示起初所有物体均未放入背包

for(i = 0; i

{

optp[i][0] = 0;

x[i] = FALSE;

}

//根据(4)式初始化第0行

for(i = 0; i

{

optp[0][i] = 0;

}

//利用(5)(6)式计算optp[i][j]

for(i = 1; i

{

for(j = 1; j

{

optp[i][j] = optp[i-1][j];

if((j >= weight[i]) && (optp[i-1][j - weight[i]]+p[i]) > optp[i-1][j])

optp[i][j] = optp[i-1][j-weight[i]] + p[i];

}

}

//确定装入背包的具体物体

j = m;

for(i = n; i > 0; i--)

{

if(optp[i][j] > optp[i-1][j])

{

x[i] = TRUE;

j = j - weight[i];

}

}

//value就是所要求的值

value = optp[n][m];

return value;

}

1.案例分析

现有载重量为10的背包,有四个物体A、B、C、D,其重量分别为4、2、5、3,价值分别为4、3、5、8,要求放入物体使背包所获价值最大。

用optp[i][j]来存储这四个物体在不同载重量的背包下所获的价值,计算过程如下表所示:

2.时间空间复杂度

该算法中,矩阵optp的大小为(m+1)×(n+1),物体的重量、价值和解向量大小都等于物体个数n,故该算法的空间复杂度为O(nm)。对物体重量、价值的初始化(算法实现略)所需时间都为n,解向量和矩阵第0行初始化时间为n,矩阵第0列初始化时间为m,对矩阵optp的计算所需时间为n×m,解向量X的确定时间为n,故整个算法的时间复杂度为O(nm)。

(五)算法优化

在上述算法中,时间复杂度不能再继续优化了,但是空间复杂度是可以继续优化的。

上述算法中,存储optp使用的是二维数组,其大小为(m+1)×(n+1),但是仔细观察发现,optp[i][j]只与optp[i-1][j]和optp[i-1][j - weight[i]]有关,与optp[k][l](k=1,2,……,i-2,i+1,……n,j=1,2,……,m)无关,故可考虑只用一维数组_optp来存储,_optp[j]相当于optp[i][j]。而考虑到optp[i][j]是由optp[i][j]和optp[i-1][j - weight[i]]共同计算得到的,故该算法中的j循环要从后往前计算,_optp[]的计算算法设计如下所示:

for(i = 1; i

{

for(j = m; j >= 1; j--)

{

if((j >= weight[i]) && (_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

上述例子中,相应的_optp[j]计算结果如下表所示:

}

}

上述例子中,相应的_optp[j]计算结果如下表所示:

显然,对于物体i,_optp[j]的计算不会影响到_optp[0,1,……,weight[i]-1],故上述算法可继续优化为:

for(i = 1; i

{

for(j = m; j >= weitht[i]; j--)

{

if((_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

对于01背包问题,常见的要求有两种:一种是恰好装满背包、另一种则没有要求,针对这两种问法,可从初始化上来区分。

当要求恰好装满背包时,初始化时将_optp[0]设为0,其他_optp[1,2,……,m]全部设为-∞,这样就可保证最终得到的_optp[n]是一种恰好装满的最优解,此时可以把初始化理解成没有任何物体可放时,只有容量为0的背包能被价值为0的nothing“恰好装满”;当没有这个限制时,初始化时应将_optp[0,1,……,m]都设为0,此时可以理解为任何一个背包都有一个合法的解“什么都不装”,这个解的价值为0。

当优化后,空间复杂度变为O(m),计算所需时间为:

当weitht[i]较大时,可以节省很多时间。

动态规划的缺点:对于01背包问题,用动态规划方法解很容易理解,但是这种方法有一些弊端,从上述算法可以看出:当物体的重量较大时,所需的物理空间较大;当物体的重量不是整数时,无法利用数组来存储该结构。

四、结束语

在日常生活中,01背包问题有很多应用,比如如何利用有限空间的手提包,装入外出旅行的各种必需品。

01背包问题还有很多种解法,每种解法也有各种不同的实现,比如回溯法可以利用结构或类来表示状态空间树,每一本关于算法的书籍都把它当成必讲的题目,而由01背包问题引申出来的各种题目也层出不穷,例如完全背包问题就要求每种物体都无限制使用。01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,但是无论哪种类型的背包问题,都可以转换为01背包问题。所以读者们要仔细体会01背包问题基本思路的得出方法,状态转移方程的意义,以及关于时间空间复杂度的优化等问题。

上一篇:大学规划范文 下一篇:人生规划范文