等球Packing問題的啟發(fā)式研究.pdf

1、在回顧了球(圓)形Packing問題的研究現(xiàn)狀后,指出此類問題是NP-hard問題,迄今不存在確定型的求解算法。啟發(fā)式算法是求解此類問題的有效途徑。
　　為處理等球Packing問題,本文介紹了擬物模型以及基本擬物算法,并在基本擬物算法上做出三項改進:偽球策略用于保證可行解的精確性;快退策略用于削減不必要的計算時間;鄰居球策略把物體對間距離的計算時間復雜度從O(n2)降低到O(n),其中n是等球數(shù)目。包含了這三項改進的擬物算法是本

2、文的局部優(yōu)化器,記為A0。給定了初始構型的算法 A0是一個確定型算法。
　　然后,本文設計了序列對稱換位策略作為主要的全局搜索策略。將這一策略與局部優(yōu)化器A0結合,得到復合算法A1。此外又設計了抖動下落策略作為輔助搜索策略,把抖動下落策略應用于A1,得到復合算法A2。
　　算法A1和A2都是從隨機初始構型出發(fā),用序列對稱換位策略生成O(n2)個新構型,調用A0依次局部優(yōu)化它們,從中取出最緊湊者作為搜索結果。因為A1和A2每次

3、計算只檢查O(n2)個構型,故而可以處理比較大的算例。
　　本文使用算法A2在立方體容器內和球形容器內各裝填了多達200個等球。對立方體內裝填1到200個等球的算例,A2貢獻了當前世界最好記錄中65項。對球形容器內裝填1到200個等球的算例,A2在前72個算例中貢獻了25項當前世界最好記錄,而其余算例上的結果大多是由A2新發(fā)現(xiàn)的。特別地,A2成功地把68個半徑為1的等球裝入了半徑小于5的大球中,證否了以前的一個猜想,即半徑為5的大