本文轉(zhuǎn)載自MIT News，由ChatGPT翻譯，圖片來源于網(wǎng)絡(luò)

在2024QS世界大學(xué)排名中，麻省理工學(xué)院榮獲第1位

??? ?? 1611年，以行星運(yùn)動(dòng)定律著稱的約翰內(nèi)斯·開普勒提出了一個(gè)解決方案，解決了如何以最密集的方式排列相等大小的球體的問題。

? ? ?? 當(dāng)被問及如何堆放炮彈以占用最少的空間時(shí)，這位著名的天文學(xué)家研究了這個(gè)問題。

? ? ?? 開普勒得出的結(jié)論是一種所謂的面心立方格子結(jié)構(gòu)，這種方法通常用于雜貨店展示橙子：每個(gè)炮彈應(yīng)該停留在由直接在其下方排列成緊密的2x2正方形的四個(gè)炮彈留下的空腔中。

? ? ?? 然而，這只是一個(gè)猜測，直到近400年后才被密歇根大學(xué)的一位數(shù)學(xué)家證明。

? ? ?? 雖然這解決了關(guān)于均勻球體堆積的問題，但關(guān)于如何最優(yōu)地放置大小和形狀各異的3D物體的更普遍問題仍未解決。

? ? ?? 事實(shí)上，這個(gè)問題被歸類為NP難問題（NP-Hard Problem），這意味著它幾乎無法在合理的計(jì)算時(shí)間長度內(nèi)被準(zhǔn)確地解決。

? ? ?? 然而，有一些重大進(jìn)展，不是以數(shù)學(xué)證明的形式，而是通過一種新的計(jì)算方法，使這個(gè)先前難以處理的任務(wù)更易處理。

? ? ?? 由麻省理工學(xué)院和位于馬薩諸塞州梅德福德的研究人員組成的團(tuán)隊(duì)將這種技術(shù)稱為“密集的、無嵌套且可擴(kuò)展的光譜堆積”（SSP），團(tuán)隊(duì)將于2023年8月在世界上最大的計(jì)算機(jī)圖形和交互技術(shù)會議SIGGRAPH 2023上展示該研究成果。

? ? ?? SSP的第一步是確定用于填充固定容器的實(shí)體3D物體的順序。例如，一種可能的方法是以最大的物體開始，以最小的結(jié)束。下一步是將每個(gè)物體放入容器中。

? ? ?? 為了促進(jìn)這個(gè)過程，容器被“像素化”，這意味著它由微小的立方體或像素組成的3D網(wǎng)格表示，每個(gè)像素可能只有1毫米的立方體大小。該網(wǎng)格顯示哪些部分的容器已經(jīng)被填充，哪些是空的。

? ? ?? 要打包的物體也被像素化，再次由與容器中的像素大小相同的立方體組成。為了確定該物體的可用空間，算法然后在每個(gè)像素處計(jì)算一個(gè)稱為碰撞度量的量。

? ? ?? 它通過將物體的中心放置在容器的每個(gè)像素處，然后計(jì)算物體與之重疊或“碰撞”的占用像素的數(shù)量。該物體只能放置在重疊為零——即沒有“碰撞”的位置。

? ? ?? SSP算法的關(guān)鍵優(yōu)勢在于，它可以輕松地適用于不同大小和形狀的物體，以及不同形狀和大小的容器。

? ? ?? 此外，該算法可以通過添加更多的物體和容器來擴(kuò)展，因此它是可擴(kuò)展的。最后，該算法可以在合理的時(shí)間內(nèi)執(zhí)行，因?yàn)樗捎昧烁叨炔⑿谢姆椒ê涂焖俳朴?jì)算的技術(shù)。

? ? ?? 這種新的計(jì)算方法為許多應(yīng)用程序提供了方便，例如在制造業(yè)中進(jìn)行3D打印和裝載運(yùn)輸容器。

? ? ?? 此外，SSP算法還可以用于游戲開發(fā)、虛擬現(xiàn)實(shí)、建筑設(shè)計(jì)和城市規(guī)劃等領(lǐng)域，以幫助設(shè)計(jì)師和工程師優(yōu)化空間使用，同時(shí)保證物體的最佳布局。

原文鏈接：https://news.mit.edu/2023/chore-packing-just-got-faster-and-easier-0706