求解裝箱問題的啟發(fā)式算法研究_第1頁
求解裝箱問題的啟發(fā)式算法研究_第2頁
求解裝箱問題的啟發(fā)式算法研究_第3頁
求解裝箱問題的啟發(fā)式算法研究_第4頁
全文預覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、若是一塊磚的長、寬、高可寫成a ×ab ×abc(這里a、b、c都是正整數(shù),則布魯京稱之為和諧(harmonic磚塊。其中1 ×2 ×4的磚塊(見圖一又稱為標準(canonical磚,因為它不但是滿足和諧條件的最簡單例子,而且又非常像砌墻用的實際磚頭。布魯京證明一批大小為a ×ab ×abc的和諧磚塊能正好完全填滿一個匣子的充分及必要條件,是匣子的大小必須呈(ax×(aby×(abcz形式,其中x、y、z 都是整數(shù)。布魯京的結(jié)果可以推廣到高維數(shù)的歐幾里得空間,以及二維空間(即平面。在平面上,1 ×2的長方

2、形紙牌若可填滿一個大的長方形,則此長方形最少有一邊是偶數(shù)?,F(xiàn)在回到布魯京的小孩所面臨的難題。由于6不能被4除盡,根據(jù)布魯京定理,這個難題是不能解的;不過有沒有簡單的證明呢?讓我們先看另一個比較簡單的類似問題:把邊長為8的正方形紙板斜對角上的兩個方格子(面積各為1剪去后,能否用31塊1 ×2的小紙牌填滿呢?不能,證明如下:把原先紙板上的64個小方格涂以兩種不同的顏色,使相鄰兩格顏色不同。由于剪去的兩個格子顏色一樣,剩下的紙板不可能用31個紙牌填滿,因為每塊小紙牌所填入的兩格顏色不一樣之故。利用類似的方法可以把六階(指每邊長為6立方體分為27個二階小立方體,使任兩個相鄰的顏色都不同(見圖

3、二。任一塊標準磚所占有的8個格子必然是4黑4白,但大立方體中黑格子比白格子多8個,所以最多只能放入26塊磚頭??死{(D. A. Klarner在1973年趣味數(shù)學期刊第六卷第二期發(fā)表一篇文章迭磚問題,引入可劈性(cleavability的觀念。他證明若一個平面上的大長方形可以由若干個同樣大小的小長方形所填滿,則各種填法之中必有一種方法使得填好之后,可以把大長方形劈開分成兩個長方形,而每一個正好可以用這些小長方形填滿。不過在三維空間中沒有可劈性,星馬士特(D. Singmaster發(fā)現(xiàn)了一個最簡單的反例:一個5 ×5 ×12 的匣子可以用1 ×3 ×4的

4、磚塊來塞滿,但不論如何塞法都不滿足可劈性。另一問題是,對某一形狀的磚塊而言,非可劈的匣子種類是否無限多?答案是意外的否??死{證明在任何級數(shù)比2大的歐氏空間中,對任一種磚而言,只有有限個匣子是可被它填滿但卻不可劈開。1971年,二位匈牙利數(shù)學家卡透納(G.Katona及史沙茲(D.Szasz把克氏定理推廣,他們得到一些數(shù)目上的上限(指匣子的數(shù)目。如果不限于用同一類的磚塊,我們就可引入許多精彩的問題。其中最簡單的是一個三階立方體難題:我們想要用6塊1 ×2 ×2的磚頭及3塊單位體積的小立方體來填滿一個3 ×3 ×3的立方體(見圖三。這個難題看起來容易,但解

5、起來相當困難。如不計旋轉(zhuǎn)及鏡像反映,解法只有一種:3個小立方體必須沿對角線排列(見圖四。證明如下:考慮任何一個3 ×3截面,假定如圖四所示涂以黑白二色,則得5格黑色4格白色(相鄰兩截面把黑白二色交換。不管一塊1 ×2 ×2的磚頭如何放法,在每一截面中它將占有02或4個格子,其中黑白二色的格子數(shù)相同。所以9個截面中,每一截面必須剛剛好有一個格子被一個單位體積的磚塊所占有。而且每一截面中,這個單位磚必須放在正當中或者四角上。于是只有如圖四所示的排法;剩下6塊磚頭排法很容易,不再詳述?,F(xiàn)在回到用同樣的磚塊來填滿一個匣子的問題。我們可以問以下的問題:若一個匣子不能被一組(

6、同樣大小磚塊所完全填滿,那么最多可以塞幾個?這個問題非常困難。1974年,布勞迪和佛拉格(R. A. Brualdi, T. H. Foregger發(fā)表了一篇論文,把這個難題解決了一部分。假設(shè)R為匣子當中的一些格子的集合,如果不管一塊磚怎樣放,它總要占有R中的格子,則R稱為代表組。在所有的代表組中如果以R的格子數(shù)為最少,就說R含有最小基數(shù)(cardinality。他們證明一個匣子所能塞入的磚塊(不限于和諧磚的數(shù)目不能超過這個最小基數(shù)。平面上一長方形中能放入最多的和諧磚數(shù)正好等于最小基數(shù)。但三維及高次空間則不然。以標準磚及立方體為例,四階立方體可以塞入標準磚,而且可以填滿,六階則以前證明過不可能

7、填滿,最多可放26塊。五階立方體有125格,由于不能被8除盡,所以不可能以標準磚(每塊8格填滿。此時最小基數(shù)雖是15,但至多只能放入14塊。布、佛二位有一個很麻煩的涂色證法,但加德納想到一個巧妙的歸謬證法:假設(shè)可以填入15塊標準磚,其余用5個單位體積的小立方體填滿,每個單位立方體在3個平行于表面的截面上,截面共有15個,而單位立方體只有5個,所以任一截面剛好含有1個單位立方體。這樣五階立方體6個表面的150格子就剩下150-6=144個,它們必須以標準磚的表面來占滿。但每一塊磚正好有一個1 ×2的側(cè)面靠到大立方體的表面上,于是留下144-(15 ×2=114 個格子,要用1

8、 ×4及2 ×4二種長方形來填滿,但114不能以4除盡,所以原假設(shè)不成立。加德納又想到另一個證明如下:考慮立方體的三個與三面(互相垂直平行而且通過中心的截面。每一截面是一個5 ×5的方塊,一共有75個格子。由于25是奇數(shù),可知每一面必有一格與一個單位立方體相交。(有許多可能性,例如放一個單位立方體在整個立方體的正中央。每一塊標準磚一定正好與這三個截面當中某一個有兩格相交(與其他的面則可能不相交,亦可能與4或8格相交。15塊標準磚又占去30格。75減去33所剩的格數(shù)42不可能被4除盡,所以無法塞入15塊標準磚。接下來是七階立方體。此立方體很容易塞入41塊標準磚,但問

9、題在于可否放入42塊標準磚,而以單位立方體填入余下的空間。一般的n階立方體也有類似的問題,而答案是這樣的:當以標準磚塞入n階的立方匣中時,若n為4之倍數(shù)則必可塞滿;若n為偶數(shù)但不能被4除盡,則有一塊磚塞不進去。n為奇數(shù)時,每一截面有n ×n個格子,因此必然有一個洞(單位格子,所以不可能填塞滿,而最多只可塞入(n3-n/8 塊標準磚。問題是在什么情形下可以塞入這些磚塊。安曼(R.Ammann證明當n為不等于16k±1的奇數(shù)時,不可能塞入最多數(shù)目即(n3-n/8的標準磚,而當n=16k±1時,的確可以塞入最多的磚頭。英國的巴尼斯(F.Barnes得到更進一步的結(jié)果,即

10、n16k±1且為奇數(shù)時,立方匣必可被比最多的數(shù)目少一個的磚塊所填滿。在西洋棋盤(64格放骨牌(面積為2格的問題,以前證明過,若把兩個斜對角上的格子去掉,則用涂色的方法可證明不能以31塊骨牌填滿,此問題可加推廣如下:若以交錯方式把棋盤涂以兩種顏色,若把同色的二格去掉,則必不可能以31塊骨牌填滿。但若把異色的二格拿掉,是不是就一定可以填滿呢?這問題要難多了。幾年前,IBM的古莫里(R.Gomory想出一巧妙的證明:把整個棋盤分隔開來(見圖五再取走異色的二格子A、B,則由其中一格A走到另一格B有兩種相反的走法,每一條路正好有偶數(shù)個格子,因此必可被骨牌填滿。另一個有趣的問題是如何證明不可能把一個每邊有25個格子的方塊,用2 ×2及3 ×3的小方塊來填滿??死{有一個簡單的證明(見圖六:他把大方塊以黑白兩色一條條的交錯涂色。一片2 ×2的小方塊不管怎樣放都必然遮蓋2黑2白。但大方塊中黑格子比白的多25個,所以我們必須想法子用3 ×

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論