最小化頂點距離的算法 - 矮人要塞

我玩Dwarf Fortress遊戲。我面臨的主要挑戰是有效設計堡壘的佈局。這意味着，每個工業流程應儘可能密集，以儘量減少行駛距離。最小化頂點距離的算法 - 矮人要塞

一個例子可以是食品工業 Food Industry 。每個灰色橢圓代表一棟建築物。每個白色矩形代表建築物的產品。

我的目標是要找到算法，將分佈在二維網格中的建築物爲，使得這些建築之間的距離是在這個意義上，他們是如何連接的最小。這意味着fishery和loom可以相距很遠，但loom和farmer's應儘可能接近。

目前我已經考慮使用一些現成的軟件來模擬佈局，但是算法的一些提示會很好。

目前我正在考慮一些力導向算法，但我不確定離散電網的要求。

問題的形式化：是否有一個Force Draw Graph算法在離散座標系下工作？

UPDATE：我發現在執行AS3的Force draw algorithm的（網頁包含JS版本太多）。我會嘗試將其轉換爲離散版本。但我有一些懷疑它會起作用...

UPDATE2：在評論中請求了一些進一步的限制。它們是：每個建築物都佔用虛擬網格上的單個單元格。建築物可以在相鄰的單元格上。建築物不能堆疊/重疊。（PS：在遊戲中，每座建築物的尺寸都是一定的，通常是3x3，但我想保持這個問題更一般，以便採取更多方法）。

2014-01-23 jnovacho

每棟建築是否只佔用一個格子的一個平方？現在你在任何邊長上都沒有下界，所以最佳解決方案就是堆疊在彼此之上的所有東西。 –

建築物佔用3x3平方，幾種類型的遊戲中有5x5尺寸的網格單位。但是爲了一般性，我們假設每個建築物可以佔據單個網格單元並且建築物不能堆疊。 – jnovacho

我的猜測是，這個問題有太多方面需要爭論到任何現有的算法。我的直覺說，某種形式的模擬退火方法在這裏最適合。 –

你幾乎試圖解決一個佈局規劃問題，在您試圖最小化總「連接」長度的一個實例。大多數這些問題都是NP難題的例子，其中一些問題有僞多項式運行時算法。

有一種特殊情況下，您可能會感興趣的是，實際上可以在多項式時間內完全解決：如果要提前知道要放置的「盒子」或建築物的相對位置。

有關如何解決此特定情況的完整詳細信息，請參閱此tutorial關於斯坦福大學的第6章第6.1節中的第幾個編程，標題爲「樓層規劃」。另一個website還包括實現和解決問題的MATLAB代碼（在第8章幾何編程下）。

2014-01-23 21:31:31 ldog

我剛剛瀏覽了您鏈接的論文，並認爲它不起作用。因爲在我的情況下，A連接到B，不會說出他們的相對位置，反之亦然。 – jnovacho

是的，但我想我在這裏說的是，除非你聲明每個人相對於另一個人的相對位置，否則你有一個總體規劃實例，這個實例幾乎可以保證爲NP-hard。這裏暗示的建議是，找到一個合理的算法來預先強加相對位置，然後執行嚴格的優化問題。重複並繼續N個這樣的配置，直到達到所需的最小總連接長度。 – ldog

這可能是你感興趣的：http://academics.smcvt.edu/jellis-monaghan/papers/papers/research%20papers/E-MGLP06.pdf – ldog

所以我設法做了一些代碼，它解決了這個問題。這不是頂級產品，但它的工作。我計劃隨着時間的推移進行一些更新，但我沒有設定任何時間框架。

我的代碼使用模擬退火方法。成本函數基於總面積，邊的總長度和重疊。爲了測量距離，我使用出租車司機的度量標準，但這是一個可以改變的主題。

2014-01-30 19:26:08 jnovacho

你有沒有比較過其他方法？這是一個很酷的研究 - 如果你能改進最先進的技術，它會成爲一篇很棒的博客文章，甚至是一篇研究論文！ – AndyG

不，不是真的。但我正在考慮這個主題的未來發展。就在這一刻。 :) – jnovacho

回答