在生活的某個時刻，大多數(shù)人都站在一塊鋪開的餅干面團(tuán)上，思考著如何以盡可能少的浪費(fèi)來最好地切出餅干。現(xiàn)在，即使是數(shù)學(xué)專家也放棄了尋找一種計(jì)算機(jī)算法來回答此類幾何問題的意愿。

切出圣誕餅干時，如何才能使面團(tuán)最大化?我們?nèi)绾卧诔浞掷每臻g的同時收拾行李箱或裝滿廚房櫥柜?可能有人認(rèn)為，“一定有最好的方法來做到這一點(diǎn)”?，F(xiàn)在，對這些問題進(jìn)行太深的思考似乎完全是在浪費(fèi)時間?，F(xiàn)在的科學(xué)證明，暫時不可能找出對四五個以上的辛辣姜餅人或圣誕樹餅干最有效的方法。

計(jì)算機(jī)科學(xué)系的助理教授Mikkel Abrahamsen和兩位研究同事研究了找出二維無重疊包裝對象的最佳方法是多么困難，這是計(jì)算機(jī)科學(xué)家數(shù)十年來所不愿解決的難題。

“雖然算法可以解決嚴(yán)重的復(fù)雜問題，但對于當(dāng)今的計(jì)算機(jī)而言，這仍然是一個很大的問題。就目前而言，不可能最佳地打包5-10個以上的對象。而且，我們的結(jié)果表明，這個數(shù)量暫時不會增加太多。” Mikkel Abrahamsen解釋說。

最佳包裝的東西不僅是家中偶爾遇到的問題，而且在包括服裝制造和金屬加工在內(nèi)的各種行業(yè)中也是如此。在每種情況下，重要的是切出盡可能少的廢料。在運(yùn)輸中，它適用于容器包裝。

只有四個姜餅曲奇

我們知道最小的方形容器的大小，可以在其中裝滿10個方形的1x1米托盤。但是，僅通過增加一個額外的托盤，就不可能計(jì)算出容器的最佳尺寸。亞伯拉罕森解釋說：

“隨著增加的托盤數(shù)量，計(jì)算時間將成倍增加。即使是最好的計(jì)算機(jī)也無法跟上。從理論上講這是可能的。但是基于計(jì)算能力的增長速度，我們可能需要花費(fèi)數(shù)百萬年的時間。以優(yōu)化其他一些對象的處理。”

此外，如果人們正在加工更復(fù)雜的形狀，例如圣誕樹狀姜餅，Mikkel Abrahamsen說，如今最多只能找到四個物體的最佳解決方案。

無限數(shù)量的選擇

是什么使它如此困難?亞伯拉罕森(Abrahamsen)解釋說，該問題類似于求解5級或更高級別的方程，并且存在許多未知數(shù)。在此，已知不能總是使用常規(guī)的算術(shù)運(yùn)算來寫下這樣的解決方案。

“我們的研究證明，問題具有我們在數(shù)學(xué)中稱為連續(xù)性的性質(zhì)，簡而言之，這意味著人們必須知道可以放置Cookie的所有坐標(biāo)以及可以放置Cookie的所有角度旋轉(zhuǎn)。”亞伯拉罕森解釋說。

由于可能的組合是無限的，因此無法創(chuàng)建所有試圖找到最佳包裝解決方案所需位置的列表。取而代之的是，最佳解決打包問題的算法需要進(jìn)行更多分析，這很耗時。這與許多其他已知的算法問題形成對比，在算法問題中，人們可以先嘗試有限數(shù)量的組合，然后再找到最佳組合。因此，包裝問題要困難得多。

因此在實(shí)踐中，沒有比我們?nèi)祟惸芟氲降母玫慕鉀Q包裝問題的方法了。

Mikkel Abrahamsen總結(jié)道：“在業(yè)界和整個廚房柜臺上，我們都必須繼續(xù)對我們的非最佳解決方案感到滿意，并放心，就目前而言，我們的人類仍然比計(jì)算機(jī)更勝一籌。”