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

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

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

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