动态规划 5.ppt

动态规划(五)最小代价子母树-问题问题描述:设有n堆沙子排成一排,其编号为1,2,3,…,n(n<=100)。每堆沙子有一定的数量,如下表: **********现要将n堆沙子归并为一堆。归并的过程为每次只能将相邻的两堆沙子堆成一堆,这样经过n-1次归并之后最后成为一堆。如上面7堆沙子,可以有多种方法归并成一堆。其中的2种方法入下图:16214181378202425446987最小代价子母树-问题16214181378153722288759归并的代价是这样定义的,将两堆沙子归并为一堆时,两堆沙子数量的和称为归并2堆沙子的代价。如上图中,将7和8归并为一堆的代价为20。归并的总代价指的是将沙子全部归并为一堆沙子的代价的和。如上面的2种归并方法中, 第1种的总代价为20+24+25+44+69+87=267 第2种的总代价为15+37+22+28+59+87=248由此可见,不同归并过程得到的总的归并代价是不一样的。问题:当n堆沙子的数量给出后,找出一种合理的归并方法,使总的归并代价为最小。最小代价子母树-分析根据问题描述,深刻理解问题。画出一些简单的最小代价子母树。(1)n=213720当n=2时,仅有一种堆法,因此总的归并代价为2堆沙子数量之和。1378202813781528最小代价子母树-分析(2)n=3请你先画一画有几种堆法总代价=15+28=43总代价=20+28=48当n=3时,有2种堆法。由于最后归并的代价为全部沙子数量的和,对任何归并方案都是相同,因此总的代价将取决于第一次归并。由于左边堆法第一次归并代价为15,优于右边堆法20,因此总代价左边为优。161378154431161378204424最小代价子母树-分析(3)n=4请你先画一画有几种堆法。137815281644137820281644161378244431(a)总代价=20+28+44=92(b)总代价=15+28+44=87(c)总代价=20+24+44=88(d)总代价=15+31+44=90(e)总代价=24+31+44=99最小代价子母树-分析(3)n=4时共有5种堆法。这5种堆法可以分成3类:第1类:先归并1~3堆,再与第4堆归并。这是上图(a)、(b)的情形。可以看到(b)要占优是因为(b)中1~3堆是最小代价归并方案。第2类:先归并1~2堆,3~4堆,再归并为一堆。这是上图(c)的情形。第3类:先归并2~4堆,再与第1堆归并。这是上图(d)、(e)的情形。可以看到(d)要占优是因为(d)中2~4堆是最小代价归并方案。归纳上述分析,我们可以得出这样的结论:(1)如果把归并1~4堆看成整个问题,则这个问题可以分解为三个归并方案,每个归并方案包含1~2个子问题: ①归并1~3;再与4归并 ②归并1~2,归并3~4;再归并 ③归并2~4;再与1归并(2)问题的最优解必然是这三种分解方案之一的结果为最优。从上图可以看到,是①方案的结果为最优。而①方案实际有两种堆法,可以看到最终入选的是归并1~3的最优解。也就是说,在问题(归并1~4堆)的一个最优解中,包含着子问题(归并1~3堆)的一个最优解。最小代价子母树-分析(3)请一定要注意的是,参与“竞选”的②③两种方案的子问题也必须是由子问题的最优解构成,否则根本没有机会获胜。例如,在归并2~4堆的子问题中,只有(d)有机会获胜,调小第4堆的数值可以实现这一点,大家可以试一试。但是不管怎样调小数值,(e)都不可能获胜。因为(e)不是归并2~4堆的最优解,(d)才是!同样,在②方案中,归并1~2,归并3~4两个子问题也都是最优解。(4)如果我们继续分析增加更多堆数进行归并的问题,就会发现n个沙堆归并时,会分解为n-1种类型: Case1:“归并”第1堆,归并2~n堆;再最后归并 Case2:归并1~2堆,归并3~n堆;再最后归并 Case3:归并1~3堆,归并4~n堆;再最后归并 …… Casen-2:归并1~n-2堆,归并n-1~n堆;再最后归并 Casen-1:归并1~n-1堆,“归并”第n堆;再最后归并最小代价子母树-分析在Case1和Casen-1两种情况中,都是一堆沙与另n-1堆沙归并。一堆沙没有归并代价,为了形式上的统一,我们把一堆沙的归并代价设为0。这样,在所有n-1种情况中,都是先归并左右两个子问题,求出子问题的最小代价,再归并在一起。致此,我们分析出了问题的最优子结构性质。