计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 55-59.doi: 10.11896/j.issn.1002-137X.2014.08.011
• 2013年全国理论计算机科学学术年会 • 上一篇 下一篇
何琨,姚鹏程,李立文
HE Kun,YAO Peng-cheng and LI Li-wen
摘要: 对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法。
[1] Gehring H,Bortfeldt A.A parallel genetic algorithm for solving the container loading problem [J].International Transactions in Operational Research,2002,9(4):497-511 [2] Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem [J].European Journal of Operational Research,2001,131(1):143-161 [3] Bortfeldt A,Gehring H.A tabu search algorithm for weaklyheterogeneous container loading problems[J].0R Spectrum,1998,20(4):237-250 [4] 张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法[J].计算机学报,2009,32(11):2147-2156 [5] He Kun,Huang Wen-qi.An efficient placement heuristic forthree-dimensional rectangular packing[J].Computers & Operations Research,2011,38(1):227-233 [6] 何琨,黄文奇.三维矩形Packing问题的拟人求解算法[J].中国科学(F辑),2010,40(12):1586-1595 [7] Ford L R,Fulkerson D R.Maximal flow through a network [J].Canadian Journal of Mathematics,1956,8:399-404 [8] Andrew V G,Robert E T.A new approach to the maximum flow problem [J].Journal of the ACM,1988,35(4):921-940 [9] Prüfer H.Neuer Beweis eines Satzes über Permutationen [J].Archiv für.Mathematik und Physik,1918,27:742-744 |
No related articles found! |
|