假設我有一個完整的無向圖G，每條邊都有一段距離。具有長度l的邊（u，v）的含義是「點u和v不可能比l更接近彼此」。我的目標是將這個圖的節點放在一個平面上，這樣就不會違反這些距離約束，並且這些點的凸包的總面積最小。舉個例子，假設我有一堆電子元件要放在芯片上，每個元件都會產生一定數量的電干擾。如果我把組件放得太近，他們會開始互相干擾，導致整個系統無用。考慮到每個點應該距離每個點最小距離，將這些元件放在芯片上的最節省空間的方式是什麼？飛機上的密集點？
我不知道如何開始思考這個問題。我也不知道這個問題可能會如何推廣到更高維的情況（包裝點進入超平面）。有誰知道解決這個問題的好方法嗎？
我有一個最佳的解決方案，但你不會喜歡它:)。
讓我們的標籤我們的節點X ，X ，...，X ñ。令B =最大 I，J <Ñ（DIST（X 我，X Ĵ）），其中DIST（X 我，X Ĵ）是x 我和X之間的最小距離 j。對於每個i，將節點x i放置在位置（0，i * B）處。現在每個節點至少與所有其他節點相距B，並且凸包的面積爲0.
這裏的真正意義在於，最小化單獨凸包的面積會給您一個無意義的解決方案。一個可能更好的措施是凸包的直徑。
我猜這將很難找到最佳算法。如果事實證明這是一個NP難題，我不會感到驚訝。但是，如果您對能夠提供體面解決方案的實用算法感興趣，我建議您查看force-based graph drawing algorithms。
這裏是一般的想法（一些更高的數學將出現）。它推廣到任何數量的維度。
構造一個函數f，它爲每個節點佈局分配一個值 - 一個您想要最小化的值。在你的情況下，函數可以計算給定佈局的凸包的面積+對於沒有滿足的每個約束的大懲罰。或者它可以是一個更簡單的函數g，它合理地近似於前者：簡而言之，當f變小時，我們希望g變小，反之亦然。選擇一個相對簡單的函數是很好的，因爲你需要計算它的偏導數（關於節點的座標）。
現在讓我們假設您有100個節點，並且您希望將它們放在3D中。這意味着您有300個未知數（每個節點的100個節點乘以3個座標）。功能f是從R到R的函數，理想情況下我們希望找到它是全局最小值。更現實的說，足夠深的當地最低限度就足夠了。
存在衆所周知的用於找到這樣的最小值的數值算法，例如：Conjugate gradient,BFGS。好的是，你並不需要詳細瞭解它們，這些算法在很多語言中都可以實現。你所要做的就是提供一個計算f(x)和f'(x)的方法，該算法對算法請求的任何x以及初始佈局x₀。
這是2D bin packing problem（這是NP難）與額外的限制。我聽說模擬退火表現非常好，電路/芯片設計。
我實際上是looking for real-world test-data of a big bin packing problem對於Drools Planner。
你想查找圖形繪製。在這種情況下，強制導向的技術可以給你一個很好的結果。 – novalis 2011-01-24 21:54:14
@ novalis-我意識到這些技術，但據我所知，沒有任何證據表明這些技術可以提供最佳解決方案（甚至任何接近最佳解決方案的解決方案）。我正在尋找一個算法，這個算法可以在一些可預測的最優化因子內。 – templatetypedef 2011-01-24 21:59:07
而不是凸包的面積（每克里斯·霍普曼的答案），你可能想要最小化類似長寬比和從質心到最遠點的半徑的乘積。我假設這是有意義的，你的圖形是完全密集的 - 你沒有可以在相同位置堆疊的組件？ – Novelocrat 2011-01-25 05:09:00