动态规划求解方法的Matlab实现及应用[1]

1、动态规划求解方法的Matlab实现及应用1.txt我自横刀向天笑，笑完我就去睡觉。 你的手机比话费还便宜。路漫漫其修远兮，不如我们打的吧。第 %卷第 ,期信息工程大学学报 S:+% +,!年 )月 T8D3F: C 53CDEFB23 G3?23D23? 032HDA2BI 6N+! ! !动态规划求解方法的 !#$%实现及应用于斌，刘姝丽，韩中庚（信息工程大学信息工程学院，河南郑州 #!）摘要：文章对动态规划问题的求解方法进行了分析研究，根据问题的特点、难点和关键点做了针对性的处理，然后用 !#$%做了实现尝试，从而实现了“最佳组队”和“最短路线”等问题的求解。实践证明所采用方法和程序都是有

2、效的。关键词：动态规划；基本方程；!#$%实现；最佳组队中图分类号：* !&+,文献标识码：-文章编号：&%.& $ %.,（!）, $ ) $ # !#$% &$()#(*+ *, #- ./+0(1 23*4300(+4 5663*1-+7 8#9 566$(1#(*+ /0 123，450 6789:2，;-3?9?3?（53AB2B8B C 53CDEFB23 G3?23D23?，53CDEFB23 G3?23D23? 032HDA2BI，=73?J78 #!，K723F） 5%9#31#：1I F3F:IJ23? F3L 23HAB2?FB23? B7 LI3FE2M ND?DFEE

3、23? FNNDFM7，F3 CCMB2H L2ANAF: 7FA O3 L3 FMMDL23? B B7 NDO:E+ P73 F3 FBBENB 3 B7 NDO:EA C“1AB BFE9CDE23?”F3L “67DBAB NFB7”7FA O3 A8MMAAC8:I EFL OI QFB:FO+ 5B 2A NDHL B7FB B7 EB7L F3L ND?DFEE FD CCMB2H+ :/ ;*379：LI3FE2M ND?DFEE23?；OFA2M R8FB23；QFB:FO；OAB BFE9CDE23? NDO:E 小规模的动态规划问题成为可能，从而使得动态规引言划的理论和方

4、法在实际中的应用范围迅速增加。目前，在计算机上实现动态规划的一般求解方动态规划是一类解决多阶段决策问题的数学法并不多见，尤其是用来解决较复杂的具体问题的方法，在工程技术、科学管理、工农业生产及军事等成果甚少。本文从实际出发，利用数学工具软件 领域都有广泛的应用。在理论上，动态规划是求解QFB:FO的强大功能，对动态规划模型的求解方法做&!这类问题全局最优解的一种有效方法，特别是对于了尝试，并结合“最佳组队问题”和最短路问题实际中的某些非线性规划问题可能是最优解的唯进行了应用检验，实际证明结果是令人满意的。 一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法，或者说是考查问题的一种途径，而

5、&动态规划的基本模型不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法，在实际实际中，要构造一个标准的动态规划模型，通应用中，需要具体问题具体分析。动态规划模型的常需要采用以下几个步骤： 求解问题是影响动态规划理论和方法应用的关键!划分阶段按照问题的时间或空间特征，把所在，而子问题的求解和大量结果的存储、调用更问题分为若干个阶段。这些阶段必须是有序的或是一个难点所在。然而，随着计算机技术的快速发者是可排序的（即无后向性），否则，应用无效。 展，特别是内存容量和计算速度的增加，使求解较选择状态将问题发展到各个阶段时所处收稿日期：!# $ % $ &%修回日期：! $

6、 $ (作者简介：于斌（&)(! $），男，江苏姜堰人，信息工程大学硕士研究生，主要研究方向为通信工程。=信息工程大学学报 (). 年的各种客观情况用不同的状态表示，即称为状态。状态的选择要满足无后效性和可知性，即状态不仅依赖于状态的转移规律，还依赖于允许决策集合和指标函数结构。 !确定决策变量与状态转移方程当过程处于某一阶段的某个状态时，可以做出不同的决策，描述决策的变量称为决策变量。在决策过程中，由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式，逆序形式和顺序形式。

7、动态规划基本方程的逆序形式为 !）! $! %（ #）&$（ # %& ! ， .， &（ #$ （ #，）% ! %&）， &，(，边界条件：! %&（ # %&）!)或 !（#）! &（#，$）（&）其中第 阶段的状态为 #，其决策变量 $表示状态处于 # %&的决策，（ #，状态转移方程为 # %& ! ($）阶段的允许决策集合记为 %）&$，（ #，（ #，）为指标函数。当求解时，由边界条件从 ! 开始，由后向前逆推，逐阶段求出最优决策和过程的最优值，直到最后求出 !（&#&）即得到问题的最优解。类似的，动态规划基本方程的顺序形式为 !（#%&）!#$!%)（#%&）&（#%&，$）%

8、!&（#），!&，(，.，&，）（ #&边界条件：!)!)（(）其中状态转移方程为 # ! ()$）阶段的（ # %&， 允许决策集合为 %（)# %&）指标函数为 &，（ # %&， $）。当求解时，由边界条件从 !&开始，由前向后顺推，逐阶段求出最优决策和过程的最优值，直到最后求出 !（# %&）即得到问题的最优解。 (基本方程求解的 *+$,+-实现动态规划没有统一的标准模型，对于基本方程（&）和（(）的求解也没有统一的标准算法。但是，我们分析用动态规划解决问题的思想方法，会发现一个共同的明显特征，这就是将所研究的问题分为关联着的多个阶段后，每个阶段都有若干个对应的子问题，求解问题的关键

9、就是按阶段次序求解大量子问题的最优解。而且对于每一个子问题的求解结果都必须完整贮存下来，上一阶段子问题的结果将对下一阶段产生一定的影响，即对全局最优决策也产生影响。如何处理好所有各阶段的大量子问题的求解及结果的贮存和调用等，这是编程求解动态规划问题的难点所在，也是必须要解决的问题。 (* & *+$,+-实现方法综述在这里仅就动态规划基本方程的逆序形式进行讨论，顺序形式也类似。对于各个阶段的子问题的求解方法基本都是相同的，在当前阶段的所有子问题求得最优决策以后，通过状态转移方程可以确定出下一阶段的状态和允许状态集合，从而可以在决策集合上来寻求这个新阶段的最优决策。从第 个阶段出发，直到第一个阶

10、段为止，即可得到全过程的最优决策。因此，在具体实现的过程中，针对每一个状态编写一个相对通用的函数，然后在主程序中循环调用该函数，以实现任意状态下的最优决策。问题的主体程序框图如图 &所示。图 &主程序框图 (* (具体程序实现按照如上的程序框图，编写相关程序，主要由 .个子程序构成： #主函数 /012$31#+3，453! +,-（6，7）输入状态向量 6和相关指标矩阵 7，返回最优策略和相应指标值；用全局变量 8，88，888，分别记录指标值、状态地址和相应决策。 $状态计算子函数 !./0-1 /（1，66，9+,）计算相应状态下的最优决策，并存储；1为目前阶段数，66为前一阶段某个状态

11、的最优决策，9+,为相应指标值。 !辅助计算子函数 !./0-16:;，! 2)32（6， $，1，6:;）确定变量 88；在某个阶段，对该阶段所 第 +期于斌等：动态规划求解方法的 9/#:/;实现及应用%有状态进行预排列，并在 !中记录状态的相对位置；表示本次是第几次调用，#$#表示排列的数目；在主函数中调用。 !查找子函数 !#$%&#%& ()*$（）根据辅助计算子函数在 !中记录的位置，在某个阶段中查找相应状态的地址；为待查寻的状态；在子函数 (中调用。 指标计算子函数 !#$%&#)& *（参数）计算所确定决策的指标值。 ( + +计算结果的存储方法在实际计算过程中，对于中间的阶段

12、性结果必须要进行存储，也是为后续计算的基础，这是求解动态规划问题的主要特征体现，而与存储相关的问题也是动态规划编程实现的难点之一。在具体操作中，将每个阶段的最优值的计算结果都要保存下来，在计算结束后就可以得到一族最优决策，通过比较各策略的优劣，从而可以得到问题的全局最优决策。同时，因为存储量很大，在计算过程中要注意内存变量的替换，以节省内存空间。具体做法可有两种：一是将所有决策结果综合比较后得到最优解，然后直接一次性存储；二是对每一次的计算结果都与上次存储的结果进行比较，再择优存储。由于在许多实际问题中，各阶段的状态往往是通过状态转移关系确定的，是不可预知的，所以，该状态下的所有决策也就不能提

13、前预知。因此，只能采用第二种方法实现。方法如下： #将需要存储的数据置为全局变量，每个阶段对应一个数组，每个状态对应该数组中的一个元素，并赋初值为零； $当得到某个允许决策时，确定其对应的状态，寻找相应的存储空间； %计算该决策的指标函数值，并与原来的存储结果比较，然后择优存储。值得说明的是，在一些复杂的问题中，在允许状态集合中寻求相应的状态和对应的决策是一个难点。如果对于某个阶段的允许状态集合的元素（即状态）很多，如何快速找到相应的状态及存储空间？一般不能采用循环搜索的方法，因为它的耗时是不可忍受的。这在实际计算中是非常重要的，应该具体问题采取具体的方法。另外，计算结果的存储必须包括指标值的

14、存储和决策变量的存储，因此，还需要定义一个用于存储最优决策全局变量，而且两个全局变量的读、写也必须是同步的。 +求解方法的实践与应用 + ,最佳组队问题,在文献,“确定最佳组队问中的第 +个问题：题，即要求给出 ,-名队员组成 .个队的组队方案，使整体竞赛水平最高，并给出每个队的竞赛水平”。文献,建立了最佳组队的动态规划模型，其模型的基本方程以逆序形式给出，即 （）& %/!0（ ，）0 !（ ），, &2，3，+，(，!,-,-,1, 0,-, 1, ,(.) ! /,!（）& 0. （ 2， -）队的技术水平指标）.-.&4+ 42.+(3.（3， 其中决策变量为 1, &（ .，4，5）

15、 ,，即任取 +名队员（ .，4，5）所组成的一个组队方案；状态变量为 -，即从第 ,个到第 2个组队的组队方案所包含的队(,) 员，-,&6，7，8，.，9；状态转移方程为 -, 0, & -, 1 1,；允许决策集合为 /, &（ .，4，5）；.，4，5! ，（ .， 5） :(， 3，；-,0,4， #（ , &,， +， 2）指标函数为 0（ -，1）表示决策 1（一个组队）关于状态 -的,技术水平指标；最优值函数 !（ -）表示在状态 ,下确定的 ,个组队的技术水平指标之和（,$ ,$2）的最大值。该问题是一个较为复杂的动态规划模型，其状态数目较多，每个阶段的决策由 +个变量构成，

16、而且各阶段的状态不可预知。决策过程分为 2个阶段，即分步给出 2个队的组队方案，在除了一个最,佳组队的 +名队员（ 2，3，-）外的 ,2名队员中组成 2个队，每一阶段确定一个队。第一阶段有 5+ ,2个状态，5+ 个子决策；第二阶段有 5. 个状态，5. 个,2,2,2子决策；第 +阶段有 56 个状态，56 个子决策；第 3,2,2阶段有 5,(个状态，5,(个子决策；第 2阶段有 ,个状,2,2态，,个决策（即最优策略）。参考 (7 (，编写相关程序，运行可以得最佳的决策方案，即最佳的组队方案为，（ ;，2，）（ 7， ?）（ ， B）（ 6， D），其整体竞，8，A，C， 赛水平指标为

17、 47+(3,。由此结果可以看出，求解结果（即组队方案）优于文献,中的结果，从而也说明了文献,的解是局部最优解，并非全局最优解。 +7(最短路线问题(对于最短路线问题(也是一类非常有代表性的问题，即对于给定的网络，从 6点到 3点寻求一条最短的路线。其问题可以归结为 .个阶段的动态规划决策问题，即基本方程的逆序形式为： .信息工程大学学报 +-(年$!（#）!#$!%（#）&（#，$（#）%!%&（#%&），!，(，)，*，+，&!（#）!-，或!（#）!&（#，）,编写程序，求解可以得到最短路线为 ( )& * + %& + ,+ ，其最短距离为 &.。此结果与直接计算的最优结果完全一致，充

18、分说明该求解方法的有效性。 )结果的分析与说明根据前面的分析和实际应用结果，可以充分地证明，我们采用的求解动态规划问题的方法和 /012 304实现程序是有效可行的，由此可以求得问题的全局最优解。特别是在变量的使用和存贮处理上，所采用的方法使得利用现有计算机资源求解一般性的动态规划问题成为可能。但值得注意的是：在很多情况下，在确定某阶段状态时，首先要获取前一阶段的决策，因此，需将每个阶段的最优子决策和指标值记录并保存。当每个阶段都有多个状态时，则须计算该状态下的所有可能决策。为了快速寻找并调用相应计算结果，有必要对各阶段的所有状态进行唯一、简单的标识，并记录其存储地址。根据目前的计算机技术水平

19、，这种方法也不是对任何动态规划问题都能解决，当问题的阶段数和各阶段的状态数很大时，从理论上是可行的，但实际是无法做到的。这里我们可以做一个初步的估算，譬如：就最佳组队问题，其时间和空间复杂度都是 -（ ./），按照 &(个人的情况来计算，每个状态至少需要 .-56178才能完成其指标值和最优策略的存储，那么，不难得到解决不同规模的问题需消耗的资源见表 &。表 &不同分组人数需消耗资源分组人数 &( &. +& +) +,状态数 &-9 &-9 ,-9 (:)/ (-/所需内存 .-95 ./5 (/5 )*+/5 );5计算时间 &-#$ &-#$ ,-#$ &- &-,，+,（+）：&* ? &)-:+编写组 :运筹学（修订版）/:北京：清华大学出版社， &):*张志涌 :精通 /AB5 :(版/:北京：北京航空航天大学出版社，+-*:# （上接第 )页）表 &论文指标得分 C& C+ C* C) C( C D& .: -. :+ : :* .: ):( D+ ,: + :-,:) (:. : + (:( D*& ,E ,: :( :& .: ( (:+ D*+ .: ) . :