幫助算法在有限的空間上放置房間

我正在研究一個小房子的設計項目，其中最重要的部分之一是用戶可以提供有關他希望自己的房間的某些信息的部分（例如，一個10×10米的房子，一個3x3的客廳，一個3x3的廚房，兩個4x5的臥室和一個4x2的浴室），然後程序會根據所做的要求生成房屋地圖。現在，我並不擔心繪製地圖，只是以不重疊的方式排列房間（是的，輸出可能非常難看）。現在，我並不擔心繪製地圖，只是以不重疊的方式排列房間（是的，輸出可能非常難看）。我已經做了一些搜索，發現我想要的與packing problem非常相似，其中有一些algorithms，它很好地處理了這個問題（儘管它是一個NP完全問題）。幫助算法在有限的空間上放置房間

但是後來我又有了一個限制：用戶可以在房間之間指定「鏈接」，例如，他可能希望一個房間必須有一個「門」的浴室，客廳要有直接的廚房等（也就是說，房間必須並排放置），這是事情變得複雜的地方。

我很確定我想要配置一個NP問題，所以我要求提示構建一個好的，但不一定是最佳的實現。我的想法是使用圖表來表示房間之間的關係，但我無法瞭解如何使現有的打包算法適應這種新的限制。誰能幫我？

來源

2011-06-29 Luiz Rodrigo

我相信這類問題的一般名稱是約束優化*，約束滿足*的一個子集。這可能有助於您的搜索。我也懷疑你是否真的想解決這個問題;還有更多東西進入房間定位（例如，早晨的太陽撞到哪一側，所有交流管道，管道等都在哪裏運行？） – derobert

事實上，製作一個時髦的用戶界面可能會更好讓用戶放置自己的房間，同時提醒他們自己的限制。 – bdonlan

如果用戶指定的約束太多，並且您沒有尋找最佳解決方案，則應該使用「建設性」算法。根據約束條件逐步逐個建立，如果不起作用，則返回並更改以前的選擇 –

我沒有一個完整的答案給你，但我確實有一個提示：你的連接限制將形成所謂的planar graph（如果他們不這樣做，解決方案是不可能的，一個單層住宅）。最終解決方案中的房間將與dual of the constraint graph中的邊緣所包圍的區域相對應，因此，您所需要做的就是採取雙重對比，並調整其邊緣的形狀，而不引入交叉點，以適應尺寸限制。請注意，您需要在約束圖中引入一個頂點來表示「外部」，並確保它不會包含在對偶中。您可能還需要在約束圖中引入額外的邊以確保連接所有房間（併爲走廊等添加房間）。

來源

2011-06-29 19:49:12 bdonlan

你可能會覺得this有趣。這是建造帕拉第奧別墅的語法。

要應用類似的東西到你的問題，我會有辦法隨機構造一個，然後能夠隨機更改它，並使用模擬退火算法。

來源

2011-06-29 20:46:16

幫助算法在有限的空間上放置房間

回答

相關問題