计算机科学 ›› 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! |
|
||
首页