直徑68cm和直徑58cm的圓內可以放多少個直徑10cm的圓?
本回答分三部分。第一部分將問題翻譯為最最佳化的數學語言,貼出了大圓內放 N=1~13 個小圓的小規模問題的最優解。第二部分改進演算法,求出了 R/r=6。8 和 5。8 的大圓內分別最多能放 N=37 個和 N=25 個小圓。第三部分進一步討論
的熱力學極限性質。
一、基本數學形式
這是一個非凸最佳化問題,要計算半徑為 R 的圓內最多可以放多少個半徑為 r 的圓,可以轉化為給定 N 個圓,在互不重疊的約束下最小化 R 的取值。由於半徑和圓的個數都是給定的,所以只有圓心座標共 2N 個變數。我們有
最小化 R,使得
且
且
這個問題需要從多個隨機初始構型開始梯度下降求解。我的 solver 算到 N=1~13 的 R/r 最小值和圓的堆疊方式如下圖:
圖 1 在大圓裡放 N 個小圓的最優解
從 N=1~13 可以看出,某些 N 值堆疊結構較為對稱(如 N=1~5, 7, 12 等),類似於元素週期表中的稀有氣體元素。而其它 N 值的堆疊結構對稱性破缺嚴重,類似於化學性質活潑的其它元素。這個幾何堆疊問題的複雜性提示了我們化學元素或者核結構這一類少體問題的複雜性的由來。
二、演算法改進與結果
前面的解法有 N 個圓就要引入
個硬約束,然後再反覆從隨機構型開始梯度下降。N 大到一定程度後,最最佳化的 solver 就處理不了了。後來我對這一部分進行改進,把
個硬約束變為加性的軟罰分,透過調節罰分的係數來控制約束的軟硬。於是目標函式變為
也就是說任意兩個不同的圓的圓心比
近產生交疊時有罰分,比
遠則沒有罰分。透過控制
的大小來調節約束的軟硬。梯度下降時取
左右,讓圓和圓之間交疊不多的時候可以擠過,便於收斂到最優解。從多個隨機初始構型開始梯度下降。找到一個解時,把
增加到
左右,即可完全除去交疊。下面給大家貼我計算的 N=25, 26, 36~38 時的 R/r 最小值和最優(較優)方案。因為 N 已經比較大,很難保證所找到的解就是嚴格最優的。
圖 2 一些更大規模的最優(較優)解
根據我的計算,R/r=5。8 時最多可放 N=25 個小圓,R/r=6。8 時最多可放 N=37 個小圓。
三、熱力學極限行為
如果圓的個數 N 進一步增大,堆疊行為會更加複雜混亂和無序嗎?答案是否定的。從前面的計算結果可以看出,隨著 N 的增大,小圓的佔空比
有增加的趨勢。而這一增加有一個理論的上界,就是 N=7 圖中的六角密排結構佔空比
。 注意 N=7 本身的佔空比並沒有達到這個理論值,因為邊緣處有較大的空隙。那麼在
極限下,佔空比
究竟是否會趨近於六角密排結構的
?一堆無序的鋼球在外框半徑 R 最小化的壓力下會自發排列成有序的晶格嗎?
為了驗證上述問題,我用 Matlab 寫了一個基於分子動力學演化的大規模 solver。 假設有 N=500 個小圓,它們任意兩個圓心距離小於 2r 時有彈性的排斥力,大於等於 2r 時無相互作用。用大圓半徑 R 作為一個邊界,讓 N=500 個小圓在圓形區域內挪動位置,直到任意兩個小圓的圓心距離都大於等於 2r 時,把大圓半徑 R 再減小 0。01。 一個非常樸素的演化程式,最後給出了 N=500 的一個較優解 R/r=24。27 如下:
圖 3 一種 N=500 個圓的堆疊方式
根據圖 3 的結果可以看出,遠離邊緣的地方確實都排成了六角密排晶格,局域來看的六度對稱性、長程式都出來了。邊緣附近為彌散層,密度達不到六角密排。但隨著
,我們有
,處於內部的小圓個數將遠多於處於邊界附近的。所以熱力學極限下的最佳堆疊方式竟然是有序的晶格。這個問題非常有意思吧~
下一篇:大齡少女的牙套日記