装箱问题近似算法的并行化
  张   蕾     SA02011130  
  摘要：装箱问题（bin   packing   problem）是一个著名的NP难解问题，其在工业生产及日常生活中有广泛的用途。本文首先对装箱问题进行了简要的介绍，然后介绍了两种一维装箱问题的近似算法并讨论了其相应的并行化算法，即下次适应算法及其并行化算法和调和装箱算法极其并行化算法。  
  关键词：装箱问题       并行算法     近似算法  
   
  1．引言  
        装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以装箱问题有着广泛的应用背景，具有很大的研究价值。（在生产管理细排产中，也有用处 ）  
        装箱问题是经典的NP难解问题，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P≠NP）。因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，如下次适应（Next   Fit）、首次适应（First   Fit）、最佳适应（Best   Fit）、调和（Harmonic-K）算法等。这些串行算法已经具有了比较好的性能，表1给出了这些研究成果的三种重要性能指标，装箱问题近似算法的三个评价标准是最坏情况性能比，平均情况性能比（如非特别指出，一般是指当输入物品满足(0,1]均匀分布情况下的平均性能），时间、空间复杂度。Coffman等从这三个主要标准出发对众多目前已经提出的算法进行了很好的评价[2]，下面列出其中一部分。   
表1   一些著名的经典装箱问题近似算法

  首次适应算法(FF) 在线 O(nlogn) 1.7 1  
  最佳适应算法(BF) 在线 O(nlogn) 1.7 1  
  调和算法(HK) 在线 O(n) 1.69103… 与K相关  
  改进的调和算法(RH) 在线 O(n) ≤1.63596… 与K相关  
  Next   Fit-K(NFK) 在线 O(n) 1.7+0.3/(K-1) 与K相关  
  AFBK 在线 O(n) 1.7+0.3/(K-1) 与K相关  
  K-Bounded   Best   Fit(BBFK) 在线 O(n) 1.7 与K相关  
  ABFK 在线 O(n) 1.7+0.3/K 与K相关  
  降序首次适应算法(FFD) 离线 O(nlogn) 11/9 1  
  降序最佳适应算法(BFD) 离线 O(nlogn) 11/9 1   
   
        装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题所与生俱来的复杂性，虽然已经有一些研究成果发表了，但是其研究还是相当的困难。本文所讨论的还是一维装箱问题。  
   
  2．部分相关知识  
  在研究装箱问题的并行化之前，我们先来了解一下一些相关的知识。  
  2．1   在线算法、离线算法与半在线算法  
        在线算法：如果一个近似装箱算法在执行过程中，每当一个物品到达时，就立刻决定把该物品放入哪个箱子中，而不管后序物品如何，这种算法就被称为在线算法。

        下次适应算法、首次适应算法、K-调和算法等等都是在线算法，其时间复杂度都为O(n)，但下次适应算法的最坏情况性能比较高（为2），而K-调和算法对此有较大改善（为1.6910)。   
      离线算法：如果算法在开始装箱之前，已经预先得到了所有物品的信息而一次性的确定装箱策略，这种算法就被称为离线算法。

      降序首次适应算法和降序最佳适应算法是两个重要的离线算法，它们首先对所有物品按照物品大小的降序排序，然后对这个排序后的物品序列分别应用在线算法中的首次适应、最佳适应策略。由于离线算法预先知道所有物品的信息，因此算法的性能一定远远优于在线算法。   
      半在线算法：与在线算法相同它不要求预先知道所有的物品信息，物品一到达，立刻决定把该物品放入哪个箱子中，与在线算法的区别在于它每次处理当前物品的时候允许对前面已经完成装箱的物品做有限的调整（比如常数个物品的调准）。   
  2．2 适应算法 

          适应算法(Any   Fit   Algorithm)：当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被称为适应算法。下次适应算法、首次适应算法、最佳适应算法、最坏适应算法和几乎最坏适应算法是几个著名的适应算法。适应算法的最坏情况性能比被证明一定处于[1.7,2]范围内，即在最坏情况性能上不可能优于首次适应算法。  

'=================================================  
  'CBoxs.cls  
  '=================================================  
  Private   m_Boxes()   As   CBox  
  Public   Property   Let   NewBox(value   As   CBox)  
          ReDim   Preserve   m_Boxes(UBound(m_Boxes)   +   1)   As   CBox  
          Set   m_Boxes(UBound(m_Boxes))   =   value  
  End   Property  
   
  Public   Property   Get   LeftContains(ByVal   Index   As   Long)   As   Long  
          Dim   i   As   Long  
          Dim   pBox   As   CBox  
           
          For   i   =   Index   +   1   To   UBound(m_Boxes)  
                  Set   pBox   =   m_Boxes(i)  
                  LeftContains   =   LeftContains   +   pBox.nMax   *   pBox.nNum  
          Next   i  
  End   Property  
   
  Public   Function   Div(ByVal   nBall   As   Long)   As   String  
          Dim   i                       As   Long  
          Dim   dNum                 As   Double  
          Dim   nDivBall         As   Long  
           
          nDivBall   =   nBall  
          'check   if   has   enough   space  
          If   LeftContains(0)   <   nDivBall   Then  
                  Div   =   "the   ball   number   larger   than   all   boxes'   space   "  
                  Exit   Function  
          End   If  
           
          For   i   =   1   To   UBound(m_Boxes)  
                  If   m_Boxes(i).nMax   *   m_Boxes(i).nNum   >=   nDivBall   Then  
                           
                          dNum   =   ndivall   /   Format(m_Boxes(i).nMax,   "#.0000")  
                          dNum   =   CLng(dNum)   +   IIf(CLng(dNum)   -   num   =   0,   0,   1)  
                          If   dNum   =   0   Then   dNum   =   1  
                           
                          Div   =   Div   &   "Type:"   &   m_Boxes(i).nMax   &   "----"   &   dNum   &   vbCrLf  
                          Exit   Function  
                           
                  Else  
                          Div   =   Div   &   "Type:"   &   m_Boxes(i).nMax   &   "----"   &   m_Boxes(i).nNum   &   vbCrLf  
                          nDivBall   =   nDivBall   -   m_Boxes(i).nMax   *   m_Boxes(i).nNum  
                  End   If  
          Next   i  
           
  End   Function  
   
  Private   Sub   Class_Initialize()  
          ReDim   m_Boxes(0)   As   CBox  
  End   Sub  

'========================================  
  'CBox.cls  
  '========================================  
  Public   nMax   As   Long   '   max   contain   number  
  Public   nNum   As   Long   'number   of   these   boxes   
 

'=======================  
  'Form1.frm  
  '========================  
  Private   Sub   Command1_Click()  
           
          Dim   nBall  
          Dim   pBox   As   CBox  
          Dim   objBoxs   As   New   CBoxs  
           
          Set   pBox   =   New   CBox  
          pBox.nMax   =   200  
          pBox.nNum   =   1  
           
          objBoxs.NewBox   =   pBox  
           
          Set   pBox   =   New   CBox  
          pBox.nMax   =   150  
          pBox.nNum   =   1  
          objBoxs.NewBox   =   pBox  
           
          Set   pBox   =   New   CBox  
          pBox.nMax   =   100  
          pBox.nNum   =   1  
          objBoxs.NewBox   =   pBox  
           
          Set   pBox   =   New   CBox  
          pBox.nMax   =   80  
          pBox.nNum   =   1  
          objBoxs.NewBox   =   pBox  
             
          nBall   =   440  
           
          MsgBox   objBoxs.Div(nBall)  
           
  End   Sub  

 

用递归的办法遍历所有装箱可能，然后找出用箱子最少并且剩余空间最小的方案。关键看着两个条件的优先级哪个高。比如说360个球，最少箱子的方案是两个200的箱子，最少浪费空间的方案是一个200的两个80的。  
  我下面给出的代码是以最少箱子的优先级更高  
   
  'LeftBall:剩余未装箱球的数量，第一次传入球的总数  
  'arybox:     传入箱子数组  
  'begin:       第一次传入的标志，第一次传入true  
  'BoxSel:     递归过程中传递的参数，不必传入  
  Private   Function   test(ByVal   LeftBall   As   Integer,   ByVal   arybox   As   Variant,   begin   As   Boolean,   Optional   ByVal   BoxSel   As   String)   As   String  
   
          Static   BestSel   As   String  
          Static   BestSpaceLeft   As   Integer  
          Static   BestCount   As   Integer  
           
          Dim   i   As   Integer  
          Dim   tmpLeftBall   As   Integer  
          Dim   tmpBoxSel   As   String  
          Dim   tmpCount   As   Integer  
           
          If   begin   Then  
                  BestSel   =   ""  
                  BestSpaceLeft   =   400  
                  BestCount   =   100  
          End   If  
           
          For   i   =   LBound(arybox)   To   UBound(arybox)  
                  DoEvents  
                  tmpLeftBall   =   LeftBall   -   arybox(i)  
                  tmpBoxSel   =   BoxSel   &   i   &   "   "  
                  If   tmpLeftBall   <=   0   Then  
                          tmpCount   =   Len(tmpBoxSel)   /   2  
                          If   tmpCount   <=   BestCount   Then  
                                  If   Abs(tmpLeftBall)   <=   BestSpaceLeft   Then  
                                          BestSpaceLeft   =   Abs(tmpLeftBall)  
                                          BestSel   =   tmpBoxSel  
                                          BestCount   =   tmpCount  
                                  End   If  
                          End   If  
                          'Debug.Print   tmpBoxSel  
                  Else  
                          Call   test(tmpLeftBall,   arybox,   False,   tmpBoxSel)  
                  End   If  
          Next  
          test   =   BestSel  
  End   Function  
   
  调用举例：  
  Dim   arybox(1   To   4)   As   Integer  
   
  arybox(1)   =   200  
  arybox(2)   =   150  
  arybox(3)   =   100  
  arybox(4)   =   80  
   
  Debug.Print   test(440,   arybox,   True)  
  Debug.Print   test(360,   arybox,   True)  
  Debug.Print   test(501,   arybox,   True)  
   
  输出：  
  3   2   1    
  1   1    
  2   1   1    
   
  440个球3号箱子用一个2号箱子用一个1号箱子用一个  
  360个球1号箱子用两个  
  501个球2号一个一号两个，剩余空间49