一维装箱问题的交叉算法分析.docVIP

一维装箱问题的交叉算法分析 李杉林 (台州学院 数学与信息工程学院，浙江 临海 317000） 摘 要：2004 年孙春玲等研究了一维装箱问题，给出了一个近似程度最好的近似值为 3 的近似算法 - 交叉算法. 2 遗憾的是他们的交叉算法的近似值分析是错误的，本文通过两个反例说明了他们的错误所在，并给出一个正确的 近似值分析. 关键词：装箱问题；强 NP-难；近似算法；反例 中图分类号：O233 文献标识码：A 文章编号：1672-3708（2009）03-0001-05 引言 一维装箱问题(Bin-Packing)是一个著名的难的组合问题.由于它有极其广泛的应用背景，得到了深 入细致的研究，取得了许多好的成果.Garey 和 Johnson(1979，[1])证明了一维装箱问题是一个强 NP-难问 题.也就是说，要对它寻求一种有效的（即多项式的）算法是不可能的，只能去探讨某种好的近似算法. 1 Bramel和 Simchi-Levi(1997，[2])指出：如果 P≠NP，那么对于任意给定的 ε＞0，不存在近似值为 3 -ε 的 2 近似算法来解决一维装箱问题.因此，这个 3 近似值是对装箱问题的近似算法的最好期待.目前，较为经 2 典和成熟的近似 算 法 有 NF (Next Fit) 算 法 、FF (First Fit) 算 法 、BF (Best Fit) 算 法 、FFD (First Fit Decreasing)算法等.NF(Next Fit)算法的近似值为 2(Johnson，et al.，1974，[3])；FF(First Fit)算法的渐近 近似值为 17 L*(即 FF(L) 17 L*+1， L)(Galambos 和 Wocgingcr，1995，[4])；BF(Best Fit)算法的渐近近似 10 10 值也为 17 L*（Galambos 和 Wocgingcr，1995，[4]）；FFD(First Fit Decreasing)算法具有最好的近似值 3 10 2 （simchi-levi，1994，[5]）和较好的渐近近似值 11 L*（即 FFD(L)≤ 11 L*+1， L)(越民义，1991，[6])，其中 L 为 9 9 物件列，L* 为最优箱子数目. 2004 年孙春玲等[7]对一维装箱问题也给出一个新的近似算法，称作交叉算法（简记为 CF 算法）.证明 了 CF 算法达到一维装箱问题的最好的近似值 3 ，而且该算法的时间复杂性为 O(n\logn)，也是非常理想 2 的.应该算作装箱问题的一个好的近似算法.稍感遗憾的是，虽然他们的结论是好的，也是对的，但他们在 证明的过程中出现了错误.本文下面的反例将说明他们的分析是不对的，并重新给出一个证明. 2 CF 算法和近似值证明 收稿日期：2008-09-24 作??简介：李杉林（1956- ），山西太原人，硕士，副教授，主要最优化理论及应用研究。 一维装箱问题指的是：任给一个表示 n 个物件的序列 L={a1，a2，…，an}，每个物件的大小为 s(ai)∈(0， 1]，以及充分多个容量为 1 的箱子.寻找某种方案，将物件 a1，a2，…，an 放入上述某些箱子中，使得所用箱 子数目最少. CF 算法 step1:把物件 L={a1，a2，…，an}按其大小进行非增序排列，不妨设 s(a1)≥s(a2)≥…≥s(an). step2:首先把 a1 放入箱子 B1 中，然后从最右端开始，依次把物件 an，an-1…放入 B1，直到下一个物件不 能再放入箱子为止，开启新的箱子 B2. step3:设在第 i 步循环时，打开第 i 个箱子，此时把物件 ai 放入 Bi 中.假设第 i-1 个箱子 Bi-1 中最后一 个放入的物件为 ak，则在 i 步循环时最右端的物件为 ak-1，那么当 s(ai)+s(ak-1)+…+s(al)≤1，且 s(ai)+s(ak-1) +…+s(al)+s(al-1)1 时，把 ak-1，ak-2，…，al 放入 Bi 中，开启新的箱子 Bi+1.直到把物件 a1，a2，…，an 放入 m 个 箱子. step4：输出 m. 称输出 m 为由 CF 算法得到的解，记作 CF(L).由最优装箱方案 I 得到的箱子数称作最优解，记作 L*. 令 Bi 表示由 CF 算法得到的 m 个箱子中的第 i 个箱子；σ（Bi）表示箱子 Bi 中所有物件的数目；f（Bi）表示 装入箱子 Bi 中的所有物件的大小之和.孙春玲等的算法分析是通过下面的引理和定理给出的. 引理 1 由 CF 算法得到的 m 个箱子中，若至少存在 m-1 个箱子，每个箱子中的物件数目不少于 2， 则这 m-1 个箱子中的任何一个箱