装箱问题的一种新的近似算法

维普资讯 http://www.77cn.com.cn

云南大学学报 (然科学版 ) 04 6 () 9￣36自，20,2 5:3 2 9J u n l fYu n n Unv riy o r a n a iest o

CN 3— 1 4/ 5 0 5 N I S 0 5 S N 2 8—7 7 9 1

装箱问题的一种新的近似算法。孙春玲，陈智斌，李建平(云南大学数学系，云南昆明 60 9 ) 5 0 1

摘要：研究了一维装箱问题 ( i Pci r l。出了一个新的近似算法： Bn ak gPo e给 n b m)交叉装填算法 (简称 (算

法.明 (算达装问的好近值；且这物的小非性预排后c算 )了法到箱题最的似导并当些件大按增质先序， 证 F法的时间复杂度是线性的 .

关键词：一维装箱问题； P一完备； N近似算法中图分类号： 5 .; 0 . 0 1 7 6 TP 3 1 5文献标识码： A文章编号：2 8 9 1 2 0 )5—0 9 0 5—7 7 (0 4 0 3 2—0 5

在7 0年代初期 N P一完备性刚建立时，一维的装箱问题 ( i P c i rbe就得到广泛研 Bn ak gP o l n m)究，取得许多好的成果 .同时因为 P NP的著≠名猜想，解决一维装箱问题的一些好的算法一直以

定理 13如果 P≠ NP,么对于任意给定 1 J那0

的 e> 0不存在近似值为一 e,的近似算法来解二

决一维装箱问题 . 因此，这个近似值是我们对装箱问题的近

来都被作为近似算法的经典范例，其原因不仅因为对一维装箱问题的研究能提供人们一个学习、熟悉、至应用近似算法的基础 .且还因为一维装甚而

似算法的最好期待、实上，们得到的很多近似事人算法的近似值都是朝这个目标迈进[本文给出 2. 2]的算法已经解决了这个问题 .在下面的证明过程中0

箱问题有着极其广泛的应用背景、例如有装载量限制的装载卡车问题及库存削减问题等、 下面给出一维装箱问题的数学描述： 任意给定的一个序列 L= ( 1a, n )表 a, 2…, ,

可以看到算法能达到最优的近似值，同时算法的复杂度也能达到非线性最优 O( l n . n g )特别. o当物件的大d (i )非增性质预先排序后. F法

￣s e按 z C算,’

示 n个物件，每个物件的大小 S a) (,] ( ∈ 0 1,其中 i= 12…,l此处有一些容量为 1的箱子，,,, (i )一维的装箱问题要求给出一种方案，物 bn . s把件 a, 2…,全部放人上述容量为 1的某些箱 1a, a子中，使得所用箱子数目最少 . 由于一维装箱问题是 N P一完备的… . 1在历史上产生很多装箱问题的近似算法，为经典的算较法有 Net i NF和 Fr—FtF )NF x—Ft ) ( i t i F .算法能 s (获得 NF L)≤ 2 ( OPT( L)一 1的结果，这里

能够在线性时间内找到近似解，近似值为 .其我

们给出的算法的主要思想是：先把物件按从大到小的顺序排列，然后首先把左端最大的一个物件放人一

个箱子，再从物件序列的最右端开始从右往左依

次把物件放人箱子中，直到下一个物件不能放人该箱子，么开启新的箱子，那重复上述装填步骤，到直所有的物件都装入箱子中.

0 T L是最优的箱子数目， F P ( )而 F算法能取得 2 的近似值[I 2. 对一维装箱问题有下面的经典结果来说明其困难程度 .收稿日期：0 3 2 2 20—1— 4

1主要结果为了叙述方便，首先给出一些概念与符号 .令L= ( 1 a, a )为任意给定的 n个物件的一 a, 2…,

基金项目：家自然科学研究基金资助项目(07 13;南省自然科学研究基金资助项目(0 3 0 1M)国 12 10 )云 20 F 0 5 作者简介：春玲 (90 )女，南人，孙 18一，云硕士生，主要从事组合优化方面的研究 . 李建平 (95 )男，南人， 16一，云教授 .主要从事组合优化方面的研究 .

维普资讯 http://www.77cn.com.cn

第5期

孙春玲等：装箱问题的一种新的近似算法

33 9

个序列 .个物件的大小 sa)∈ (,]其中 i 每 ( 0 1,∈{,, n, 12…,} B表示所用的第 j个箱子，箱子 B的 容量(也称长度 )为 1∈{,, m}这里 m均 . 1 2…,,.

输出：需要的箱子数目 m. se:物件 a, 2…,按其大小进行非增序 t 1把 p ln, n排列，妨设为 sa ) sa )…≥ sa)不 ( 1≥ ( 2≥ ( .

s p2首先把 a放入箱子 B】然后从最右端开 t: e】中，始，依次把物件 a, ,放入 B, a… 1直到下一个物件不能再放入箱子为止，开启新的箱子 B . 2 s p3设在第 i循环时， t: e步打开第 i个箱子，此时把物件 a放入 B中， 再从最右端开始从右往左把物

表示一种给定的装箱方案所需的箱子数目.知，易 不同算法产生的箱子数目不必相同.令 ( i表示 B)箱子中所有物件的数目., B )令 ( 表示装入箱子 B中的所有物件的大小之和 . i表示按照算法 i a放入第 j箱子的第是个物件，中 j∈{,, 个其 12…, m} .因此我们有 f )= (

件依次放入 B中.设第 i个箱子一中最后 假一1一

个放入的物件为 a,在第 i则步循环时最右端的

竺t=1

物件为 a_I么当 s a)+ sa一)+…+ s a) l那 ( ( 1 (￡ a, j j= 12…, ),, m,≤ 1且 s a) s a一)…+ s a) s a一)>, ( + ( k1+ (￡+ (￡1

∑fB=∑ s (j ) () n.下面给出装箱问题的交叉装填算法：

1把 a一， 2…,￡时， k1 a一， a放入中，开启新的箱子+ 1.

直到把物件 a, 2…, 1 a, a放入 m个箱子 .

s p4输出 m. t: e 为了便于更好的理解算法，我们利用 C F算法

算法 1交叉装填算法( F算法 ) c 输入：= ( 1 a,, L a, 2… a )及每个物件的大小 sa) (,] i 12…, . (∈ 0 1,=,, n

来计算下面一个例子所需要的箱子数目.

例=专 e,+,+,号 e+,吉 e 1L (+,专 e e,+, e,+)…号…吉…

6N n bi s O PT=6 N

4 b ns N i

2N ns bi

胃1 bi s N n ’椰^

使，B≤,B≤, ij m 得f i号，j号1<≤ . () ()≤则B中所装物件为口，{…, j, i所装物件 in, n B中l 2 ‘(B )口

为 a.a, a )这里 n和 a, j j…, j,,:椰 i j是∈{,, 12…,

( ), {,, ( )分别为第是 }是∈ 12…, }个和第

玎7 7= N

是个

装入 B和马中的物件. i按算法顺序 n,

分别为最后一个装入 B和和中的物件 . i

由假设知

2算法分析下面讨论 C F算法的近似值及时间复杂性 .为

, B )= s nI s n2…+ (i ({ )+ ( i )+

s‘) j, ( () B≤专, ) ( s )+ s:…+ ( ( )+

( 1 )() 2

了证明 c F算法是一维装箱问题的一个詈一近似算法，我们首先给出引理 1:

引理 1由 C F算法得到的 m个箱子中，若至少存在 m一1个箱子，每个箱子中的物件数目不少于 2即 d B ) 2 j{,, m}, ( i≥,∈ 12…,则这 7—1 7 1个箱子中的任何一个箱子所装的物件容量之和大于3‘

sq ) T (删≤ -,且由算法知以下性质成立s n:≤ s a )…≤ s n ) ( ) (i≤ (≤ 3 sn ( s a) ( i,

() 3

s:≤ s )…≤ s 8) ( ) (≤ ( l≤】

证明若不然，不妨设存在 2箱子 B和 B个 i

s )= s ) ( (,.

() 4

维普资讯 http://www.77cn.com.cn

34 9

云南大学学报 (自然科学版 )

第 2卷 6

又因为 i< j所以， sa≥ s ) (i ) (, 并且 sn≤…≤ sn ( ) ( ) s a≤ (j )≤…≤ s ( ) s )≤ s n ) ( )≤ ( ( . 6 ,

2那么 c, F算法是一维装箱问题的一个一近似算() 5法.

证明设 C F算法的输出值为 m,其问题本身的最优值为 O T,由假设及引理 1知若至少有 P m一1个箱子，每个箱子中的物件数目不少于 2那，么其所装的物件容量之和大于，则存在 m∈ {,, m}使得对任意的 j∈{,,o 12…,, 12 o om

现在考虑 …… 此处隐藏：8183字，全部文档内容请下载后查看。喜欢就下载吧 ……