第 6 卷 　第 3 期 　　 　　　 　　　　信 息 工 程 大 学 学 报 　　　　 　　 　　 　　Vol. 6 No. 3 　2005 年 9 月 　 　 　　 　Journal of Information Engineering University 　　　 　　　 　　Sep . 2005 动态规划求解方法的 Matlab 实现及应用 于 　斌 , 刘姝丽 , 韩中庚 (信息工程大学 信息工程学院 ,河南 郑州 450002) 摘要 :文章对动态规划问题的求解方法进行了分析研究 ,根据问题的特点 、难点和关键点做了 针对性的处理 ,然后用 Matlab 做了实现尝试 ,从而实现了“最佳组队”和“最短路线”等问题的 求解 。实践证明所采用方法和程序都是有效的 。 关键词 :动态规划 ;基本方程 ; Matlab 实现 ;最佳组队 中图分类号 :O 221. 3 　　　文献标识码 :A 　　　文章编号 :1671 - 0673 (2005) 03 - 0095 - 04 Matlab Realization of the Dynamic Programming Approach and Its Application YU Bin , LIU Shu li , HAN Zhong geng ( Institute of Information Engineering , Information Engineering University , Zhengzhou 450002 , China) Abstract :By analyzing and investigating the dynamic programming approach , an effective disposal has been done according to the problem. Then an attempt on the problems of“Best team forming”and“Shortest path”has been successfully made by Matlab. It is proved that the method and programme are effective. Key words :dynamic programming ; basic equation ; Matlab ; best team forming problem 0 　引言 动态规划是一类解决多阶段决策问题的数学 方法 ,在工程技术 、科学管理 、工农业生产及军事等 领域都有广泛的应用 。在理论上 ,动态规划是求解 这类问题全局最优解的一种有效方法 ,特别是对于 实际中的某些非线性规划问题可能是最优解的唯 一方法 。然而 ,动态规划仅仅是解决多阶段决策问 题的一种方法 ,或者说是考查问题的一种途径 ,而 不是一种具体的算法 。就目前而言 ,动态规划没有 统一的标准模型 ,其解法也没有标准算法 ,在实际 应用中 ,需要具体问题具体分析 。动态规划模型的 求解问题是影响动态规划理论和方法应用的关键 所在 ,而子问题的求解和大量结果的存储 、调用更 是一个难点所在 。然而 ,随着计算机技术的快速发 展 ,特别是内存容量和计算速度的增加 ,使求解较 小规模的动态规划问题成为可能 ,从而使得动态规 划的理论和方法在实际中的应用范围迅速增加 。 目前 ,在计算机上实现动态规划的一般求解方 法并不多见 ,尤其是用来解决较复杂的具体问题的 成果甚少 。本文从实际出发 ,利用数学工具软件 Matlab 的强大功能 ,对动态规划模型的求解方法做 了尝试 ,并结合“最佳组队问题”[1 ]和最短路问题[2 ] 进行了应用检验 ,实际证明结果是令人满意的 。 1 　动态规划的基本模型 实际中 ,要构造一个标准的动态规划模型 ,通 常需要采用以下几个步骤 : ①划分阶段 　按照问题的时间或空间特征 ,把 问题分为若干个阶段 。这些阶段必须是有序的或 者是可排序的 (即无后向性) ,否则 ,应用无效 。 ②选择状态 　将问题发展到各个阶段时所处 的各种客观情况用不同的状态表示 ,即称为状态 。 状态的选择要满足无后效性和可知性 ,即状态不仅 　　收稿日期 :2004 - 06 - 16 　修回日期 :2005 - 05 - 08 　　作者简介 :于 　斌 (1982 - ) ,男 ,江苏姜堰人 ,信息工程大学硕士研究生 ,主要研究方向为通信工程。 

69　　　　　　　　　　　　　　　　　　　　　信 息 工 程 大 学 学 报 　　　　　　　　　　　　　　　 2005 年 2. 1 　Matlab 实现方法综述 在这里仅就动态规划基本方程的逆序形式进 行讨论 ,顺序形式也类似 。对于各个阶段的子问题 的求解方法基本都是相同的 ,在当前阶段的所有子 问题求得最优决策以后 ,通过状态转移方程可以确 定出下一阶段的状态和允许状态集合 ,从而可以在 决策集合上来寻求这个新阶段的最优决策 。从第 n 个阶段出发 , 直到第一个阶段为止 , 即可得到全 过程的最优决策 。因此 , 在具体实现的过程中 , 针 对每一个状态编写一个相对通用的函数 ,然后在主 程序中循环调用该函数 ,以实现任意状态下的最优 决策 。问题的主体程序框图如图 1 所示 。 依赖于状态的转移规律 ,还依赖于允许决策集合和 指标函数结构 。 ③确定决策变量与状态转移方程 　当过程处 于某一阶段的某个状态时 ,可以做出不同的决策 , 描述决策的变量称为决策变量 。在决策过程中 ,由 一个状态到另一个状态的演变过程称为状态转移 。 状态转移就是根据上一阶段的状态和决策来导出 本阶段的状态 。 ④写出动态规划的基本方程 　动态规划的基 本方程一般根据实际问题可分为两种形式 ,逆序形 式和顺序形式 。动态规划基本方程的逆序形式为 { vk ( s k , x k) + f k + 1 ( s k + 1) } , k = n , n - 1 , …,2 ,1 f k ( s k) = opt ∈D k x k ) ( s k 边界条件 :f n + 1 ( s n + 1) = 0 或 f n ( s n) = vn ( s n , x n) (1) 其中第 k 阶段的状态为 sk , 其决策变量 xk 表示状 态处于 sk + 1的决策 ,状态转移方程为 sk + 1 = Tk ( sk , xk) , k 阶段的允许决策集合记为 Dk ( sk) , vk ( sk , xk) 为指标函数 。 当求解时 ,由边界条件从 k = n 开始 , 由后向 前逆推 ,逐阶段求出最优决策和过程的最优值 , 直 到最后求出 f 1 ( s1) 即得到问题的最优解 。 类似的 ,动态规划基本方程的顺序形式为 f k ( s k + 1) = opt r ∈D ( s k x k k + 1 边界条件 :f 0 ( s1) = 0 { vk ( s k + 1 , x k) + f k - 1 ( s k) } , k = 1 ,2 , …, n - 1 , n ) (2) 其中状态转移方程为 sk = Tr k ( sk + 1 , xk) , k 阶段的 k ( sk + 1) , 指标函数为 vk ( sk + 1 , 允许决策集合为 Dr xk) 。当求解时 ,由边界条件从 k = 1 开始 , 由前向 后顺推 ,逐阶段求出最优决策和过程的最优值 , 直 到最后求出 f n ( sn + 1) 即得到问题的最优解 。 2 　基本方程求解的 Matlab 实现 动态规划没有统一的标准模型 ,对于基本方程 (1) 和 (2) 的求解也没有统一的标准算法 。但是 ,我 们分析用动态规划解决问题的思想方法 ,会发现一 个共同的明显特征 ,这就是将所研究的问题分为关 联着的多个阶段后 ,每个阶段都有若干个对应的子 问题 ,求解问题的关键就是按阶段次序求解大量子 问题的最优解 。而且对于每一个子问题的求解结 果都必须完整贮存下来 ,上一阶段子问题的结果将 对下一阶段产生一定的影响 ,即对全局最优决策也 产生影响 。如何处理好所有各阶段的大量子问题 的求解及结果的贮存和调用等 ,这是编程求解动态 规划问题的难点所在 ,也是必须要解决的问题 。 图 1 　主程序框图 2. 2 　具体程序实现 按照如上的程序框图 ,编写相关程序 ,主要由 5 个子程序构成 : ①主函数 function [pai , zhi ] = main ( s , W) 　 输入状态向量 s 和相关指标矩阵 W ,返回最优策略 和相应指标值 ;用全局变量 x , xx , xxx ,分别记录指 标值 、状态地址和相应决策 。 ②状态计算子函数 f unction ff (n , ss , val) 　计 算相应状态下的最优决策 ,并存储 ; n 为目前阶段 数 ,ss 为前一阶段某个状态的最优决策 ,val 为相应 指标值 。 ③辅助计算子函数 f unction [ ser , d ] = prep ( s , tot , n ,ser) 　确定变量 xx ;在某个阶段 ,对该阶段所 有状态进行预排列 ,并在 xx 中记录状态的相对位 置 ;n 表示本次是第几次调用 ,tot 表示排列的数目 ; 在主函数中调用 。 

第 3 期 　　　　　　　　　　　　于 　斌等 :动态规划求解方法的 Matlab 实现及应用 　　　　　　　　　　　　　　 79 ④查找子函数 f unction [ m ] = serc ( ss) 　根据 辅助计算子函数在 xx 中记录的位置 ,在某个阶段 中查找相应状态的地址 ; ss 为待查寻的状态 ; 在子 函数 2 中调用 。 ⑤指标计算子函数 f unction [f ] = vv (参数) 　 计算所确定决策的指标值。 2. 3 　计算结果的存储方法 在实际计算过程中 ,对于中间的阶段性结果必 须要进行存储 , 也是为后续计算的基础 , 这是求解 动态规划问题的主要特征体现 ,而与存储相关的问 题也是动态规划编程实现的难点之一 。在具体操 作中 ,将每个阶段的最优值的计算结果都要保存下 来 ,在计算结束后就可以得到一族最优决策 , 通过 比较各策略的优劣 ,从而可以得到问题的全局最优 决策 。同时 , 因为存储量很大 , 在计算过程中要注 意内存变量的替换 ,以节省内存空间 。具体做法可 有两种 :一是将所有决策结果综合比较后得到最优 解 ,然后直接一次性存储 ; 二是对每一次的计算结 果都与上次存储的结果进行比较 ,再择优存储 。由 于在许多实际问题中 ,各阶段的状态往往是通过状 态转移关系确定的 ,是不可预知的 ,所以 ,该状态下 的所有决策也就不能提前预知 。因此 ,只能采用第 二种方法实现 。方法如下 : ①将需要存储的数据置为全局变量 ,每个阶段 对应一个数组 , 每个状态对应该数组中的一个元 素 ,并赋初值为零 ; ②当得到某个允许决策时 , 确定其对应的状 态 ,寻找相应的存储空间 ; ③计算该决策的指标函数值 ,并与原来的存储 结果比较 ,然后择优存储 。 值得说明的是 , 在一些复杂的问题中 , 在允许 状态集合中寻求相应的状态和对应的决策是一个 难点 。如果对于某个阶段的允许状态集合的元素 (即状态) 很多 ,如何快速找到相应的状态及存储空 间 ? 一般不能采用循环搜索的方法 ,因为它的耗时 是不可忍受的 。这在实际计算中是非常重要的 ,应 该具体问题采取具体的方法 。另外 ,计算结果的存 储必须包括指标值的存储和决策变量的存储 , 因 此 ,还需要定义一个用于存储最优决策全局变量 , 而且两个全局变量的读 、写也必须是同步的 。 3 　求解方法的实践与应用 3. 1 　最佳组队问题[1 ] 在文献[1 ]中的第 3 个问题 :“确定最佳组队问 题 ,即要求给出 18 名队员组成 6 个队的组队方案 , 使整体竞赛水平最高 ,并给出每个队的竞赛水平”。 文献[1 ]建立了最佳组队的动态规划模型 , 其 模型的基本方程以逆序形式给出 ,即 f k ( Sk) = max ∈D k x k { vk ( Sk , Xk) + f k + 1 ( Sk - 1) } , k = 5 ,4 ,3 ,2 ,1 f 6 ( S6) = v6 = 0. 0563246 　( ( L , G , S) 队的技术水平指标) 其中决策变量为 Xk = ( x , y , z) k , 即任取 3 名队员 ( x , y , z) 所组成的一个组队方案 ; 状态变量为 S k , 即从第 k 个到第 5 个组队的组队方案所包含的队 员 , S 1 = { A , B , C , …, T} ;状态转移方程为 S k + 1 = S k - Xk ;允许决策集合为 Dk = { ( x , y , z) ; x , y , z ∈ S k , vk ( x , y , z) ≥ W} ( k = 1 , 2 , 3 , 4 , 5) ; 指标函数为 vk ( S k , Xk) 表示决策 Xk (一个组队) 关于状态 S k 的 技术水平指标 ; 最优值函数 f k ( S k) 表示在状态 S k 下确定的 k (1 ≤k ≤5) 个组队的技术水平指标之和 的最大值 。 该问题是一个较为复杂的动态规划模型 ,其状 态数目较多 ,每个阶段的决策由 3 个变量构成 ,而 且各阶段的状态不可预知 。决策过程分为 5 个阶 段 ,即分步给出 5 个队的组队方案 ,在除了一个最 佳组队的 3 名队员 ( L , G , S) [1 ]外的 15 名队员中组 成 5 个队 ,每一阶段确定一个队 。第一阶段有 C3 15 个状态 ,C3 15个 子决策 ;第 3 阶段有 C9 15个子决策 ;第 4 阶段有 C12 15个状态 ,C12 15个子决策 ;第 5 阶段有 1 个状 态 ,1 个决策 (即最优策略) 。 15个子决策 ;第二阶段有 C6 15个状态 ,C9 15个状态 ,C6 参考 2. 2 ,编写相关程序 ,运行可以得最佳的 决策方案 ,即最佳的组队方案为 , ( K , L , Q) , ( D , M , R) , ( B , C , O) , ( F , J , P) , ( A , E , N) ,其整体竞 赛水平指标为 0. 3241 。 由此结果可以看出 ,求解结果 (即组队方案) 优 于文献[1 ]中的结果 ,从而也说明了文献[1 ]的解是 局部最优解 ,并非全局最优解 。 3. 2 　最短路线问题[2 ] 对于最短路线问题[2 ]也是一类非常有代表性 的问题 ,即对于给定的网络 ,从 A 点到 G 点寻求一 条最短的路线 。其问题可以归结为 6 个阶段的动 态规划决策问题 ,即基本方程的逆序形式为 : f k ( s k) = min ∈D ( s k k x k ) { dk ( s k , x k ( s k) ) + f k + 1 ( s k + 1) } , k = 6 ,5 ,4 ,3 ,2 ,1 f 7 ( s7) = 0 ,或 f 6 ( s6) = d6 ( s6 , G) 编写程序 ,求解可以得到最短路线为 A →B 1 →C2 →D1 →E2 →F2 →G , 其最短距离为 18 。此结果与 直接计算的最优结果完全一致 ,充分说明该求解方 法的有效性 。 4 　结果的分析与说明 根据前面的分析和实际应用结果 ,可以充分地 

89　　　　　　　　　　　　　　　　　　　　　信 息 工 程 大 学 学 报 　　　　　　　　　　　　　　　 2005 年 证明 ,我们采用的求解动态规划问题的方法和 Mat lab 实现程序是有效可行的 ,由此可以求得问题的 全局最优解 。特别是在变量的使用和存贮处理上 , 所采用的方法使得利用现有计算机资源求解一般 性的动态规划问题成为可能 。但值得注意的是 :在 很多情况下 ,在确定某阶段状态时 ,首先要获取前 一阶段的决策 ,因此 ,需将每个阶段的最优子决策 和指标值记录并保存 。当每个阶段都有多个状态 时 ,则须计算该状态下的所有可能决策 。为了快速 寻找并调用相应计算结果 ,有必要对各阶段的所有 状态进行唯一 、简单的标识 ,并记录其存储地址 。 根据目前的计算机技术水平 ,这种方法也不是 对任何动态规划问题都能解决 ,当问题的阶段数和 各阶段的状态数很大时 ,从理论上是可行的 ,但实 际是无法做到的 。这里我们可以做一个初步的估 算 ,譬如 :就最佳组队问题 ,其时间和空间复杂度都 是 O ( en) ,按照 15 个人的情况来计算 ,每个状态至 少需要 80Bytes 才能完成其指标值和最优策略的存 (上接第 94 页) 表 1 　论文指标得分 P1 8. 0 7. 2 7 9 8. 4 8. 6 8. 5 6. 8 7. 3 7. 8 8. 2 8. 0 P2 8. 2 9. 0 7. 9 8. 2 8. 0 8. 6 7. 5 7. 5 7. 2 7. 8 8. 2 P3 6. 9 7. 4 6. 5 6. 9 7. 3 7. 5 5. 7 6. 2 5. 9 6. 0 6. 1 P4 6. 3 5. 8 6. 1 5. 7 5. 9 5. 5 5. 8 5. 0 6. 0 7. 5 6. 0 P5 8. 9 9. 2 8. 5 8. 6 8. 3 8. 8 9. 2 9. 0 7. 9 8. 0 8. 5 P6 4. 5 5. 5 5. 2 4. 7 4. 5 4. 9 5. 3 5. 0 5. 5 6. 0 6. 5 u1 u2 u31 u32 u33 u34 u4 u5 u61 u62 u63 5 　结果分析 从 6 篇论文对评语集的隶属度向量可以看出 : 论文 IV、论文 V、论文 VI 以较大的隶属度属于其相 应的评语 ,而其它 3 篇论文的隶属度相对分散 。造 储 ,那么 ,不难得到解决不同规模的问题需消耗的 资源见表 1 。 表 1 　不同分组人数需消耗资源 分组人数 15 状态数 10k 所需内存 800kB 计算时间 10min 18 100k 8MB 100min 21 700k 56MB 700min 24 5. 4M 432MB 100h 27 50M 4GB 1000h 　　可见 ,人数多于 24 (包括 24) 时问题的求解几 乎是不可能的了 。 参考文献 : [1 ] 韩中庚. 最佳组队方案及模型[J ]. 数学的实践与认识 , 1997 , 27 (2) :133 - 140. [2 ] 编写组. 运筹学 (修订版) [M]. 北京 :清华大学出版社 , 1994. [3 ] 张志涌. 精通 MATLAB 6. 5 版[M]. 北京 :北京航空航天 大学出版社 ,2003. 　 成隶属度分散的原因有两个 : ①论文某些指标的水 平介于两个档次之间 ,使得指标具有相邻两评语的 程度相差不大 。 ②论文各指标间水平不均衡 ,属于 相邻档次的指标个数相差不大 。 模糊评价的最后结果将论文分为了几个档次 , 如果要对同档次间的论文比较优劣 ,还需进一步分 析讨论 。 参考文献 : [1 ] 　李兴昌. 科技论文写作讲 义 [ EB/ OL ]. http :/ / test. biox. cn/ UpLoadFiles/ Nffy/ Files/ 一般资料/ 科技论文写 作讲义. doc ,2005 - 6 - 13. [2 ] 　秦寿康. 综合评价原理与应用[M]. 北京 :电子工业出 版社 ,2003. 6. [3 ] 　熊小芸. 优秀科技论文的五要素 [ EB/ OL ]. http :/ / hoo - klee. com/ Research/ 5Factors. txt ,2005 - 6 - 13. [4 ] 　郭亚军. 综合评价理论与方法 [ M]. 北京 :科学出版 社 ,2002 ,8.