动态规划的技巧- 阶段的划分和状态的表示

动态规划的技巧—阶段的划分和状态的表示

在动态规划的设计过程中，阶段的划分和状态的表示是特别重要的两步,

这两步会直接影响该问题的计算简单性，有时候阶段划分或状态表示的

不合理还会使得动态规划法不适用。

［例9］街道问题

在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。

这是一道简洁而又典型的动态规划题，很多介绍动态规划的书与文章中

都拿它来做例子。通常，书上的解答是这样的：

依据图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变

量Xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成

了一个特别的多段图。用决策变量阪=0表示向右走，uk=l表示向上走，

则状态转移方程如下：

（这里的row是地图竖直方向的行数）

我们看到，这个状态转移方程需要依据k的取值分两种状况争论，显得

特别麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因

而我们在实现时，一般是不会这么做的，而代之以下面方法：

（这里Distance表示相邻两点间的边长）

这样做的确要比上面的方法简洁多了，但是它已经破坏了动态规划的原

来面目，而不存在明确的阶段特征了。假如说这种方法是以地图中的行

(A、B、C、D)来划分阶段的话，那么它的“状态转移”就不全是在两

个阶段之间进行的了。

或许这没什么大不了的，由丁实践比理论更有说服力。但是，假如我们

把题目扩展一下：在地蛰中找出从左下角到右上角的两条路径，两条路

径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，

再用这种“简洁”的方法就不太好办了。

假如非得套用这种方法的话，则最优指标函数就需要有四维的下标，并

且难以处理两条路径”不能重叠”的问题。

而我们回到原先“标准”的动态规划法，就会发觉这个问题很好解决，只

需耍加一维状态变量就成了。即用X"(ak,b。分别表示两条路径走到阶段

k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示

两条路径的行走方向。状态转移时将两条路径分别考虑

在写规划方程时，只要对两条路径走到同一个点的状况略微处理一下，

削减可选的决策个数：

从这个例子可以看出，合理地划分阶段和选择状态可以给解题带来便利。

[例10]LITTLESHOPOFFLOWERS(IOr99)

PROBLEM

Youwanttoanangethewindowofyourflowershopinamostpleasantway.

YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastas

manyvasesorderedinarow.Thevasesaregluedontotheshelfandare

numberedconsecutively1throughV,whereVisthenumberofvases,from

lefttorightsothatthevase1istheleftmost,andthevaseVistherightmost

vase.Thebunchesaremoveableandareuniquelyidentifiedbyintegers

betweenIandF.Theseid-numbershaveasignificance:Theydeterminethe

requiredorderofappearanceoftheflowerbunchesintherowofvasesso

thatthebunchzmustbeinavasetotheleftofthevasecontaining

bunch/wheneverz<^.Suppose,forexample,youhaveabunchofazaleas

(id-number=l),abunchofbegonias(id-number=2)andabunchof

carnations(id-number=3).Now,allthebunchesmustbeputintothevases

keepingtheirid-numbersinorder.Thebunchofazaleasmustbeinavaseto

theleftofbegonias,andthebunchofbegoniasmustbeinavasetotheleft

ofcarnations.Iftherearemorevasesthanbunchesofflowersthenthe

excesswillbeleftempty.Avasecanholdonlyonebunchofflowers.

Eachvasehasadistinctcharacteristic(justlikeflowersdo).Hence,putting

abunchofflowersinavaseresultsinacertainaestheticvalue,expressedby

aninteger.Theaestheticvaluesarepresentedinatableasshownbelow.

Leavingavaseemptyhasanaestheticvalueof0.

VASES

12345

1(azaleas)723-5-2416

Bunches2(begonias)521-41()23

3(carnations)-215-4-2020

Accordingtothetable,azaleas,forexample,wouldlookgreatinvase2,but

theywouldlookawfulinvase4.

Toachievethemostpleasanteffectyouhavetomaximizethesumof

aestheticvaluesforthearrangementwhilekeepingtherequiredorderingof

theflowers.IfmorethanoneaiTangementhasthemaximalsumvalue,any

oneofthemwillbeacceptable.Youhavetoproduceexactlyone

arrangement.

ASSUMPTIONS

•1<=F<=100whereFisthenumberofthebunchesofflowers.The

bunchesarenumbered1through/7.

•F<=V<=100whereVisthenumberofvases.

•-50<=Aij<=50whereA(/istheaestheticvalueobtainedbyputtingthe

flowerbunchzintothevase/.

INPUT

Theinputisatextfilenamedflower.inp.

•Thefirstlinecontainstwonumbers:F,V.

•ThefollowingFlines:EachoftheselinescontainsVintegers,so

that4/；isgivenasthe/z,,numberonthe(i+Inlineoftheinputfile.

OUTPUT

Theoutputmustbeatextfilenamcdflower.outconsistingoftwolines:

•Thefirstlinewillcontainthesumofaestheticvaluesforyour

arrangement.

•ThesecondlinemustpresentthearrangementasalistofFnumbers,

sothatthck'thnumberonthislineidentifiesthevaseinwhichthe

bunchesput.

EXAMPLE

flower.inp:

35

723-5-2416

521-41023

-215-4-2020

flower.out:

EVALUATION

•Yourprogramwillbeallowedtorun2seconds.

•Nopartialcreditcanbeobtainedforatestcase.

本题虽然是101'99中较为简洁的一题,但其中大有文章可作。说它简洁,

是由于它有序，因此我们一眼便可看出这题应当用动态规划来解决。但

是，如何动态规划呢？如何划分阶段，乂如何选择状态呢？

v方法1>

以花束的编号来划分阶段。在这里，第k阶段布置第k束花，共有F束

花,有F+1个阶段，增加第F+1阶段是为了计算的便利；状态变量Xk

表示第k束花所在的花瓶。而对于每一个状态Xk，决策国就是第k+1

束花放置的花瓶号；最优指标函数fk(xQ表示从第k束花到第n束花所

得到的最大美学值;A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F

是花的总数。

状态转移方程为乂卬二勺

规划方程为

边界条件为：

心+1⑸+】)=

事实上这是一个虚拟的边界。

最终要求的最大美学价值是

〈方法2>

方法1的规划方程中的允许决策空间：xk+i<Uk<V-(F-k)+l比较麻烦，因

此有待改进。还是以花束的编号来划分阶段，第k阶段布置第k束花;

状态变量Xk表示第k束花所在的花瓶；留意，这里我们考虑倒过来布置

花瓶，即从第F束花开头布置到笫1束花。于是状态变量风表示第k-1

束花所在的花瓶；最优指标fk(Xk)表示从第一束花到第k束花所获得的

美学价值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的

总数。则状态转移方程为：

规划方程为：

增加的虚拟边界条件为：

最终要求的最大美学价值是：

可以看出，这种方法实质上和方法1没有区分，但是允许决策空间的表

示变得简洁了。

〈方法3>

以花瓶的数目来划分阶段，第k个阶段打算花瓶k中是否放花；状态变

量Xk表示前k个花瓶中放了多少花；而对于任意一个状态Xk，决策就

是第Xk束花是否放在第k个花瓶中，用变量U"1或0来表示。最优指

标函数fk(Xk)表示前k个花瓶中插了Xk束花，所能取得的最大美学值。

留意，这里仍旧是倒过来考虑。

状态转移方程