一維裝箱問題畢業(yè)論文

1、<p><b>　　摘 要</b></p><p>　　一維裝箱問題來(lái)源于人們的長(zhǎng)期以來(lái)的生產(chǎn)實(shí)踐，是一種組合優(yōu)化問題。給定有窮個(gè)物體，每個(gè)物體的重量是已知的正實(shí)數(shù)。給定足夠多個(gè)空箱子，問題是要在滿足兩個(gè)約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個(gè)數(shù)盡可能地少。兩個(gè)約束條件是：第一，每個(gè)物體均保持完整，恰好放到一個(gè)箱子中去。不能將物體分割成幾塊。第二，每個(gè)箱子中所放

2、的物體的重量之和均不能超過一個(gè)相同的上限，這個(gè)上限是一個(gè)已知的正實(shí)數(shù)。</p><p>　　一維裝箱問題具有很高的理論價(jià)值和實(shí)際價(jià)值。一方面，學(xué)者已經(jīng)證明一維裝箱問題是一個(gè)NP難度問題，因此一維裝箱問題具有很高的理論價(jià)值。另一方面，一維裝箱問題出現(xiàn)在實(shí)際生產(chǎn)的一些領(lǐng)域，因此也具有很高的實(shí)際價(jià)值。</p><p>　　迄今為止，國(guó)內(nèi)外學(xué)者提出了許多用來(lái)求解一維裝箱問題的嚴(yán)格算法和近似算法。一

3、方面，嚴(yán)格的最優(yōu)算法所花時(shí)間太長(zhǎng)，實(shí)際部門無(wú)法忍受。另一方面，近似算法由于可能快速地生成最優(yōu)解或者接近最優(yōu)解而為實(shí)際生產(chǎn)部門所廣泛采用。</p><p>　　人類把物體往容器中裝，已有幾千年以上的經(jīng)驗(yàn)。這些生活經(jīng)驗(yàn)可引導(dǎo)出高效率的算法。本文提出了一種擬人算法。算法由三個(gè)部分組成。第一部分是降序最佳適合算法，用于生成初始解。第二部分是鄰域搜索算法。給定一個(gè)解，用鄰域搜索算法可以通過迭代改進(jìn)這個(gè)解。本文的鄰域定義的思

4、想來(lái)源于“天之道損有余而補(bǔ)不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。跳坑策略的思想來(lái)源是“三十六計(jì)走為上”。</p><p>　　本文的程序計(jì)算了一組共17個(gè)國(guó)際公認(rèn)的問題實(shí)例。這組問題實(shí)例分為兩類。第一類為8個(gè)問題實(shí)例，目前尚未確定其客觀最優(yōu)解。第二類為9個(gè)問題實(shí)例，目前已經(jīng)確定了其客觀最優(yōu)解。擬人算法對(duì)第一類問題實(shí)例中的6個(gè)問題實(shí)例找出了與當(dāng)前已知最好

5、解質(zhì)量相同的解。擬人算法還證明了TEST0068這個(gè)問題實(shí)例的目前已知最好解正是客觀最優(yōu)解。擬人算法快速地找出了第二類問題實(shí)例中全部9個(gè)問題實(shí)例的客觀最優(yōu)解。</p><p>　　計(jì)算結(jié)果表明，擬人算法是一種有效的求解一維裝箱問題的近似算法。</p><p>　　關(guān)鍵詞： NP難度； 擬人； 鄰域搜索； 跳坑； 裝箱</p><p><b>　　Abstr

6、act</b></p><p>　　The one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin p

7、acking problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all it

8、ems into the bins with the objective of minimizing the number of occupied bins, subject to two f</p><p>　　The one dimensional bin packing problem is of both highly theoretical and practical values. On one ha

9、nd, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one dimensional bin packing problem appears in some real world factories.</p><p>　　So far, many exact algorit

10、hms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, approximation a

11、lgorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.</p><p>　　Mankind have more than several thousands of years of experience to pack items into containers. Th

12、e experience can induce efficient algorithm. A quasi-human algorithm is presented in this paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second

13、part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborhood comes from</p><p>　　Computational

14、experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The se

15、cond class consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algo

16、rithm proves that the best known solution for </p><p>　　The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.</p><p>　　Keywords:

17、 NP-hard; Quasi-human; Local search; Off-trap; Bin packing</p><p><b>　　目 錄</b></p><p><b>　　1 緒論1</b></p><p><b>　　1.1 引言1</b></p>&

18、lt;p>　　1.2 問題描述1</p><p>　　1.3 研究現(xiàn)狀2</p><p>　　1.4 本論文的主要結(jié)構(gòu)5</p><p><b>　　2 算法描述6</b></p><p>　　2.1 擬人算法的大致框架6</p><p>　　2.2 生成初始解7&l

19、t;/p><p>　　2.3 鄰域搜索7</p><p>　　2.4 跳坑策略9</p><p>　　3 程序設(shè)計(jì)11</p><p>　　3.1 程序流程11</p><p>　　3.1.1 讀取文本文件中的數(shù)據(jù)13</p><p>　　3.1.2 生成初始解13</

20、p><p>　　3.1.3 鄰域搜索14</p><p>　　3.1.4 釋放內(nèi)存15</p><p>　　3.2 調(diào)試程序15</p><p>　　4 計(jì)算結(jié)果16</p><p><b>　　5 結(jié)論18</b></p><p><b>　　參

21、考文獻(xiàn)19</b></p><p><b>　　致謝21</b></p><p><b>　　1 緒論</b></p><p><b>　　1.1 引言</b></p><p>　　當(dāng)前世界經(jīng)濟(jì)高速發(fā)展，人口日益增加，資源日漸緊張。人們?cè)谏a(chǎn)生活中希望提高效

22、率，節(jié)約資源，以實(shí)現(xiàn)可持續(xù)發(fā)展。在運(yùn)籌學(xué)領(lǐng)域有一類所謂最優(yōu)化問題。最優(yōu)化問題的一般形式是：在滿足約束條件的前提下，給出自變量的值，使得目標(biāo)函數(shù)值最優(yōu) (通常是使得目標(biāo)函數(shù)值最小或者最大)。</p><p>　　一維裝箱問題[1]來(lái)源于人們的長(zhǎng)期以來(lái)的生產(chǎn)實(shí)踐，是一種最優(yōu)化問題，一維裝箱問題具有很高的理論價(jià)值和實(shí)際價(jià)值。</p><p>　　一方面，學(xué)者已經(jīng)證明一維裝箱問題是一個(gè)NP難度問題

23、，因此一維裝箱問題具有很高的理論價(jià)值。在現(xiàn)實(shí)的工業(yè)、商業(yè)、交通、通信、軍事等領(lǐng)域出現(xiàn)了大量的所謂NP難度問題，例如車間調(diào)度問題、貨郎擔(dān)問題等等。人們雖然目前不能證明，但是強(qiáng)烈相信NP難度問題不存在時(shí)間復(fù)雜度為多項(xiàng)式的完整算法。所謂完整算法，對(duì)于優(yōu)化問題來(lái)說就是能保證找到最優(yōu)解的算法，對(duì)于判定問題來(lái)說就是能夠保證正確判定的算法。</p><p>　　另一方面，一維裝箱問題出現(xiàn)在實(shí)際生產(chǎn)的一些領(lǐng)域，因此也具有很高的實(shí)

24、際價(jià)值。</p><p>　　世界各國(guó)學(xué)者已經(jīng)對(duì)一維裝箱調(diào)度問題做了數(shù)十年的研究，人們還提出了許多種算法來(lái)求解一維裝箱調(diào)度問題。</p><p>　　另外，在現(xiàn)實(shí)中存在二維、三維、多維的裝箱問題。本文僅討論一維裝箱問題。</p><p><b>　　1.2 問題描述</b></p><p>　　本文研究的這種一維裝箱問

25、題的描述如下。給定有窮個(gè)物體，每個(gè)物體的重量是已知的正實(shí)數(shù)。給定足夠多個(gè)空箱子，問題是要在滿足兩個(gè)約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個(gè)數(shù)盡可能地少。兩個(gè)約束條件是：第一，每個(gè)物體均保持完整，恰好放到一個(gè)箱子中去。不能將物體分割成幾塊。第二，每個(gè)箱子中所放的物體的重量之和均不能超過一個(gè)相同的上限，這個(gè)上限是一個(gè)已知的正實(shí)數(shù)。</p><p>　　為了將問題描述得確切，本文提出一種形式化描述。&

26、lt;/p><p><b>　　表示物體的集合。</b></p><p><b>　　表示物體的重量。</b></p><p>　　表示每個(gè)箱子所能容納的物體的重量之和的上限。</p><p>　　表示所用箱子的集合。</p><p>　　，，是已知的。和是變量。</p&g

27、t;<p>　　問題是要在滿足如下兩個(gè)約束條件的前提下，使得所用箱子的個(gè)數(shù)盡可能地小。</p><p><b>　　(1.1)</b></p><p><b>　　(1.2)</b></p><p><b>　　其中，。</b></p><p>　　1.3 研究

28、現(xiàn)狀 </p><p>　　當(dāng)前求解NP難度問題的算法分為兩類：完整算法和近似算法。以一維裝箱問題為例，本文介紹這兩類算法。</p><p>　　完整算法[2]也稱為嚴(yán)格算法，其本質(zhì)是毫無(wú)遺漏的窮舉，因此能保證找到問題的最優(yōu)解，這是完整算法的優(yōu)點(diǎn)。完整算法的缺點(diǎn)是計(jì)算時(shí)間太長(zhǎng)，實(shí)際部門無(wú)法忍受，因此只能用于計(jì)算較小規(guī)模的問題實(shí)例。</p><p>　　近似算法是

29、當(dāng)前研究的主要方向。當(dāng)今時(shí)代，在純粹科學(xué)研究，通信、交通運(yùn)輸、工程設(shè)計(jì)和企事業(yè)管理部門，在社會(huì)的軍事、政治和商業(yè)的斗爭(zhēng)中涌現(xiàn)出大量NP難度的問題。若按經(jīng)典的純粹數(shù)學(xué)家們所熟悉的窮舉方法來(lái)求解，則計(jì)算時(shí)間動(dòng)輒達(dá)到天文數(shù)字，根本沒有實(shí)用價(jià)值。學(xué)術(shù)界許多有經(jīng)驗(yàn)的人認(rèn)為對(duì)于這些問題根本上就不存在完整、精確而不是太慢的求解算法。</p><p>　　于是人們寄希望于非完整的啟發(fā)式算法。啟發(fā)式算法屬于近似算法。這種算法對(duì)于很

30、刁鉆古怪的例子可能會(huì)失敗，但在通常面臨的實(shí)際情況下卻能算得既精確又相當(dāng)?shù)乜臁?lt;/p><p>　　到哪里去尋求啟發(fā)？這是一個(gè)根本的難點(diǎn)。中國(guó)古代的畫論有“外師造化內(nèi)得心源”的說法，即認(rèn)為智慧應(yīng)源于大自然與自身的心靈。事實(shí)上，自然界中的各種現(xiàn)象以及人類共同生活中的社會(huì)經(jīng)驗(yàn)，尤其是處理相互關(guān)系中許多矛盾的各種公關(guān)手腕都是很好的源泉。許多數(shù)學(xué)中的概念方法與策略事實(shí)上都是來(lái)源于人類對(duì)大自然的觀察，來(lái)源于他們?cè)谏鐣?huì)中生存奮

31、斗的社會(huì)經(jīng)驗(yàn)。</p><p>　　擬物擬人的途徑，本來(lái)就是科學(xué)的正統(tǒng)，而不是邪門歪道。隨著新的有意義的困難問題例如NP難度問題的涌現(xiàn)，公理化符號(hào)化的方法會(huì)逐漸顯出自己的不足，樸素的擬物擬人的途徑會(huì)逐漸被人們所選用。</p><p>　　特別值得指出的是，對(duì)于所得的啟發(fā)式算法，在遇到刁鉆的實(shí)例而表現(xiàn)出疲軟失敗的時(shí)候，人們可以十分自然地通過分析算法在該次失敗中的表現(xiàn)而對(duì)它有針對(duì)性地加以改善和

32、強(qiáng)化。經(jīng)過若干次自然的改善和強(qiáng)化之后，一個(gè)從實(shí)用角度看來(lái)叫人很是滿意的算法就會(huì)呈現(xiàn)在我們的面前[3]。</p><p>　　人們或者運(yùn)用自身的智慧，或者從大自然得到啟發(fā)，同時(shí)運(yùn)用良好的編程技術(shù)，經(jīng)常能設(shè)計(jì)出很好的近似算法，有可能在較短時(shí)間內(nèi)求解大規(guī)模問題實(shí)例，并達(dá)到令人滿意的精確度。這種方法被實(shí)際部門廣泛的使用。這是一條現(xiàn)實(shí)的路線。近似算法主要分為以下幾種類型：</p><p>　?、贁M物

33、算法和擬人算法。擬物算法和擬人算法是黃文奇提出的用于求解NP-hard難度問題的近似算法。擬物方法[4]是一個(gè)許多人會(huì)感到有趣有用的方法。其工作路徑是，到物理世界中去尋找出與原始數(shù)學(xué)問題等價(jià)的自然現(xiàn)象，然后觀察其中物質(zhì)運(yùn)動(dòng)的演化規(guī)律，從中受到啟發(fā)以得出形式化的、對(duì)于數(shù)學(xué)問題的求解算法。單純的擬物方法就已能解決許多問題[5][6]。在遇到刁鉆的問題時(shí)還可以將擬物方法和擬人方法聯(lián)合使用形成所謂擬物擬人方法[7]。對(duì)其工作的方式可作如下解釋、

34、描敘和評(píng)論。</p><p>　　由于物理狀態(tài)的演化天然地是按照使其Lagange函數(shù)的時(shí)間積分達(dá)到最小值的方式進(jìn)行，這就決定了擬物算法最終在數(shù)學(xué)上落實(shí)為優(yōu)化問題。然而用數(shù)學(xué)方法求解優(yōu)化問題，常常會(huì)碰到計(jì)算落入局部極小值陷阱的困難境地，對(duì)于如何跳出局部極小值陷阱，讓計(jì)算走向前景更好的區(qū)域中去的問題，擬物方法已無(wú)能為力。但是，人類在最近幾千年的共同生活中形成了豐富的社會(huì)經(jīng)驗(yàn)，利用這些經(jīng)驗(yàn)往往可以啟發(fā)出好的“跳出陷阱

35、”的策略。我們可以將這種把人類的社會(huì)經(jīng)驗(yàn)形式化為算法用以求解某些特殊困難問題的數(shù)學(xué)問題的方式稱為擬人途徑[8]。</p><p>　　擬物擬人算法的效率通常比生物遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、淬火算法要高，其原因是它有針對(duì)性地為具體問題找到了非常貼切的物理世界，而不是像在遺傳、神經(jīng)網(wǎng)絡(luò)、淬火方法中那樣依賴于一個(gè)惟一的始終不變的因而往往是不太貼切的物理體系。另外，擬人方法是向人學(xué)習(xí)，而人比遺傳、神經(jīng)網(wǎng)絡(luò)、淬火世界里的那些

36、蛋白質(zhì)、單個(gè)的神經(jīng)元及晶體顯然有高得多的智慧。當(dāng)然，這里的關(guān)鍵在于合適的數(shù)學(xué)形式化前夜的藝術(shù)和手段，要得到它們也不是一件很容易的事情，需要長(zhǎng)期艱苦細(xì)心的工作。這種得出算法的過程的艱苦性，可以說是擬物擬人途徑的一個(gè)缺點(diǎn)。</p><p>　　另外，生物遺傳算法、神經(jīng)網(wǎng)絡(luò)法、淬火法雖然針對(duì)性較差，但其適應(yīng)性較強(qiáng)，并且亦有其深刻的思想根源和自然背景。在肯動(dòng)腦筋并且機(jī)遇好的時(shí)候，擬物擬人與生物遺傳算法、神經(jīng)網(wǎng)絡(luò)法、淬火法

37、能結(jié)合得很好，能產(chǎn)生新的效能更高的算法。</p><p>　　至于純粹的擬人方法[9][10]，其途徑是將人類在最近幾千年的生存斗爭(zhēng)中所形成的某些經(jīng)驗(yàn)?zāi)承┳鞣ㄕf完整說清楚，然后加以抽象化形式化，最后形成算法以求解NP難度問題。</p><p>　　此方法的關(guān)鍵難點(diǎn)在于為給定的NP難度問題找到相應(yīng)的有悠久歷史的人類活動(dòng)。但是一旦找到，必然能很順利地發(fā)展為高效能的求解算法。</p>

38、<p>　?、趦?yōu)先分配規(guī)則算法。人們最早提出的求解一維裝箱問題的近似算法是優(yōu)先分配規(guī)則算法。優(yōu)先分配規(guī)則算法以某種優(yōu)先序依次給定將所有物體裝入某個(gè)箱子。優(yōu)先分配規(guī)則算法的速度非?？欤瞧渖山獾馁|(zhì)量仍有改進(jìn)的余地。因?yàn)閮?yōu)先分配規(guī)則算法速度很快，所以很多學(xué)者采用優(yōu)先分配規(guī)則算法來(lái)生成初始解。本文介紹降序首次適合算法（first fit decreasing）和降序最佳適合（best fit decreasing）算法。降序

39、首次適合算法是將所有物體按照重量從大到小的順序排成一個(gè)物體序列，然后依次取出序列中的一個(gè)物體，在所有能放下這個(gè)物體的箱子中，選取序號(hào)最小的箱子，把物體放進(jìn)去。降序最佳適合算法是將所有物體按照重量從大到小的順序排成一個(gè)物體序列，然后依次取出序列中的一個(gè)物體，在所有能放下這個(gè)物體的箱子中，選取空余最小的箱子，把物體放進(jìn)去。</p><p>　?、劬植克阉?local search)算法。局部搜索算法給出的解的質(zhì)量比優(yōu)

40、先分配規(guī)則算法高。局部搜索算法的工作過程是一個(gè)迭代的過程：從初始給定的解開始，所有物體裝在有窮個(gè)箱子中。取出第一個(gè)箱子中的所有物體，裝入其他箱子。此時(shí)某些箱子可能會(huì)超重，這是一個(gè)格局，稱為一個(gè)點(diǎn)。然后在與當(dāng)前格局相近的格局集合(即當(dāng)前點(diǎn)的鄰域)中搜索比當(dāng)前格局更好的格局。如果在鄰域中找到了比當(dāng)前格局更好的格局，那么接受這個(gè)更好的格局，然后繼續(xù)做迭代。如果當(dāng)前格局的鄰域中沒有比當(dāng)前格局更好的格局，也就是說，當(dāng)前格局是局部最優(yōu)解，那么算法停

41、機(jī)。具體來(lái)說，有兩種搜索策略。第一種搜索策略叫做 “見好就收”：檢查當(dāng)前格局的鄰域，一旦找到比當(dāng)前格局好的格局，就接受這個(gè)格局，這樣就做完了一次迭代，然后繼續(xù)做迭代；如果當(dāng)前格局的鄰域中沒有比當(dāng)前格局更好的格局，那么鄰域搜索停止。第二種搜索策略是找到鄰域中最好的格局，如果比當(dāng)前格局好，就接受這個(gè)格局，這樣就做完了一次迭代，然后繼續(xù)做迭代；如果當(dāng)前格局的鄰域中沒有比當(dāng)前格局更好的格局，那么鄰域搜索停止。當(dāng)鄰域搜索停止時(shí)，如果對(duì)應(yīng)一個(gè)解，則

42、接受這個(gè)解，繼續(xù)從新解開始做鄰域搜索。如果不對(duì)</p><p>　?、芙伤阉?tabu search)算法。禁忌搜索算法是基于局部搜索的一種算法，它可以看作是局部搜索算法的一種改進(jìn)算法。禁忌搜索算法由Glover[11]提出。禁忌搜索算法可用于求解各種組合優(yōu)化問題人們已經(jīng)提出了多種求解一維裝箱問題的禁忌搜索算法[12]。禁忌搜索算法生成解的質(zhì)量較高。禁忌搜索算法的工作過程是一個(gè)迭代的過程。從初始給定的解開始，所

43、有物體裝在有窮個(gè)箱子中。取出第一個(gè)箱子中的所有物體，裝入其他箱子。此時(shí)某些箱子可能會(huì)超重，這是一個(gè)格局，稱為一個(gè)點(diǎn)。然后在與當(dāng)前格局相近的格局集合(即當(dāng)前點(diǎn)的鄰域)中搜索比當(dāng)前格局更好的格局。算法找到當(dāng)前格局的鄰域中目標(biāo)函數(shù)值最小的格局，不論這個(gè)格局的目標(biāo)函數(shù)值是否比當(dāng)前格局小，都接受這個(gè)格局。這樣就做了一次迭代。然后繼續(xù)做迭代。像這樣做迭代，很容易陷入循環(huán)。為了防止循環(huán)，禁忌搜索算法設(shè)置一個(gè)名為禁忌表的數(shù)據(jù)結(jié)構(gòu)。禁忌表中記錄著在最近若

44、干次迭代中訪問過的格局，如果這些格局在當(dāng)前格局的鄰域中，那么就把它們從鄰域中清除掉。這樣就能夠在一定程度上避免循環(huán)，從而提高搜索效率。因?yàn)榻伤阉鲿?huì)接受比當(dāng)前格局差的格局，所以它能夠跳出局部最優(yōu)點(diǎn)。當(dāng)禁忌搜索因?yàn)?lt;/p><p>　?、菽M退火算法。模擬退火算法也是基于局部搜索的一種算法。模擬退火算法也可用于求解各種組合優(yōu)化問題，包括一維裝箱問題[13]。模擬退火算法檢查當(dāng)前格局的鄰域中的格局，如果鄰域中的這個(gè)格

45、局比當(dāng)前格局好，則一定接受這個(gè)格局；否則以一個(gè)大于0 同時(shí)小于1 的概率接受這個(gè)格局。與禁忌搜索算法一樣，模擬退火算法也能跳出局部最優(yōu)點(diǎn)。</p><p>　?、捱z傳算法。遺傳算法可用于求解一維裝箱問題[14]。遺傳算法的工作過程也是迭代的過程。與局部搜索算法、禁忌搜索算法和模擬退火算法不同的是，遺傳算法是將當(dāng)前一組格局更新為另外一組格局，而不是將當(dāng)前一個(gè)格局更新為另外一個(gè)格局。遺傳算法首先隨機(jī)生成一組格局做為所

46、謂初始種群，然后對(duì)種群做迭代：從當(dāng)前種群(當(dāng)前這組格局)中選擇一些格局，對(duì)這些格局做遺傳操作(交叉、變異等)，從而得到一組新的格局(即一個(gè)新的種群)。</p><p>　　1.4 本論文的主要結(jié)構(gòu)</p><p>　　本學(xué)位論文主要由五個(gè)部分組成，其內(nèi)容具體安排如下：</p><p>　　第一部分是緒論。主要介紹了本課題的來(lái)源、選題背景、問題描述和論文的主要結(jié)構(gòu)。

47、</p><p>　　第二部分介紹算法描述。</p><p>　　第三部分介紹程序設(shè)計(jì)。</p><p>　　第四部分介紹程序運(yùn)行的結(jié)果。</p><p>　　第五部分是本課題研究的結(jié)論。</p><p><b>　　2 算法描述</b></p><p>　　人類把物體往

48、容器中裝，已有幾千年以上的經(jīng)驗(yàn)。我們可以利用這些生活經(jīng)驗(yàn)來(lái)發(fā)展出高效率的算法。</p><p>　　本文提出的這種算法是一種擬人算法。算法由三個(gè)部分組成。第一部分是降序最佳適合算法（best fit decreasing）用于生成初始解。第二部分是鄰域搜索算法。給定一個(gè)解，用鄰域搜索算法可以通過迭代改進(jìn)這個(gè)解。第三部分是跳坑策略。跳坑用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。算法三個(gè)部分的思

49、想來(lái)源均為人類的生產(chǎn)和生活經(jīng)驗(yàn)，本算法是由擬人途徑得到的。</p><p>　　定義2.1 某些物體在箱子里，其余物體在箱子外，這稱為一個(gè)格局。</p><p>　　初始格局是所有物體均在箱子外，所有箱子均為空。與初始格局對(duì)稱的終止格局是所有物體均在箱子里。</p><p>　　終止格局的形式化描述為：整數(shù)變?cè)?，…，的一組指派表示一個(gè)終止格局，其中表示物體放在箱子

50、中，，。把對(duì)整數(shù)變?cè)?，…，的一組指派看成空間中的一個(gè)點(diǎn)，將與點(diǎn)在一個(gè)、兩個(gè)或更多個(gè)變?cè)先≈挡煌狞c(diǎn)的集合稱為的鄰域。</p><p>　　考慮一個(gè)終止格局，如果每個(gè)箱子中所裝的物體的重量之和均不超過上限，則此終止格局對(duì)應(yīng)著一個(gè)解。</p><p>　　2.1 擬人算法的大致框架</p><p>　　步驟一（初始解的生成）：調(diào)用一種簡(jiǎn)單好想的構(gòu)造型算法生成初始解。

51、該構(gòu)造型算法見2.2節(jié)。轉(zhuǎn)步驟二。</p><p>　　步驟二（判斷停機(jī)條件）：判斷停機(jī)條件是否滿足，若滿足則停機(jī)，輸出本次計(jì)算過程中所找到的最好的解。若不滿足停機(jī)條件，則轉(zhuǎn)步驟三。停機(jī)條件恰有兩個(gè)：第一，客觀最優(yōu)解已經(jīng)找到。第二，跳坑次數(shù)已經(jīng)達(dá)到上限。只要滿足其中一個(gè)條件，則算法停機(jī)。</p><p>　　步驟三（鄰域搜索）：從當(dāng)前解出發(fā)，調(diào)用鄰域搜索算法進(jìn)行計(jì)算，試圖尋找一個(gè)比當(dāng)前解更

52、好的解。該鄰域搜索算法見2.3節(jié)和2.4節(jié)。鄰域搜索算法執(zhí)行完畢后，轉(zhuǎn)步驟二。</p><p>　　2.2 生成初始解</p><p>　　步驟一：開局。將所有物體按照重量從大到小的順序排好序。這個(gè)物體序列記為。所有物體均在箱子外面。將物體放在箱子中。轉(zhuǎn)步驟二。</p><p>　　步驟二：考慮當(dāng)前格局。如果所有物體均在箱子里面，則生成了初始解。如果至少有一個(gè)物體

53、在箱子外面，則按照如下手法將一個(gè)物體放入箱子。在當(dāng)前格局中，物體在箱子里，物體在箱子外。如果箱子中的每一個(gè)均不能容納，則將放入箱子。如果箱子中的若干個(gè)箱子能容納，則選取在當(dāng)前格局空余最小的箱子（如果空余最小的箱子不止一個(gè)，則選取其中編號(hào)最小的箱子），將放入，從而演化到新格局。轉(zhuǎn)步驟二。</p><p><b>　　2.3 鄰域搜索</b></p><p>　　本文提

54、出的鄰域搜索的思路來(lái)源于人們用箱子裝物體的實(shí)際經(jīng)驗(yàn)。當(dāng)個(gè)物體裝在個(gè)箱子中，首先任意取一個(gè)裝了物體的箱子，取出其中全部物體，裝到其它已裝有物體的箱子中去。此時(shí)很可能有某些箱子中的物體重量超過上限。然后根據(jù)某種方法進(jìn)行調(diào)整，試圖使得每個(gè)箱子中的物體重量均不超過上限。最終鄰域搜索的結(jié)果恰有兩種：或者成功，或者失敗。</p><p>　　步驟一：考慮當(dāng)前解。將當(dāng)前解的格局記錄下來(lái)，記為。物體放在箱子中。令。轉(zhuǎn)步驟二。&l

55、t;/p><p>　　步驟二：如果，則鄰域搜索結(jié)束。如果，則取出箱子中的所有物體，將的編號(hào)改為，…，將的編號(hào)改為。按照從重量大到小的順序，依次將物體放入已裝物體重量之和最小的箱子（如果已裝物體重量之和最小的箱子不止一個(gè)，則選取序號(hào)小的箱子），從而演化到新格局。如果無(wú)超重的箱子，則新格局是一個(gè)解。將這個(gè)解作為當(dāng)前解，鄰域搜索結(jié)束。如果有超重的箱子，無(wú)不滿的箱子，則當(dāng)前解是客觀上的最優(yōu)解，停機(jī)。如果既有超重的箱子，又有不

56、滿的箱子，則轉(zhuǎn)步驟三。</p><p>　　步驟三：進(jìn)行調(diào)整。如果經(jīng)過調(diào)整后，得到了一個(gè)比當(dāng)前解更好的解，則接受這個(gè)解，鄰域搜索結(jié)束。如果沒有找到一個(gè)比當(dāng)前解更好的解，則返回到當(dāng)前解的格局。。轉(zhuǎn)步驟二。</p><p>　　所謂調(diào)整，是一個(gè)迭代的過程。已知一個(gè)終止格局，用一個(gè)新的終止格局取代老的終止格局，這是迭代的一步。</p><p>　　在敘述如何進(jìn)行迭代之前，

57、要給出鄰域的定義。</p><p>　　取一個(gè)超重的箱子，記為。取一個(gè)不滿的箱子，記為?，F(xiàn)在要將中的若干物體放入中，將中的若干物體放入中。目的是要減輕中物體的重量，增加中物體的重量。中國(guó)人有句格言“天之道損有余而補(bǔ)不足[15]”。我們所設(shè)計(jì)的鄰域是基于這句格言的。</p><p>　　我們采用的目標(biāo)函數(shù)是由Fleszar和Hindi[16]提出的目標(biāo)函數(shù)。給定一個(gè)終止格局，目標(biāo)函數(shù)值等于所

58、有箱子中的物體重量的平方的和。調(diào)整的目的是要在所用箱子數(shù)不變的前提使得目標(biāo)函數(shù)值盡可能地小。形式化描述如下：</p><p>　　minimize (2.1)</p><p>　　其中是所用箱子數(shù)，是箱子中所裝物體重量。</p><p>　　對(duì)于點(diǎn)，是的一個(gè)鄰點(diǎn)。若，則稱為

59、的鄰域中的下降點(diǎn)。</p><p>　　第一種鄰域記為。將超重的箱子中的一個(gè)物體取出放入不滿的箱子。</p><p>　　第二種鄰域記為。將超重的箱子中的一個(gè)物體與不滿的箱子中的一個(gè)物體交換。</p><p>　　第三種鄰域記為。將超重的箱子中的一個(gè)物體與不滿的箱子中的兩個(gè)物體交換。</p><p>　　第四種鄰域記為。將超重的箱子中的一個(gè)物

60、體與不滿的箱子中的三個(gè)物體交換。</p><p>　　可以推廣到,...,，其中是箱子中所裝的物體個(gè)數(shù)。</p><p>　　因?yàn)橛辛耍瑒t不必考慮?？梢杂脙纱稳〈?。</p><p>　　第五種鄰域記為。將超重的箱子中的兩個(gè)物體與不滿的箱子中的一個(gè)物體交換。</p><p>　　第六種鄰域記為。將超重的箱子中的兩個(gè)物體與不滿的箱子中的兩個(gè)物體交

61、換。</p><p>　　可以推廣到,...,，其中是箱子中所裝的物體個(gè)數(shù)。</p><p>　　Loh，Golden和Wasil[1]提出了兩種鄰域和。Fleszar和Hindi[16]提出了兩種鄰域和。本文提出的鄰域與這些鄰域類似。差別在于本文考慮一個(gè)超重的箱子和一個(gè)不滿的箱子。文獻(xiàn)[1][16]考慮任意兩個(gè)箱子。已知一個(gè)點(diǎn)，考慮其鄰域，若一個(gè)鄰點(diǎn)對(duì)應(yīng)的目標(biāo)函數(shù)值嚴(yán)格小于當(dāng)前點(diǎn)對(duì)應(yīng)的目

62、標(biāo)函數(shù)值，則這個(gè)點(diǎn)稱為下降點(diǎn)。</p><p>　　微調(diào)的思路如下所述。</p><p>　　第一，從一個(gè)給定的終止格局開始，這是初始點(diǎn)。</p><p>　　第二，設(shè)在任一時(shí)刻的值已算出，首先按照某種自然的順序依次考慮當(dāng)前點(diǎn)的鄰點(diǎn)。若下降點(diǎn)集非空，則用第一個(gè)下降點(diǎn)作為在時(shí)刻的值。我們將這種從到的過渡稱為下降步驟。若下降點(diǎn)集為空，則已知點(diǎn)為函數(shù)的局部最小值點(diǎn)，于是按

63、照某種基于擬人思路的“跳坑”策略將計(jì)算從點(diǎn)跳到其鄰域中的一個(gè)確定的新點(diǎn)。我們可將這種從到的過渡稱為逃出步驟。</p><p>　　以上思路雖然是本質(zhì)的，但有一個(gè)小漏洞需要補(bǔ)平。即在逃出步驟中，若點(diǎn)按照跳坑策略逃出到，則很可能從的角度來(lái)看，老點(diǎn)是的鄰域中的下降點(diǎn)，于是很有可能從出發(fā)的下降步驟是回到。即計(jì)算走了回頭路。</p><p>　　為補(bǔ)平這一漏洞，我們可以設(shè)置變?cè)?。這樣，我們的尋優(yōu)

64、搜索的思路框架被發(fā)展為如下步驟：</p><p>　　步驟一：從一個(gè)給定的終止格局開始，這是初始點(diǎn)。將變?cè)跏技x為空集。轉(zhuǎn)步驟二。</p><p>　　步驟二：考慮當(dāng)前點(diǎn)的鄰域。有些鄰點(diǎn)是由對(duì)禁集中的變?cè)x值而得到的。除去這樣的鄰點(diǎn)不考慮。按照某種自然的順序考察鄰域，如果找到了一個(gè)下降點(diǎn)，則見好就收，接受此下降點(diǎn)。如果對(duì)鄰域搜索完畢，沒有找到下降點(diǎn)，則按跳坑策略跳到一個(gè)點(diǎn)。轉(zhuǎn)步驟三

65、。</p><p>　　步驟三：若當(dāng)前點(diǎn)對(duì)應(yīng)一個(gè)解，則停止。若計(jì)算時(shí)間已超限，則停止。否則更新變?cè)?lt;/p><p>　　以下我們描述跳坑策略和更新變?cè)牟襟E。</p><p><b>　　2.4 跳坑策略</b></p><p>　　當(dāng)前點(diǎn)為局部最小值點(diǎn)，在所有超重的箱子中均勻地隨機(jī)選取一個(gè)箱子，在這個(gè)箱子中

66、的所有物體中均勻地隨機(jī)選取一個(gè)物體，在所有不滿的箱子中均勻地隨機(jī)選取一個(gè)箱子，將從中取出，放入。</p><p>　　這個(gè)跳坑策略的思想來(lái)源依然是“天之道損有余而補(bǔ)不足”。</p><p>　　變?cè)难莼?guī)則如下：</p><p>　　第一，如果從老點(diǎn)到是按下降步驟操作的，則置變?cè)癁榭铡?lt;/p><p>　　第二，如果從老點(diǎn)到是按逃出

67、步驟操作的，則將對(duì)應(yīng)的變?cè)尤胱冊(cè)?lt;/p><p><b>　　3 程序設(shè)計(jì)</b></p><p>　　本文的程序設(shè)計(jì)采用已故卓越美籍荷蘭裔計(jì)算機(jī)科學(xué)家Edsger Wybe Dijkstra提出的結(jié)構(gòu)化程序設(shè)計(jì)思想。</p><p>　　Edsger Wybe Dijkstra早在1951年就學(xué)習(xí)了計(jì)算機(jī)程序設(shè)計(jì)，然后參與了一些荷蘭

68、的大工程例如Fokker友誼飛機(jī)的開發(fā)，其中機(jī)翼震動(dòng)的計(jì)算需要編寫程序。因?yàn)榫帉扆嫶蟪绦虻男枰?，Edsger Wybe Dijkstra提出了結(jié)構(gòu)化程序設(shè)計(jì)思想。</p><p>　　結(jié)構(gòu)化程序設(shè)計(jì)可歸納為“自頂向下，逐步求精”。結(jié)構(gòu)化程序設(shè)計(jì)由計(jì)算機(jī)科學(xué)家提出，但是其思想根源并不是純粹科學(xué)，而是人類在長(zhǎng)期生存斗爭(zhēng)中的經(jīng)驗(yàn)。軍事家提出“分而治之”，“集中優(yōu)勢(shì)兵力，各個(gè)殲滅敵人”。這些說法是結(jié)構(gòu)化程序設(shè)計(jì)思想的來(lái)源

69、。在軍事上，如果敵人多而且強(qiáng)，則設(shè)法將敵人分割，集中兵力和火力將敵人各個(gè)殲滅。作者在寫程序時(shí)，如果程序難而且復(fù)雜，不好寫，則首先將程序分成一些模塊，然后集中思維和時(shí)間去寫每一個(gè)模塊的程序。</p><p>　　所謂“自頂向下”是指首先將程序分割為幾個(gè)大模塊，從而寫出主函數(shù)main()的程序，然后對(duì)復(fù)雜的大模塊，再分割成若干小模塊，如果小模塊仍然較復(fù)雜，則依此類推，繼續(xù)分割，直到小模塊容易被編程者寫出程序?yàn)橹埂?l

70、t;/p><p>　　所謂“逐步求精”是指在分割程序的過程中，程序的面貌越來(lái)越清晰，針對(duì)每個(gè)小模塊，寫出清晰的程序。最終將所有模塊合并，成為所需要的完整的程序。</p><p>　　作者對(duì)面向?qū)ο蟮某绦蛟O(shè)計(jì)也曾經(jīng)淺嘗。結(jié)構(gòu)化程序設(shè)計(jì)思想與面向?qū)ο蟮某绦蛟O(shè)計(jì)思想并無(wú)實(shí)質(zhì)性矛盾，在需要引入對(duì)象概念的場(chǎng)合，這兩者可以很好地結(jié)合。例如可以采用結(jié)構(gòu)化程序設(shè)計(jì)來(lái)寫底層的核心的程序，采用面向?qū)ο蟮某绦蛟O(shè)計(jì)來(lái)

71、設(shè)計(jì)外表的吸引人的界面。</p><p><b>　　3.1 程序流程</b></p><p>　　整個(gè)程序的流程如圖3.1所示。整個(gè)程序可分為四個(gè)模塊。</p><p>　　第一個(gè)模塊是讀取文本文件中問題實(shí)例的數(shù)據(jù)，調(diào)用庫(kù)函數(shù)malloc()為各種數(shù)據(jù)結(jié)構(gòu)分配內(nèi)存。這個(gè)模塊的程序簡(jiǎn)單，無(wú)需再分解。</p><p>　

72、　第二個(gè)模塊是生成初始解。這個(gè)模塊的程序較簡(jiǎn)單，無(wú)需再分解。</p><p>　　第三個(gè)模塊是鄰域搜索。這個(gè)模塊是重點(diǎn)，程序復(fù)雜，本身需分成一些更小的模塊。</p><p>　　第四個(gè)模塊是釋放內(nèi)存。這個(gè)模塊的程序最簡(jiǎn)單，只需調(diào)用庫(kù)函數(shù)free()就可以，無(wú)需再分解。</p><p>　　圖3.1 整個(gè)程序的流程</p><p>　　作者寫程

73、序時(shí)遵循如下四條原則。</p><p>　　第一，要有整塊的時(shí)間來(lái)寫程序，不要煩，不要急。</p><p>　　第二，要有好的草稿紙，舉個(gè)例子，畫圖輔助自己寫程序。</p><p>　　第三，草稿紙要寫得干凈，不要折，寫上頁(yè)碼，作為原始文檔好好保存。</p><p>　　第四，自頂向下，逐步求精。</p><p>　　

74、3.1.1 讀取文本文件中的數(shù)據(jù)</p><p>　　一個(gè)benchmark問題實(shí)例存儲(chǔ)在一個(gè)文本文件中，以名為TEST0005的問題實(shí)例為例，存儲(chǔ)在名為TEST0005.txt的磁盤文件中，其格式如下。</p><p>　　第1行：57表示物體的重量總共恰有57種不同的重量。</p><p>　　第2行：10000表示箱子的容量是100

75、00。</p><p>　　第3行：49643表示重量為4964的物體恰有3個(gè)。</p><p><b>　　依此類推。</b></p><p>　　第59行：402表示重量為40的物體恰有2個(gè)。</p><p>　　在C語(yǔ)言中，要讀取文本文件中的數(shù)據(jù)，首先定義一個(gè)FILE類型的指針FP，然后利

76、用庫(kù)函數(shù)fopen()來(lái)打開文件，例如FP = fopen("e:\\TEST0005.txt","r")，其中e:\\TEST0005.txt是文本文件所在目錄以及文件名，r表示以只讀方式打開文件，最后利用庫(kù)函數(shù)fscanf()文件指針,格式字符串，變量地址)來(lái)讀取文本文件中的數(shù)據(jù)，例如fscanf(FP,"%d",&numberOfDifferentItemWeig

77、hts)表示讀取FP指針指向的文本文件中一個(gè)符號(hào)串，將其轉(zhuǎn)化為十進(jìn)制整數(shù)，存儲(chǔ)在變量numberOfDifferentItemWeights中。</p><p>　　本文的程序采用庫(kù)函數(shù)malloc()來(lái)給數(shù)據(jù)分配內(nèi)存。與之對(duì)稱地，當(dāng)程序運(yùn)行結(jié)束的前夕，調(diào)用庫(kù)函數(shù)free()來(lái)釋放用malloc()分配的內(nèi)存。</p><p>　　本模塊中使用的主要數(shù)據(jù)結(jié)構(gòu)如下。</p>&

78、lt;p>　　int NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS表示物體總共有多少種不同的重量。</p><p>　　int CAPACITY_C_OF_THE_BINS表示箱子容量。</p><p>　　int * ITEM_WEIGHTS是整型數(shù)組名，此數(shù)組記錄所有不同的重量的值。</p><p>　　int * NUMBER_O

79、F_ITEMS_OF_WEIGHTS是整型數(shù)組名，此數(shù)組記錄每種重量的物體有多少個(gè)。</p><p>　　int NUMBER_OF_ITEMS表示物體總數(shù)。</p><p>　　int * WEIGHT_OF_ITEMS是整型數(shù)組名，此數(shù)組記錄每個(gè)物體的重量。</p><p>　　NUMBER_M_OF_DIFFERENT_ITEM_WEIGHTS，CAPACIT

80、Y_C_OF_THE_BINS，ITEM_WEIGHTS，NUMBER_OF_ITEMS_OF_WEIGHTS是題目給定的，可以直接從文本文件中讀取。NUMBER_OF_ITEMS，WEIGHT_OF_ITEMS可以根據(jù)已知的信息算出。</p><p>　　3.1.2 生成初始解</p><p>　　生成初始解的函數(shù)命名為generate_initial_solution()。此模塊中所

81、使用的主要數(shù)據(jù)結(jié)構(gòu)如下。</p><p>　　int * BIN_NUMBER_OF_ITEMS記錄在初始解中，每個(gè)物體放在哪個(gè)箱子中。</p><p>　　int * SPARE_SPACE_OF_BINS記錄每個(gè)箱子的剩余空間。</p><p>　　int NUMBER_OF_OCCUPIED_BINS表示使用的箱子數(shù)。</p><p>

82、　　int ** ITEMS_NUMBER_IN_EACH_BIN是二維整型數(shù)組名，其中記錄每個(gè)箱子中放了哪些物體。</p><p>　　程序生成初始解后，將初始解作為當(dāng)前解。有_IN_CURRENT_SOLUTION_PATTERN后綴的變量是屬于對(duì)應(yīng)當(dāng)前解的終止格局的。</p><p>　　int * BIN_NUMBER_OF_ITEMS_IN_CURRENT_SOLUTION_PA

83、TTERN表示在對(duì)應(yīng)當(dāng)前解的終止格局中，每個(gè)物體放在哪個(gè)箱子中。</p><p>　　int NUMBER_OF_OCCUPIED_BINS_IN_CURRENT_SOLUTION_PATTERN表示在當(dāng)前解中使用的箱子數(shù)。</p><p>　　int ** ITEMS_NUMBER_IN_EACH_BIN_IN_CURRENT_SOLUTION_PATTERN是二維整型數(shù)組，其中記錄在當(dāng)

84、前解中每個(gè)箱子中放了哪些物體。</p><p>　　int * LOAD_OF_EACH_BIN_IN_CURRENT_SOLUTION_PATTERN記錄在當(dāng)前解中每個(gè)箱子中物體的重量之和。</p><p>　　INCREASING_SEQUENCE_OF_BINS_BY_LOAD_IN_CURRENT_SOLUTION_PATTERN是一個(gè)整型數(shù)組，其中記錄在當(dāng)前解中箱子按照重量從小到

85、大的序列。</p><p>　　3.1.3 鄰域搜索</p><p>　　鄰域搜索函數(shù)命名為local_search()。此模塊中所使用的主要數(shù)據(jù)結(jié)構(gòu)如下。</p><p>　　有_IN_CURRENT_FINAL_PATTERN后綴的變量是屬于當(dāng)前終止格局的，很可能并不對(duì)應(yīng)一個(gè)解。</p><p>　　int * BIN_NUMBER_O

86、F_ITEMS_IN_CURRENT_FINAL_PATTERN表示在當(dāng)前終止格局中使用的箱子數(shù)。</p><p>　　int NUMBER_OF_OCCUPIED_BINS_IN_CURRENT_FINAL_PATTERN是二維整型數(shù)組，其中記錄在當(dāng)前終止格局中每個(gè)箱子中放了哪些物體。</p><p>　　int ** ITEMS_NUMBER_IN_EACH_BIN_IN_CURREN

87、T_FINAL_PATTERN表示在當(dāng)前終止格局中，每個(gè)物體放在哪個(gè)箱子中。</p><p>　　int * LOAD_OF_EACH_BIN_IN_CURRENT_FINAL_PATTERN記錄在當(dāng)前終止格局中每個(gè)箱子中物體的重量之和。</p><p>　　INCREASING_SEQUENCE_OF_BINS_BY_LOAD_IN_CURRENT_FINAL_PATTERNint 是一

88、個(gè)整型數(shù)組，其中記錄在當(dāng)前終止格局中箱子按照重量從小到大的序列。</p><p>　　3.1.4 釋放內(nèi)存</p><p>　　釋放函數(shù)命名為free_memory()。此函數(shù)調(diào)用庫(kù)函數(shù)free()來(lái)釋放用庫(kù)函數(shù)malloc()分配的內(nèi)存空間。</p><p>　　以ITEMS_NUMBER_IN_EACH_BIN為例，此二維數(shù)組所占用的內(nèi)存是采用malloc(

89、)函數(shù)分配的。程序如下：</p><p>　　ITEMS_NUMBER_IN_EACH_BIN = (int **)malloc(sizeof(int *) * (NUMBER_OF_OCCUPIED_BINS+1));</p><p>　　for(j=1; j<=NUMBER_OF_OCCUPIED_BINS; j++)</p><p>　　ITEMS_NU

90、MBER_IN_EACH_BIN[j] = (int *)malloc(sizeof(int) * (MAXIMAL_NUMBER_OF_ITEMS_IN_A_BIN+1));</p><p>　　在釋放二維數(shù)組的內(nèi)存時(shí)，程序應(yīng)為：</p><p>　　for(j=1; j<=NUMBER_OF_OCCUPIED_BINS; j++)</p><p>　　fr

91、ee(ITEMS_NUMBER_IN_EACH_BIN[j]);</p><p>　　free(ITEMS_NUMBER_IN_EACH_BIN);</p><p><b>　　3.2 調(diào)試程序</b></p><p>　　在調(diào)試程序的過程中，作者遵循的四條原則如下。</p><p>　　不熬夜，保證在腦筋清醒的狀態(tài)下

92、調(diào)試程序。</p><p>　　用折半查找，找到第一個(gè)出錯(cuò)的地方。</p><p>　　第三，用放大鏡仔細(xì)看第一個(gè)出錯(cuò)的地方，也就是顯示各個(gè)變量的值，就能看出錯(cuò)在哪里。</p><p>　　第四，將調(diào)試過程中發(fā)現(xiàn)的錯(cuò)誤以及改正的手段記錄在紙上作為原始文檔以備忘。</p><p>　　作者在調(diào)試本文的程序時(shí)所找出并糾正的錯(cuò)誤按順序列舉如下。&l

93、t;/p><p>　?、?local_search()函數(shù)中一個(gè)for循環(huán)沒有用花括號(hào)將循環(huán)體括起來(lái)。</p><p>　?、?將箱子按照重量從小到大排序的算法有錯(cuò)，改為用冒泡排序的算法。</p><p>　?、?generate_initial_solution()函數(shù)生成初始解后，要將其信息記錄在各種數(shù)據(jù)結(jié)構(gòu)中。最初版的程序沒有記錄這些信息，從而導(dǎo)致出錯(cuò)。</

94、p><p>　?、?swap_one_zero()函數(shù)中，從一個(gè)超重的箱子取一個(gè)物體放在一個(gè)不滿的箱子中，需修改這兩個(gè)箱子的重量值，然后更新箱子按照重量從小到大排序的序列。更新序列的程序有錯(cuò)，交換兩個(gè)數(shù)組元素的值時(shí)寫錯(cuò)了。</p><p><b>　　4 計(jì)算結(jié)果</b></p><p>　　我用C語(yǔ)言編程序?qū)崿F(xiàn)了本文提出的算法。編譯器是微軟公司

95、的Visual C++ 6.0。我采用最快速度選項(xiàng)來(lái)編譯源程序。程序在CPU為AMD 3.0 GHz的個(gè)人電腦上運(yùn)行。</p><p>　　本文的程序計(jì)算了一組共17個(gè)benchmark問題實(shí)例。這17個(gè)benchmark問題實(shí)例由Wäscher 和 Gau 于1996年提出。這組問題實(shí)例可通過網(wǎng)絡(luò)下載，網(wǎng)址為http://paginas.fe.up.pt/~esicup/index.php。</

96、p><p>　　這17個(gè)實(shí)例可分為兩類。第一類有8個(gè)問題實(shí)例名為TEST0005、TEST0014、TEST0022、TEST0030、TEST0058、TEST0065、TEST0068、TEST0082，目前尚未確定其客觀最優(yōu)解。第二類有9個(gè)問題實(shí)例名為TEST0044、TEST0049、TEST0054、TEST0055_52、TEST0055_64、TEST0075、TEST0084、TEST0095、TES

97、T0097，目前已經(jīng)確定了其客觀最優(yōu)解。</p><p>　　第一類8個(gè)問題實(shí)例的計(jì)算結(jié)果見表5.1。本文的程序標(biāo)記為擬人算法。在這一組共8個(gè)benchmark問題實(shí)例中，擬人算法對(duì)6個(gè)問題實(shí)例找出了與當(dāng)前最好解質(zhì)量相同的解。擬人算法還證明了TEST0068這個(gè)benchmark問題實(shí)例的目前已知最好解正是客觀最優(yōu)解。在表5.1中以粗體顯示TEST0068的計(jì)算結(jié)果。</p><p>　　

98、表5.1 擬人算法對(duì)Wäscher 和 Gau提出的尚未確定客觀最優(yōu)解的8個(gè)實(shí)例的計(jì)算結(jié)果</p><p>　　TEST000529 29 0.22</p><p>　　TEST001424 24 0.14</p><p>　　T

99、EST002215 15 0.05</p><p>　　TEST003028 28 0.22</p><p>　　TEST005820 21 0.10</p><p>　　TE

100、ST006516 16 0.06</p><p>　　TEST006812 12 0.03</p><p>　　TEST008224 25 0.16</p><p>　　第二類

101、9個(gè)問題實(shí)例的計(jì)算結(jié)果見表5.2。擬人算法找到了全部9個(gè)問題實(shí)例的客觀最優(yōu)解。</p><p>　　表5.2 擬人算法對(duì)Wäscher 和 Gau提出的已經(jīng)確定客觀最優(yōu)解的9個(gè)實(shí)例的計(jì)算結(jié)果</p><p>　　TEST004414 14 0.03</p><p>　　TEST004911

102、 11 0.01</p><p>　　TEST005414 14 0.05</p><p>　　TEST0055_5215 15 0.03</p><p>　　TEST0055_6

103、420 20 0.04</p><p>　　TEST007513 13 0.02</p><p>　　TEST008416 16 0.04</p><p>　　TEST0095

104、16 16 0.03</p><p>　　TEST009712 12 0.01</p><p><b>　　5 結(jié)論</b></p><p>　　一維裝箱問題具有很高的理論價(jià)值和實(shí)踐價(jià)值。一維裝箱問題是一種NP難度問

105、題，因此具有很高的理論價(jià)值。一維裝箱問題在生產(chǎn)實(shí)踐中有應(yīng)用，因此也具有很高的實(shí)踐價(jià)值。如果能夠設(shè)計(jì)出求解一維裝箱問題的高效算法，就能提高生產(chǎn)效率。</p><p>　　數(shù)十年來(lái)，世界各國(guó)學(xué)者對(duì)一維裝箱問題做了廣泛而又深入的研究。求解一維裝箱問題的分為完整算法和近似算法兩類。完整算法的本質(zhì)是毫無(wú)遺漏的窮舉，雖然能保證找到問題的最優(yōu)解，但是計(jì)算時(shí)間太長(zhǎng)，實(shí)際部門無(wú)法忍受，因此只能用于計(jì)算較小規(guī)模的問題實(shí)例。</

106、p><p>　　近似算法是當(dāng)前研究的主要方向。我們深入細(xì)致地研究了一維裝箱問題，提出了一種求解一維裝箱問題的擬人算法，此算法屬于近似算法。</p><p>　　擬人方法的工作途徑是將人類在最近幾千年的生存斗爭(zhēng)中所形成的某些經(jīng)驗(yàn)?zāi)承┳龇ㄕf完整說清楚。對(duì)于裝箱，人類有超過幾千年的生活經(jīng)驗(yàn)。</p><p>　　本文的算法主要基于鄰域搜索和跳坑策略。本文的鄰域定義的思想來(lái)源是

107、“天之道損有余而補(bǔ)不足”。具體策略是把超重的箱子中的物體取出放到不滿的箱子中去。當(dāng)鄰域搜索遇到局部最優(yōu)解時(shí)，本文采用所謂跳坑策略跳出局部最優(yōu)解，將搜索引向有希望的方向。跳坑策略的思想來(lái)源是“三十六計(jì)走為上”。中國(guó)老百姓的這兩句格言暗示作者，使得作者順利地得到了本文的算法。</p><p>　　檢驗(yàn)算法的辦法有兩種：理論分析和實(shí)驗(yàn)測(cè)試。對(duì)于求解困難問題的較為有效的算法，絕對(duì)嚴(yán)格的理論分析（包括算法的精度的分析和算法

108、復(fù)雜度的分析兩個(gè)方面）經(jīng)常是既做不到又無(wú)必要。因此當(dāng)前國(guó)際上對(duì)于求解NP難度問題的算法的檢驗(yàn)主要采用實(shí)驗(yàn)測(cè)試。</p><p>　　本文采用實(shí)驗(yàn)測(cè)試的辦法來(lái)檢驗(yàn)算法。本文的算法計(jì)算了一組共17個(gè)benchmark問題實(shí)例，這組問題實(shí)例分為兩類。第一類為8個(gè)問題實(shí)例，目前尚未確定其客觀最優(yōu)解。第二類為9個(gè)問題實(shí)例，目前已經(jīng)確定了其客觀最優(yōu)解。擬人算法對(duì)第一類問題實(shí)例中的6個(gè)問題實(shí)例找出了與當(dāng)前已知最好解質(zhì)量相同的解