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

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

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

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