经典一维装箱问题的适应近似算法的研究摘要本文研究经典一维装箱问题（Bin Packing Problem）及其适应近似算法，给出了一个新的适应近似算法：交叉装填算法（简称CF算法），而且证明了当这些物件大小按非增性预先排序后，CF算法时间复杂度是线性的；通过具体例子说明交叉装填算法优于其它适应近似算法，并且推断CF算法达到装箱问题的最好近似值32。

关键词：一维装箱问题，近似算法，适应算法，交叉装填算法ABSTRACTIn this paper the Bin-Packing problems and any-fit approximation algorithm are studied. We give a new any-fit approximation algorithm (Cross Fit Approximation Algorithm) in O(nlogn)steps. In addition, if the sizes of all objects decreasing according to their sizes, Theany-fit approximation algorithm runs in O(n)steps. This paper proved the cross fit approximation algorithm’s capability excelled other any-fit approximation algorithm’s by someexample,and extrapolate the new any-fit algorithm is a 32-approximation algorithm.Key Words：Pin Packing Problem，Approximation Algorithm，Any-fit Algorithm，Cross Any-fit Algorithm.1． 引言1．1 问题的提出装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品体积之和不超过箱子容量并使所用的箱子数目最少。

其应用在实际生活中无处不在，货物装运，服装裁剪，以及计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。

例如某国际物流公司有一批固体货物要装进集装箱用船从广州运到美国。

每个集装箱的规格都一样（体积均为150立方米），而每件货物体积不一定相同但其长宽高都小于集装箱的。

问怎样的装箱方案最省钱，即所用集装箱最少？研究装箱问题能够更好解决上述这些问题，有很大的经济效益。

所以装箱问题有着广泛的应用背景，具有很大的研究价值。

但是装箱问题是NP 难解问题[7]，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P ≠NP ）因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。

目前，已经提出了大量的近似算法，其中适应近似算法是目前时间复杂性比较低的一种近似算法。

如下次适应（NF ）算法、首次适应（FF ）算法、最佳适应（BF ）算法、降序首次适应(FFD)算法、降序最佳适应(BFD)算法等。

装箱问题中最早被研究的是一维装箱问题。

随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。

但是由于这些问题的NP 困难性，虽然已经有一些研究成果，但是还有很许多未解问题,甚至一些是一维装箱问题[5]。

一维装箱问题是指要求把一些物品放入到具有固定容量的箱子中，并最小化所使用的箱子数目。

本文所讨论的是一维装箱问题。

1．2 相关知识在研究一维装箱问题的适应近似算法之前，我们先来了解一下一些相关的知识。

1．2．1近似算法的定义一个组合最优化问题π是一个最小化或最大化的问题,由三部分组成:实例的集合f π;∀I ∈f π,有一个有限的可行解集合()F I π;有一个目标函数g π,使得∀I ∈f π及σ∈()F I π,赋予一个正有理数g π(I, σ),称为σ的目标值.对于最小(大)化问题,称*σ∈()F I π为I ∈f π的最优值是指σ∈()F I π,恒有**(,)(,)((,)(,)).g I g I g I g I ππππσσσσ≤≥最优解*σ的目标值*(,)g I πσ成为I 的最优值,记作OPT (I)π,当这个问题明确时通常省略下标π.定义1 称算法A 是π的一个近似算法(Approximation Algorithm)是指: ∀I ∈f π,应用算法A 总可以找出I 的一个可行解σ∈()F I π.对应的解的目标值(,)g I πσ记作()I A ,表示由算法A 得到的I 的目标值.若∀I ∈f π,都有()I A =OPT(I)，则称A 是π的最优算法(Optimization Algorithm)。

1．2．2适应算法定义2 适应算法(Any Fit Algorithm)：适应算法是解装箱问题的一个近似算法。

当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被称为适应算法。

其中下次适应算法、首次适应算法、最佳适应算法、最坏适应算法和几乎最坏适应算法是几个著名的适应算法。

适应算法的最坏情况性能比被证明一定处于[1.7,2]范围内，即在最坏情况性能上不可能优于首次适应算法[2]。

1．2．3经典一维装箱问题在经典一维装箱问题中，处理对象是n 个输入物品的序列和一个无限多的等容量箱子序列；目标是把所有物品放入箱子中并最小化所使用的箱子数目。

可以对其做如下定义： 经典一维装箱问题：给定n 个物品的序列L n =（a 1,a 2,…,a n ），物品a i （1≤i ≤n ）的大小s (a i ) ∈(0,1]，要求将这些物品装入最小数量的单位容量的箱子中。

例如，把a i （1≤i ≤n ）分别放入箱子序列B 1,B 2,…,B m 中，使得每个箱子中的物品大小之和不超过1，即∑∈j i B a s (a i )≤1，1≤j ≤m ，且使所用的箱子数目m 最小。

2． 经典一维装箱问题的适应近似算法近似算法并不保证给出最优解,那么应当如何来评价近似算法的好坏呢?主要基于两个方面的考虑.首先是时间复杂性方面的要求,即要求有一个多项式时间界;其次是性能方面的要求,即希望所求得的近似解尽可能地“接近”最优解.可以从不同的角度来评价近似算法性能,大体可以分为三类:第一类是以算法在最坏情况下的行为标准，研究算法得到最优解的接近程度，越接近越好；第二类是以算法的平均行为为标准研究得到最优解的概率；第三类是局部搜索算法，寻找局部最优解，这种算法有时很好，有时很坏，只能通过实践加以评定。

本文所讨论的是第一种类型。

为了更好地从性能方面来讨论近似算法，我们给出度量近似算法性能的两个指标。

设π是一个最小（大）化问题，I 是π的实例。

设A 是π的一个近似算法，由A 得到的目标值为A （I ），而I 的最优目标值为OPT （I ），记()()()A A I R I OPT I =（()()()A OPT I R I A I =）,定义3 π的近似算法A 的绝对性能比（absolute performance ratio ）记为 {}i n f (),A A R r R I r I f π=≤∀∈， 定义4 π的近似算法A 的渐近性能比（asymptotic performance ratio ）记为{}i n f ,I r AA R r n OPT n R ∞*=∃∈∀≥≤的实例，有N ，其中{}*=全体非零自然数N 。

AR ∞又称为近似算法A 的近似值。

我们分析装箱问题的近似算法的性能包括两个主要内容[2]： （1）建立近似算法在最坏情况下所得目标值的一个界；（2）构造实例说明得到的界可以达到或渐近达到，从而说明这个界已经相当好了。

首先我们用下面的经典结果说明一维装箱求解的困难程度。

引理1[1] 如果P NP ≠，那么对于任意给定的0ε>，不存在近似值为32ε-的近似算法来解决一维装箱问题。

因此这个32近似值是我们对一维装箱问题的近似算法的最好期待，事实上，很多近似算法的近似值都是朝这个目标迈进[3]。

本文给出的算法也是朝这个目标前进。

2．1已知的常用适应近似算法[2][3][4] 2．1．1 NF(Next Fit)近似算法该算法的做法是随到随装,装不下就封箱运走.将n 个物品12,,n s s s 依次装箱,设12,,i s s s 已装入1B 箱,且1211()i i a a a a +-+++< 即1i s +不能装入1B 箱,则1B 箱虽未装满也装箱送走, 1i s +装入下一个箱子2B ,……这种装箱方法适合流水作业,其时间复杂性为O(n)。

定理1[2] 对装箱问题的何实例I ，均有()2()1NF I OPT I ≤- （2.1）例1 设物品集{}124,,,m s s s s = ，各物品得体积为121.2i i a i m⎧⎪⎪=⎨⎪⎪⎩，为奇数，，为偶数 对这个实例I ，易知OPT （I ）＝m+1，而NF （I ）＝2m ，从而()22()()1N F I mm O P T I m =→→∞+由定理1和例1，我们有 推论2[2]2NF R =. (2.2)2．1．2 FF （First Fit ）近似算法这是一种较为直观的、容易想到的装箱方法，其基本思想是将n 个物品12,,,n s s s 顺次装箱，设装箱的次序是12,,B B ；对某一物i s ，它总是被装到第一个能装下它的箱子中，也就是说物品i s 被装到已装进的物品的体积不超过1i a -的下标最小的箱子中。

这种装箱办法虽然不要求n 个物品全部到达后再装箱，但要求所有箱子都装好后一起送走，可以说适合半流水线作业。

由于每个物品i s 装箱时都必须从1B 开始顺次查看各个箱子是否能装下它，故FF 算法的时间复杂性为2()O n 。

关于FF 算近似法的性能我们有如下结果：定理3[3] 对装箱问题的任何实例I ，均有 17()()110FF I OPT I ≤+， （2.3）并且，存在实例I ，使得()OPT I 充分大且满足 17()(()1)10FF I OPT I ≥-， 从而1710FFR ∞=。

公式（2..3给出了FF 近似算法在最坏情况下所得到的目标值的界，反映了近似解“接近”最优解的程度。

下面用FF 算法计算一个例子所需的箱子数目。