優化房間的3D放置？

鑑於其中的節點代表3x3x1房間一個圖，頂點表示需要親近。他們應該如何放置在3D空間以優化整體親密度？優化房間的3D放置？

例（randomish）數據結構：

{ 
    room1: [room2, room3], 
    room2: [room1, room4], 
    room3: [room5], 
    room4: [room2, room5, room1], 
    room5: [] 
}

（我不是很確定，我應該會問這個問題，因爲它是從最我看到計算器不同我感興趣的編程解決方案/啓發式算法。。）

來源

2011-07-13 Annan

你如何計算兩個房間的親密度？這是兩個街區之間的最小距離嗎？你使用什麼規範？ – Simon

實際上，我打算應用這個來設計一個矮人堡壘佈局。目前，我想知道在開始思考樓梯間和不同尺寸的房間之前它是如何完成的。靠近最好的特點是房間中心之間的距離。 – Annan

（嗯，*房間中心之間距離的切比雪夫） – Annan

我想，你希望相鄰。

在backtracking search，保持室通過它們多少其他房間中的曲線圖（最約束變啓發式）連接到命令隊列。然後，對於隊列中的每個房間：

確定可能的網格位置並選擇其中的一個;
在一個循環中，確定任何其他房間是否存在現在只能在一個地方，把它們放在那裏和從隊列中（forward checking）刪除它們;
如果任何失敗之前的步驟，回溯到最後的選擇點（撤消更改到網格）。

來源

2011-07-13 09:32:24

感謝您的回答，我要讀這個。如果鄰接不可行，即有一箇中央房間需要靠近太多的其他房間。回溯搜索是否能夠找到總體最近房間的佈局？ – Annan

不是我繪製的算法;添加這種「偏好約束」可能意味着在應用回溯搜索之前，您必須從根本上更改問題表示。請查看第三版中的[Russell＆Norvig]（http://aima.cs.berkeley.edu/）第6章。 –

聞起來像一個3D bin packing problem，這是一個NP完全的遠房親戚。嘗試構建啓發式算法（首先擬合，最佳擬合減少，...），然後進行metaheuristics（禁忌搜索，模擬退火，遺傳算法......）。有那裏的開源軟件，如Drools Planner，openTS，jgap，...

來源

2011-07-14 08:43:06

優化房間的3D放置？

回答

相關問題