关于动态规划应用的研究

王沙沙

【摘要】自动态规划开始研究之后，在城市规划、金融管理、生产车间调度和最优化等方面有很广阔的应用前景。例如最短路径、资源分配、生产库存等问题，用动态规划的方法解决更加方便。

【关键词】动态规划 最优化 服装搭配

动态规划隶属于运筹学的研究范围，是用于求解决策过程最优化的数学方法。20世纪50年代初美国数学家贝尔曼等人在研究多阶段决策优化问题的过程中提出了著名的最优化原理，把多阶段的过程问题转化为一系列的单阶段问题，逐个求解，创立了解决此类过程优化问题的新方法—动态规划。

一、动态规划的基本概念

最优化原理：作为整个过程的最优策略，它满足：相对于前面的决策所形成的状态，余下的子策略必然构成“最优子策略”。

状态转移：动态规划中本阶段状态往往是上一阶段状态和上一阶段决策的结果，由第k段的状态sk和本阶段决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示

■

称为状态转移方程。状态转移是决策目的，决策是状态转移的路径，各阶段决策确定以后，整个问题的决策序列就构成了一个策略。

规划方程的一般求法是从一个目标状态出发的递推公式：

■

■某个初始值，称为边界条件。

二、搭配衣服问题

通过对动态规划的学习以及对动态规划应用的研究与分析，我发现现实生活中的“搭配衣服问题”也可以用动态规划方法实现。例如：

假设你刚开了一家服装店，你想雇来一些模特，通过她们最完美的服装展示吸引顾客。现在有模特数量m，同时也有至少同样数量的衣服被按顺序摆成一行。这些衣服固定于衣架上，衣架不可移动，并从1至n序编号，从左至右排列，则最左边的是衣服1，最右边的是衣服n，并且可以移动，每位模特用1至m的整数唯一标识。标识模特的整数决定了模特所穿的衣服的顺序，如果i

例如，假设一共雇来5位模特，第一位模特标识数为1，第二位模特的标识数为2，第三位模特标识数为3，第四位模特标识数为4，第五位模特标识数为5，所有的模特穿上衣服时必须保持其標识数的顺序，即模特的顺序不变。如果衣服的数量大于模特的数量。则多余的衣服必须空置，且一位模特只能穿一件衣服。

由于每一位模特的身高、体型各不同。所以，当不同的模特穿不同的衣服，会产生不同的视觉效果，并以美学值（一个整数）来表示，定义空置衣服的美学值为零。在上述例子中，衣服与模特的不同搭配所具有的美学值，如表3.1所示。

表3.1 衣服与模特的不同搭配所具有的美学值

■

从表中不难看出模特1搭配衣服6会很好看，然而搭配衣服7就会逊色很多；模特2搭配搭配衣服7很好看，然而搭配衣服4会逊色很多；模特3搭配衣服2会很好看，然而搭配衣服1就会逊色很多；模特4配搭配衣服6会很好看，然而搭配衣服5就会逊色很多；模特5配衣服4会很好看，然而搭配衣服1就会逊色很多。

用动态规划的方法解决这个问题的步骤：

第一，以模特的人数来划分阶段。在这里，阶段变量k表示的就是要布置的模特人数（前k位模特），状态变量sk表示第k位模特所穿的衣服。而对于每一个状态sk，决策就是第k-l位模特应该穿哪件衣服，用uk表示。最优指标函数fk（sk）表示前k位模特，其中第k位模特穿第sk件衣服，所能取得的最大美学值。

第二，状态转移方程：■。

第三，规划方程：■■。

第四，边界条件：■■（V是衣服总数）。

解：以模特人数来划分阶段，不难看出可划分为5个阶段。

方法1 逆向递推法

由于此时模特2穿的是7号衣服，要保证模特的顺序保持不变是实现不了的，故考虑要想使得模特的顺序不变，模特1 的选择只有衣服1、2、3，模特5的最优选择是衣服7，此时从后向前考虑，可得模特4选择衣服6，此时模特3的最优选择时衣服3，故模特2选择衣服2，模特1选择衣服1。

k=1时，■；

k=2时，■；

k=3时；■；

k=4时，■；

k=5时，■。

方法2 正向递推法

要保证模特的顺序保持不变是实现不了的，故考虑要想使得模特的顺序不变，模特1的选择只有衣服1、2、3，模特5的最优选择是衣服7。

当模特1选择衣服3时，其余模特的选择只有一种，即模特2选择衣服4，模特3选择衣服5，模特4选择衣服6，模特5选择衣服7；当模特1选择衣服2时，模特2只能在衣服3、4中选择，由于5<18，故模特2应当选择衣服3；模特3同样有两种选择，即衣服4、5，由于8>2，则模特3选择衣服5时，■；当模特3选择衣服4时，■，由于14>-3，则模特4选择衣服6时，■；当模特4选择衣服5时，■；故模特5衣服7；当模特1选则衣服1时，■；由于6<18，模特2有2种选择，即衣服2或衣服3，从以上结果可知模特2选择衣服3之后的有三种结果，由于6=5+1，故得到的三个顺序分别为：1-3-5-6-7，1-3-4-6-7，1-3-4-5-7。

当模特2选则衣服2时，■，由于10>2，则模特3有三种选择，当选择衣服5时，■，当模特3选择衣服4时，■，由于16=14+2，则■；当模特3选择衣服3时，■，由于27>-3，则当模特4选择衣服6时，■，当模特4选择衣服5时，■，模特5选择衣服7，■；当模特4选择衣服4时，■，模特5选择衣服7，■。故可以得到下表：

■

由此得出一个最优方案为：1-2-3-6-7。

三、总结

动态规划是求解最优化问题的一种途径、一种方法，往往针对一种最优化问题。动态规划的设计方法对不同的问题，有各具特色的解题方法。本文介绍了动态规划服装搭配方面的实际应用。通过求解，总结出了动态规划方法的便利性和高效性。

参考文献

[1]刘凤鸣.动态规划的应用[J].Science Technology Vision，2013，13（7）：40-43.

[2]赵娟，樊超.动态规划方法的应用研究[J].Computer Ero，2014，7（2）：28-30.

[3]厉洋峰.动态规划及其在数学模型中的应用[J].China New Technologies and Products，2009，16（8）：224-225.