（运筹学与控制论专业论文）2dbprg的近似算法及其性能分析.pdf

摘要 二维装箱问题在现实生活中有很多应用，有效地解决二维装箱问 题能更加有效地利用资源，节约成本。二维装箱问题的实际意义促使 学术界在其上面做了大量的工作，无论是对问题适用领域的拓展还是 对新算法的探索或是对已有算法的研究都取得了丰硕成果。 但是在已有文献中，对物体町以旋转的二维装箱问题2 一 d b 非g 的研究并不是很多，且在仪有的几篇研究旋转物体的文献 中，对已有的算法进行性能分析多是采用实验方法进行平均性能分 析，而非采用传统的数学证明方法进行最坏性能分析。鉴于此，本人 对于对装箱问题进行了定研究： 1 ：给出了两个解决2 - d b p r g 问题的近似算法h f f d s ，f f d s ， 并在前人研究的基础上用数学证明的方法对h f f d s 进行了最坏性能 分析。 2 ：把算法的适用范围推广到更加一般的箱子高和宽不等的情况 3 ：本文同时采用了实验的方法，用具体的例子对比了h f f d s 与最优算法以及h f f d s 与f f d s 的性能。 关键词：组合优化装箱问题渐进性能比近似算法 a b s t r a c t t w od i m e n s i o n a lb i np a c k i n gp r o b l e mi sw i d e l yu s e di nr e a l l i f e ，s of i n d i n ge f f e c t i v ew a y so fs o l v i n gt h i sp r o b l e mw i l lc o n t r i b u t et o m o r ee f f e c t i v eu s a g eo fr e s o u r c e sa n dt h u sr e d u c ec o s t t h es i g n i f i c a n c e o ft h i sp r o b l e mu r g e st h ea c a d e m i cc i r c l et od oal o to f i n c l u d e se x p a n d i n gt h ef i e l d sw h e r et h ep r o b l e ma p p l i e s ， n e wa l g o r i t h m so ri n - d e p t hs t u d yo ft h ee x i s t i n ga l g o r i t h m s w o r k ，w h i c h e x p l o r i n gt h e b u ta m o n gt h ee x i s t i n g a r t i c l e s ，t h es t u d y o fb i n p a c k i n g p r o b l e mf o ro b j e c t sw h i c hc a nb er o t a t e db y9 0d e g r e ei sp a i dt ol i t t l e a t t e n t i o n ，m o r e o v e rw h e nj u d g i n gt h ef u n c t i o no ft h ea l g o r i t h m s ，t h e y u s u a l l yr e s o r tt oe x p e r i m e n t a lt e s t si n s t e a do ft h ew a yo fm a t h e m a t i c a l p r o o f , w h i c hw i l lp r o v i d em u c hr e l i a b l e i n f o r m a t i o n u n d e rs u c h c o n d i t i o n ，m u c hw o r ki sd o n eh e r et os t u d yb i np a c k i n gp r o b l e mf o r r o t a t eo b j e c t s i nt h i sa r t i c l en o to n l yt w oa p p r o x i m a t ea l g o r i t h m sh f f d s ， f f d sa r ep r o p o s e d ，b u ta l s oam a t h e m a t i c a la n a l y s i so fh f f d si sg i v e n a tt h es a m et i m e m e a n w h i l e ，i t sp r o v e dh e r et h er e s u l ta l s oa p p l i e st ot h e c o n d i t i o nw h e nt h eb i n sa r er e c t a n g l ec o n t r a r yt ot h ea s s u m p t i o nt h a ta l l b i n sa r es q u a r e s f u r t h e r m o r et h ee x p e r i m e n t a lt e s ti sa l s ou s e df o r c o m p a r i s o no fh f f d sw i t ht h eo p t i m a l a l g o r i t h ma n dh f f d sw i t h f f d s k e yw o r d s ：c o m b i n a t o r i a lo p t i m i z a t i o n ，b i np a c k i n gp r o b l e m ， a s y m p t o t i c w o r s t - - c a s er a t i o ，a p p r o x i m a t ea l g o r i t h m l r r s ( r ) l ( r ) z 蠢 w c r ) h ( r ) l x ) w ( r ，z r ) w f r ) h ( 1 蛰 f f d s ( u 符母说明 待排物体集 l 的一个子集 乙中鹃元素，鄄一令镑撵耱 奉 待排物体r 的短边长度 待排物体r 的长边长度 物藩莠 刭在簇予中戆蓑 爨方蠹，有鬻个谴，横簧 或竖妻豢 集合r 中耪体宽发之和 集合r 中物体离之和 定义域为( o ，1 1 聪蒯上的函数 耪俸r 懿宽边殴漤，宅取决予秘傣在瓣子瓣撵羁方自窝携俸豹 长短边，为物体摊定之后与箱子水平边平行的边的长度，为了 书写方便，文中在不引起歧义的地方用w ( 0 代镨 物体r 的高，它取决于物体在箱子的排列方向和物体的长短边， 为物俸搀定之蜃弓籍 二垂壹逮平行豹边静长瘦，为了书鹭方 便，文中在不弓l 越歧义的地方霜h ( r ) 代替 函数，自变量为待排物体r 宽边值，由于宽度原因也取决于物 体的排列方向，为了书写方便，文中在不引起歧义的地方用 w ( 螃代替 番数，鑫变量为符簧 谚体r 酶高懿德，盘子毫的篆因浚敬凌予 物体的排列方向，为了书写方便，文中在不引起歧义的土墩方用 h ( r ) 代替 r 中物体r 的函激值w ( r ，r ) ) 之和 r 中耱俸r 鲶蘸数擅w ( r ，奄) ) 之器 f i r s tf i td e c r e a s i n gs h o r tc d g ca l g o r i t h m 装箱问题的一种鲜法 h f f d s ( l 1 p h y b r i dh r s tf i td e c r e a s i n gs h o r te d g ea l g o r i t h m 装箱问题的一 种算法 算法a 的最坏性能比，体现最坏情况下算法的性能 算法的渐近性能比，用它来得到最坏性能比的信息 第一章引 言 装箱问题在实际生活中有很多应用，1 一在二十世纪七十年代，学术界就开始 对装箱问题进行了大量研究，研究对象包括一维，一维和高维物体。其中，维 问题可简单描述为把具备一定长度的物体装到有相同k 度的若干一维箱子中，要 求每个箱子中物体的长度之和不超过箱子的长度，并尽可能使所朋的箱子数目最 少。二维和高维问题都是一维装箱问题的扩展，很多对f r 一维物体的结论都适j 日 二维和高维问题，但是后两个问题毕竟复杂的多，所以需要很多特殊的方法来研 究。本文将对二维装箱问题给出大略的介绍，然后择其一个子问题进行详细的探 讨。探讨过程中应用的对j 二一维问题的结论将在第三章和后续的章节中给出。这 里只是以少量笔墨介绍一下二维装箱问题和它的研究成果以及本文的意义。 1 1 二维装箱问题的适用领域 二维装箱问题的适用领域很广。在制造玻璃，生产家具等需要切割原材料的 行业中，需要把原来统一，t 寸的长方形原材料切割成不同大小的长方形备用品， 这在二维装箱问题巾对应为切割问题( c u t t i n gp r o b l e m ) ；在报社的排版，货架物 品的排放，计算机内存的分配等问题中，需要把平而资源有效地进行分配，这对 应二维装箱问题中的排列问题( p a c k i n gp r o b l e m ) 。两类问题在本质上是相同的， 若用简单通俗的语言描述其本质，就成为把不同规格的小长方形装在统一规格的 大长方形中，尽量减少空问的浪费，使所用的人长方形越少越好。 还有一类问题也应归入二维装箱问题家族，此类问题的典型代表如在造纸 和织布行业中，原材料的单位是卷或捆，宽度一定，长度可以很长，同样需要解决 的是如何从原材料中裁下满足要求的待用品，使所用的原材料的长度最少。这相 当于把长方形小物体装在底一定但是上不封顶的箱子巾，此类问题是几乎和二维 装箱问题等价的问题，被称为s t r i pp a c k i n g 。 1 2 二维装箱问题的分类 正因为二维装箱问题的应用领域很广，每个具体的应用有着独特的要求，所 以二维装箱问题细化为很多子问题。 首先，根据装箱之前全部物体的信息是否己知分为离线装箱问题( o f f - l i n e b i np a c k i n g ) l 口在线装箱问题( o n l i n eb i np a c k i n g ) 。前栉是实践中经常遇到的问 题，在大多数情况下都成立；后者适用排列当前物体时下一个物体信息未知的情 况，例如计算机内存的分配，在存储当前的数据时，下一个存储任务的信息并f i 可知。 另外，二维装箱问题视具体情况有两个附加条件，第一个条件是关于物体可 旋转与否，例如报纸排版要求排放的文字块不能旋转，这种装箱方式被称为 o r i e n t a t i o np a c k i n g 。与之相反，若对待排放物体无此要求，则称装箱规则为r o t a t e p a c k i n g 。第二个条件的产生是由于现代工业的自动化特征，要求在切割物体时， 每条切割线都要平行于待切割物体，顺次沿着某条切割线切割，就能得到满足要 求的小长方形。这个规则被称为g u i l l o t i n ec u t t i n g ，相反，装箱或切割时并不附 加此种要求的切割方式被称为f r e ec u t t i n g 。综上所述，二维离线装箱问题分为 2 - d b p r g ：待排放物体可以旋转，而且排放满足g u i l l o t i n ec u t t i n g 的条件 2 - d b p o g ：待排放物体不可以旋转，而日排放满足g u i l l o t i n ec u t t i n g 的条 件 2 - d b p r f ：待排放物体可以旋转，而且排放不必满足g u i l l o t i n ec u t t i n g 的 条件 2 - d b p o f 待排放物体可以旋转，而且排放不必满足g u i l l o t i n ec u t t i n g 的 条件 1 3 二维装箱问题的研究成果 距今为止，j 二维装箱领域已经取得了一一定的成就，归纳下来，成果的取得不 外乎以下几种途径 1 ：寻找新的算法，能尽量节省箱子的数f 1 ，而不管所川时间多少 2 ：寻找新的算法，它致力于尽快找到一种较满意的装箱方案，在保证所用 箱子数目并不急剧上升的前提下，争取在较短的时问内解决问题 3 ：研究已有算法或改进算法，对其进行性能分析。 途径1 的算法可以是精确算法，也可以是近似算法，而途径2 的算法就一般 为近似算法了。 2 f 1 0 3 一s 一2 04 其中近似算法又分为 一般近似算法( a p p r o x i m a t ea l g o r i t h m l 启发式算法( h e u r i s t i ca l g o r i t h m l 后脑发式算；去, ( m e t a h e u r i c t i cp d g o r i t h m l 现已取得的成就( 不完全统计如下) ： 对于2 - d b p o ；( 2 d b p o g ，2 - d b p o f ) ，已存在很多很成熟的算法和大量 对算法的分析。建模方法见g i l m o r e 和g o m o r y 1 1 ，b e a s l e y 2 1 ，f e k e t e 和 s c h e p e r s 3 ；一般近似算法见c o f f m a ne ta 1 4 j ( 对于s t r i pp a c k i n gp m b l c m ) ，c h u n g e ta 1 【5 】( 对于b i np a c k i n gp r o b l e m ) ；启) 溯, l o d ie ta 1 6 】；文献中部有对于 算法性能的详尽的分析，详细信息见 7 。 而对于2 - d b p r t ( 2 一d b p r g ，2 - d b p r f ) 的研究成果大大少于上一类 问题，现已知 7 给出了针对2 - d b p r g 的k i d n a p p i n g 算法，f l o o rc c i l i n g 算法， e l - b o u r ia h m n e d , p o p p l e w e l ln e i l 8 ，【9 1 给出了针对2 - d b p i v f 的启发式算，同 时也给出了针对2 d b p r g 的启发式算法。上述文章在对算法进行分析时都是 采用了实验的方法，对算法的平均性能进行了分析。 而如下文章用数学证明的方法分析了对于旋转问题的近似算法的最坏性能： m a u r o ，s i l v a n o ，d a n i c l c ( 1 0 1 ，给出了针对2 一d b p r f 2 f f s 似算法最坏性能比的下界， s a t o s h if u j i t a ，t a k e s h ih a d a 1 1 给出了对于可旋转物体在线装箱问题近似算法的 渐近性能比。 到目前为止，还没有一篇文章对于2 d b p r g 问题的近似算法进行最坏性能 分析。 鉴丁：此，本文着手研究2 d b p r g 的两个一般近似算法，它们实际上肘 2 - d b p o g 问题的一个算法的推广，文章组织如下：第二章是对问题，一般近似 算法及性能分析指标进行介绍。第二章提出算法并用数学证明的方法分析算法性 能。第三章用实验的方法验证算法的性能。 第二章二维装箱问题 2 1 一维装箱问题的数学描述和若干结论 二维装箱问题是一维装箱问题的扩展，所以在引进二维装箱问题的数学描述 之前，先介绍一下一维装箱问题( 1 - d b p ) 。 1 - d b p 的数学描述：有一个集合j ，iji 一1 1 ，其中每个元素有权重h j ，h j 不 大rh ，现要把j 分成尽可能少的子集，使每两个子集之间没有交集，并且每个 子集权重之和不超过h 。这里若视h 为一维箱子的长度，j 为待排物体集，h i 为 物体长度。则解决上述数学问题就相当于解决用最少的箱子排放物体的问题，所 以此类问题被形象地称为装箱问题。为了研究的方便，同时也不失一般性，通常 在研究一维装箱问题时假设h 为1 。 对j 二一维装箱问题，现已存在精确算法，但是由r 刈人规模的问题的精确算 法耗时太长，使得许多近似算法应运而生，经典的一维装箱问题的近似算法包括 f i r s tf i t ，n e x tf i t ， b e s tf i t 。 f 1 r s tf i t 对于某排列问题，已使用了若干箱子，第一个箱子为b 。，最后一个箱子为 b 。，当前待排放物体为j ，排放之前依次检测b lb 2 b l ，查看剩余长度是否能 容纳i ，然后把物体排放在第一个能够适合的箱子中，若这样的箱子不存在，开 启一个新的箱子排放物体。 n e x t f i t 同样需要排放物体j ，已开启了t 个箱了。只检测最后一个箱子的剩余长度 是否能容纳当前物体，是则把物体紧挨最后一个箱子的最后一个物体放置，否则 开启一个新的箱子放置物体。 b e s t f i t 检查若把j 放在b 。b z b 。中剩余氏度的大小，取使之剩余长度最小的那个 箱子放置i 。 2 2 二维装箱问题的数学描述 2 - d b p 的数学描述：有一长方形物体集j ，ijl = n ，其中每个元素j 都是 长方形，并且具备的宽度和高度分别为w i ，h j ，现要把它们排放在宽为w ，高为 h 的长方形箱子中，彼此不能重叠，问如何排放才能节省箱子的数目。 二维装箱问题的一个图示如 有宽和高分别为3 米的箱子若干，待排放物体如i - 待排放物体可以排列如下，当然还有别的若干种排列方式，装箱问题就是致 力于找到一种排列方式使所用的箱子数最少。 e 2 3 解决二维装箱问题的一些思路 本文所要阐述的二维装箱问题的算法是近似算法，一些近似算法的思路分 为： 两阶段法( 如图) 与一阶段法 进行两阶段法，先把两物体按某种规则排在一个底与箱子底等长但是上不封 顶的箱子中，形成若干复合物体，再把复合物体视为待排物体，按照某种规 则最终排在箱子中。进行一阶段法则直接把物体按照某种规则排在箱子中。 两阶段法的示例： 阶段1阶段2 按层排列法与非按层排列法 按层排列法把箱子分成若干层，较高一层以较低一层的顶部为底，依次把物 体排在相应底层中，非按层排列法则反之。上图所示的排法也属于按层排列法， 而非按层排列方式如图示： j # 接屡羹 列注 简单方法与复杂方法 简单方法按莱单一原则排放物体，排放之后物体不会再移动。复合方法或 是在排法中综合使加两种近似算法，或是分另0 采用不同的方法排列物体，比较之 后取其优或是在已有的排法基础上进行有目的的移动物体，修正排法使之优化。 例如：第一种如先采用分层算法，当第一层的第一个物体已确定之后，对剩下的 待排物体使用k i d n a p p i n g 算法找出排在本层的后继物体。第三种方法如t a b u 搜 索法，先给出一个排列方式，然后不断修正排列方式，使效果更加。很显然，采 用复杂算法会提高算法的精度，但会浪费很长时间。 8 2 4 评价算法的性能指标 如果p 是一个装箱问题的算法，l 是一个待排放物体集，定义p ( l ) 为用这个 排法解决装箱问题所用的箱子数，定义o p t ( l ) = m i n p ( l ) ：p 是对l 的一种排法 。 对于任何一个具体的装箱问题，它的最优排法肯定存在，但是由于实际问题的复 杂性，寻找最优排法几乎是不可能的，取而代之的，寻找一个近似最优的排法则 更具有实际意义。基于此种想法，无论是针对1 - d b p 亦或对于2 - d b p , 都已存在 很多近似算法，随之也产生了评价算法优劣的标准。目前，有两种途径可以分析 近似算法的性能： 第一种为数学证明的方式，计算出指标最坏。能l l ( r 2 ) 。这里先给出r 2 的 定义，再阐述用它进行分析的意义。 定义r 。( i d = a ( l ) o p t ( l ) ( l 为任意待排放的物体集，a 是一种算法) 定义硝= m a x r 。( l ) ：o p t ( l ) = n 定义只：一l i r as u p 一，彤 这个指标给出了对最坏情况的分析，有了该指标，可知无论是对于何种物体 集，用近似算法求得的解都是在最优排法的一个已知数倍的范围之内。很显然， r ；越是接近于1 ，说明算法越是好。 虽然最坏性能比具备很重要的意义，大多数文献中都把取得算法的最坏性能 比作为对算法分析的最终f 1 标，但是由于实际问题的复杂性，这个指标一般不能 直接计算m 来，所以通常可以用下面的方法计算聪的上界或f 界，得到关于r ： 的信息。 ( 1 ) 分析渐近性能比p ， 定义p 满足a ( l ) po p t ( l ) + t ( t 为常数，l 为任一待排物体集) 若是对j 二任何。一个大于0 的很小的数和任意一个足够大的n ，都 存在一个例子，使得a ( i ) ( p 一8 ) + o p t ( 1 ) ，并且o p t ( l ) n ，那 么p 是紧的，就是上面所述的r ；。 若p 不是紧的，那么p 是r ：的一个卜界，这说明该算法是收敛的。 若是算法a 不存在渐近性能比，即对于任何m 1 ，存在例子i ，使 得a ( i ) mo p t ( 1 ) ，那么r ；= 。，这说明算法a 是不收敛的，不 是一个好算法。 ( 2 ) 寻找具体的例子i ，若使得a ( i ) ao p t ( i ) ，则找到砰的一个下界， 同样，这个下界越小越好，虽然这并一定说明r ：一定小。 第二种分析算法性能的方式为实验方法，用此种方法进行分析是源于计算 机的广泛应用。用计算机模拟产生待排列的物体集，分析在。般情况下，算法的 性能。所以与第一种分析方式不同，这里更加注重通常，或者说平均的结果，而 不是极端最坏的情况。由于在这种情况下，无法给出最优排法的信息，所以一般 都是用于两种或多种算法的比较，本文也在最后一章中应用了这种方法，对比了 将提到的两种算法的性能。 第三章针对2 - d b p r g 的h f f d s ，f f d s 算法及对t i f f d s 的最坏 性能分析 3 1h f f d s ，f f d s 算法描述 假设：( 1 ) 这里先假定箱子的高和宽均为1 ，更一般的情况本文后面讨论。 ( 2 ) 箱子不可以旋转，与水平边平行的边为宽或底边，与水平边垂直 的边为高 h f f d s 算法属于前面所述算法分类中的两阶段算法，简单算法和按层排列 法。 算法描述：将所有待排放物体按最短边的降序排列( 这个顺序定义为初始顺 序，形成的物体队列定义为初始队列，后文会提及) ，在第一阶段先按照f i r s tf i t 原则排列在底边为1 ，上不封顶的箱子中。第二阶段按照f i r s tf i t 原则解决一 维装箱问题。具体操作如下： 将所有物体按照最短边降序排列 对于第一个物体，以短边为高，排放在箱子的左下角，形成了一个以其 短边长度为高的一层。 对于后续每一个待排放物体，先以其短边为高，检查它能否在第一层剩 余空间中( 在该层的右侧) 排列，如果不能够排列，再以短边为高试试 看，如果仍不能排列则以同样的方法检查第二层，以后依次类推，直到 把物体排列在第一个能够容纳该物体的层中为止。若找不到能够容纳该 物体的层，则创立新的一层，每创立新的一层，新层都以该层的第一个 物体的短边为高。 待所有的物体均排列完成之后，把所得到的各层作为一维物体( 因为宽 度为1 ，所以不考虑这。维度) ，按高度降序排列，然后按照f i r s tf i t 原则排在长为1 的一维箱子中。 算法f f d s 属于一阶段算法，基本排法同h f f d s ，只是把物体直接排在箱 子中。具体操作如下： 将所有物体按照最短边降序排列 对于第一个物体，以短边为高，排放在第一个箱子的左下角，形成了一 个以其短边长度为高的一层。 对于后续每一个待排放物体，先以其短边为高，检查它能否在第一个箱 子中第一层剩余空间巾( 在该层的右侧) 排列，如果不能够排列，再以 短边为高试试看，如果仍不能排列则以同样方法尝试第二层，直到尝试 完第一个箱子所有已存在的层，如果不存在一层能够容纳该物体，则检 查第一个箱子剩余的高度，看是否能够以该物体的短边长度为高创立新 的一层。若不能够创立新的一层，则以同样的方式检查第二个箱子，依 次类推。若现有的箱子都不能容纳该物体，则开启新的一个箱子，创立 在新的箱子中的新的一层。 3 2h f f d s 算法的最坏性能分析 为了分析h f f d s 的最坏性能比，需证明下面的定理。 定理1 ：对任意边陈匈小于1 的长方形物体集l ，h f f d s ( l ) 表示用h f f d s 方法排列l 所得结果，o p t i 表示最优排法所得结果，则 h f f d s ( l ) , c 1 7 4 0 p t ( l ) + 5 3 2 1 证明渐近性能比之前的准各知识 为了证明上述定理，我们首先给出以下的定义，引理1 ，2 ，3 并证明引理4 。 ( 1 ) 定义 定义一个度量函数f ：( 0 ，1 1 一( 0 8 5 i f ( x ) = 6 一x 91 一工一 51 0 61 一石十 51 0 64 一x + 一 51 0 度量函数具备如下性质： ( a ) 若x y ，则f ( x ) f ( y ) 如果o 。；三 6 如果! 。；1 6 3 如果三。z ；兰 32 虫日果! 。z 1 ( b ) 定义单位度量函数为上盟 x 则单位度量函数值= 6 5 ( 丽1 3 ，而1 5 1 ( 而1 5 ，而1 4 1 ( 2 ，爿1 6 如果( o 。x 5 _ 1 ) b 如果( 三。xs = 1 ) 0j 如果( ；c 工s 知 虫果( ；。x s l ) 类似f ( x ) 的定义，定义对于二维物体的度量函数w ( r ，z ( r ) ) ，h ( r ，z ( r ) ) ，定 义之前首先定义物体的宽度和高。 对于r e l ，r 已被摆放在某个箱子中，设w ( lz ( r ) ) 为宽度，h ( r z ( r ) ) 为 高度。由于物体可以旋转9 0 度，所以物体在箱子中排列时有两个方向，如图 竖排描排 由于同一物体在箱子中的排放方向不同，使得它的宽度和高度不同。若它是 竖排，则w ( f ) = s ( r ) ，h ( r ) = l ( r ) ；若它是横排，则w ( r ) = l ( r ) ，h ( r ) 一s ( r ) ( 文中在不引起歧义的地方都分别用w ( r ) ，h ( r ) 代替w ( lz ( r ) ) ，h ( r ，z ( r ) ) ) 。 定义 w ( r ，z ( r ) ) = h ( r ，z ( r ) ) 2 6 5 w ( r ，z ( r ) ) 9 5 w ( r ，z ( r ) ) - 1 1 0 6 5 w ( r ，z ( r ) ) - i - 1 1 0 6 5 w ( r ，z ( r ) ) + 4 1 0 6 5 h ( r ，z ( r ) ) 9 5 h ( r ，z ( r ) ) 一1 1 0 6 5 h ( r ，z ( r ) ) + 1 1 0 6 5 h ( r ，z ( r ) ) 十4 1 0 如果0 州r ，z ( r ) ) s 1 6 如果1 6 似r ，z ( r ) ) s1 3 如果1 3 w ( r ，z ( ，) ) s1 2 0 t i 果1 2 w ( r ，z ( r ) ) s1 如果0 h ( r ，z ( r ) ) s1 6 如果1 6 h ( r ，z ( r ) ) 1 3 如果1 3 h ( r ，z ( r ) ) 1 1 2 如果1 2 h ( r ，2 ( r ) ) 1 l3 文中在不引起歧义的地方用w ( r ) ，h ( r ) 代替w ( r ，z ( r ) ) ，h ( r ，z ( r ) ) ( 2 ) 对于一维问题，存在下列结论 引理1 ：存在一个集合j ，集合中元素为j ，其值为h j ，满足o h j 一 一m - - 1 ( 汪明过程参见【1 4 】中引理5 的证明) 引理3 ：b 是一个数集，集合中元素x ，满足c x 1 ，并且y ，0 ) c 1 ，则 为 或者俐= 1 ，且唯一的一个元素x 1 尼或者荟x l - c - 昙( 1 一荟，o ) ) 证明过 程参见【1 5 】中定理2 的证明) 因为二维装箱问题是一维装箱问题的扩展，所以如果单独考查二维物体的 一个维度，上述引理仍成立。例如对于二维物体集l ，如果r l ，并且w ( r ) 满足芝。w ( r ) s 1 ，h ( r ) 满足。 ( r ) s 1 ，则根据引理1 ，w ( r ) ；m ( r ) s 1 7 1 0 ，h ( r ) ；m 日( r ) s 1 7 1 0 同理引理2 ，引理3 在二维物体的某一维度上逝适用。 根据上述引理和定义，证明引理4 引理4 ：对于一个待排放的物体集l ，设f f d s i ( l ) 代表用h f f d s 的第一阶 段方法把它排放在底为1 ，上不封顶的箱子中( s t r i pp a c k i n g ) 所能达到的高度； o p t ( l ) 代表将l 排放在底和高为1 的箱子中所用的最少箱子数，那么f f d s i ( l ) 2 8 9 0 盯( l ) + 1 证明：度量函数的定义同匕， f ( x ) 一 ( 6 5 ) x ( 9 5 ) x 一1 l o r 6 5 ) x + 1 1 0 ( 6 5 ) x + 4 1 0 立口果0 xe 1 6 虫口果1 6 zs 1 3 如果1 3 xs 1 2 如果1 2 x s l w ( r ，z ( r ) ) = 6 5 w ( r ，z ( ，) ) 9 5 w 0 ，z ( r ) ) 一1 1 0 6 5 w ( r ，z ( r ) ) + 1 l o 6 5 叫r ，z ( ，) ) + 4 1 0 如果0 c 州r ，z ( r ) ) s 1 6 如果1 1 6 1 ，故 荟荟 职啦崛) 因为f f d s l ( l ) = h ( t 2 ) + h ( t 1 ) ，故为了证明上述结论成立，即证 荟荟坼帅) 洲( 驴1 定义l l 为l 的一个子集，它包含所有位于t 1 中的待排物体，重新用f f d s l 方法进行s t r i p p a c k i n g ，得到的结果同t - 中物体排列方式一样。故以下分析虽是 针对重新排列所得结果，但并不影响证明结果。 定义b 1 ，b 2 ，b 。为从下至i ：排列的层，h i 为其高，定义h 一o 。 根据物体在f f d s l 排法中的不同情况把物体分为正常排列物体和不规则排 列物体，定义正常排列物体为按照初始队列( 1 l 页) 中的先后次序排列的物体， 而不规则排列物体为打破了初始顺序，排到前面的物体。例如待排物体有这样一 个排序a b c ( 表示排序时排在前面) ，但是在排列时，a 排在第一层，b 排 在第二层，c 排在第一层a 的右侧，则称c 为不规则物体，而a ，b 为正常排列物 体。 记是b i 中第一个正常排列的物体，r i 为b i 中所有正常排列的物体的集合。 对于1 i t ，1 j j ，定义f i i 为顺序在b h 中所有正常排列物体之后但是 在b i 中所有正常排列物体之前排列在马中的物体，例如当前排列到b i 一。层，所 有应该排在b h 层中的正常排列物体已经排列完毕，开始计时，直到b i 层开始 创立，计时完毕，此段时间内排列在前面层b i 中的物体定义为r 。 对于1 i t ，1 j i ，定义s “为顺序在b i 中第一个物体之后但是在最后一 个规则排列物体之前排列在b i 中的物体，例如当前排列到b l ，从本层创立的时 刻开始计时，到本层最后一个规则排列的物体排完之后，计时完毕，此段时间内 排列在前面层面b j 中的物体定义为s i i 。可知，计算s i “ ( 1 - ejc i ) 的终止时 刻既是记录r ( 1 sjc i ) 的开始时刻，通过如上定义，把物体集l 1 分成了正常 排列物体和两类不规则排列物体集，这些物体集正好包含了原问题中所有的物 体。为了更好地理解上述定义和后面的定义，给出图形： b i 一1 b j r j 民s uq j 主恿，f 1 i 1 2 呸，1 i l 开且 l i = u i r i u uf 句ul s b l l l t 稻i i “ 对于每个i ，l i t 和每个j ，l j i ，定义c i j 为b i 中最后一个规则排列 的物体排列完成之后b j 右侧所剩余的宽度，注意下面的关系成立。 呱) 2 白十荟川，1 如川( 1 ) 旷吼，一；黔2 魂k 卜卜( 2 ) 定义c i = m a x c q 对于1 i 引，很显然c 1 2 0 。 若是对于任何一个i ，1 i t ，都存在一个i ，成立 墨。呻，毒屯州小詈c e l _ i - - c i i , 卜 因为b i 中每个规则排列物体的高度至少为h ，1 i t ，并且b j 中第一个 物体的高度为h i ，f i l ，s 。中的物体的高度至少为h i ，h i + l ，l 1 6 5 w ( r ) ，上面的和至少为 耄阻墨，c r ，+ 导c h ；- h i + z 一+ 盏州呦+ 导只墨w c r ，+ 5m 盏w c 川 17 加墨。呻，+ 缸m p 争毒 根据( 3 ) ，( 4 ) 瓦石边芏少为 芑i ；+ ；h ；( c i 一- 一吒) + 詈( 日。一日。+ - ) c 。1 由于c c i i 及c 1 2 h t + 1 2 0 ，h 1 1 我们可以得出结论 荟坶帅，z 扣；一扛 + 扣- z h ( 正) 一h 。一詈荟 皿+ l c ，+ j 6 丢, - 1 h 。c ； z h ( l ) 一日。+ ，6t - 薹h ；+ 。( c i - - e 1 ) 结果得证。故我们只需要证明 对于任何i ，l 1 2 ，所以存在i ，使得f 。 i - - l c - l ，所以说明无论r 在r 卜- 巾横放还是 竖放，w ( r ) c jl 若设c = c r _ l ，则引理3 适用集合r i _ j ，得出结论：或者w ( e ) 1 2 ( 此种情 况不成立，因为与t ，的定义矛盾) 或者 墨“一窖p 设i = i 一1 ， 则 乇。1 一墨一三 小( i - q _ l - 罂卜未， 弘- - + 扣墨y c 咖三，川，成立 引理4 得证，f f d s i ( l ) 2 8 9 0 州l ) + 1 3 2 2 h f f d s 算法的渐近性能比 证明定理1 ：h f f d s ( u 一1 7 4 0 p t ( l 。) + 5 ， 三。也违反了定理1 ，这与l 为最小反例矛盾。 很显然若x l 2 ，s 排法与最优排法所用的箱子数一致，结论自然成立。故 剩下只需证明x 1 2 。 根据x 的大小，证明分以下4 种情况。 2 0 0 3 5 2 0 19 情况1 ：设x 1 5 这样除了最后一个箱子之前的高度都应该超过4 5 ， 故4 5 ( h f f d s ( l ) 一1 ) f f d h i ( l ) 2 8 9 0 p t ( l ) + l 其中第一个不等号成立 是因为f f d s l 是h f f d s 的第一阶段算法，它得出的层的高度和应该等于h f f d s 算法所得每个箱子所用高度和。第二个不等号成立是因为引理4 。 故h f f d s ( l ) ( 5 4 ) + ( 2 8 9 1 0 0 ) o p t ( l ) + 9 4 - - 1 一x x 2 = r ：( 1 一x ) s ( r ) 1 2 ) x 3 = ”1 2 一 s ( r ) ( 1 一x ) 2 x 4 = r ：( 1 一x ) 2 s ( r ) 1 4 x j = r ：1 4 一s ( r ) x 把x 。设为空并不影响结论，因为集合x 。中的物体无论是在最优排法中还 是在f f d s 排法中，都必须占用一个箱子，若设其占用的箱子数为x 同时剩余物 体仍满足h f f d s ( l ) - 1 7 4 0 p t ( l ) + 5 显然s ( l ) + x l 3 ，可以判断) ( 4 ，x 5 集合为空。 现考察对l 的最优排法中的任一个箱子b ，沿x ，1 一x 高度划分2 条水平线， 沿x ， 1 一x 宽度划分2 条竖直线，根据x 2 ，x 3 中物体的短边长度可知，x 2 ，x 3 中的任一物体都至少被一条水平线及竖直线划中，如图假设a ，b 属于集合x 2 ， c ，d 属于集合x 3 根据引理1 在x 水平上w ( a ) + w ( b ) 1 ，所以w ( a ) + w ( b ) 1 7 1 0 在1 一x 水平上w ( c ) + w ( d ) 1 ，所以w ( c ) + w ( d ) 1 7 1 0 在x 宽度上h ( c ) + h ( a ) 1 ，所以h ( c ) + h ( a ) 1 7 1 0 在1 一x 宽度上h ( b ) + h ( d ) 1 ，所阻h ( b ) + h ( d ) 1 7 1 0 对这4 条线进行加总，得到 ( w ( a ) + h ( a ) ) + ( w ( b ) + h ( b ) ) + ( w ( c ) + h ( c ) ) + ( w ( d ) + h ( d ) ) 4 t 1 7 1 0 对所有的o p t ( l ) 个箱子数进行加总，得 在水平的两条线上w ( x 2 ) + w ( x 3 ) 2 t 1 7 1 0 0 p t ( l ) 在竖直的两条线上h ( x 2 ) + h ( x 3 ) 2 + 1 7 1 0 0 p t ( l ) 故在最优排法中 w ( x 2 ) + w ( x 3 ) + h ( x 2 ) + h ( x 3 ) - - w ( x 2 u x 3 a ) 2 ( n 2 + n 3 ) 一2 综合考虑h f f d s 排法与最优排法，下式成立： w ( x 2 ) + w ( x 3 ) ( 在h f f d s 排法中) w ( x 2 ) +