Trợ giúp về thuật toán để đặt phòng trên một không gian giới hạn

Question

Tôi đang làm việc trong một dự án thiết kế ngôi nhà nhỏ và một trong những phần quan trọng nhất của nó là phần mà người dùng có thể cung cấp một số thông tin về cách anh ấy muốn phòng của mình (ví dụ: một ngôi nhà với 10 x 10 mét, có một phòng khách 3x3, một nhà bếp 3x3, hai 4 x 5 phòng ngủ, và một phòng tắm 4x2), và sau đó chương trình tạo ra một bản đồ của ngôi nhà theo các requeriments thực hiện.

Hiện tại, tôi không lo lắng về việc vẽ bản đồ, chỉ sắp xếp các phòng theo cách mà chúng không chồng lên nhau (có, đầu ra có thể khá xấu xí). Tôi đã thực hiện một số tìm kiếm và thấy rằng những gì tôi muốn rất giống với packing problem, có một số algorithms xử lý vấn đề này khá tốt (mặc dù đó là vấn đề NP-complete). Tuy nhiên, sau đó tôi có thêm một hạn chế: người dùng có thể chỉ định "liên kết" giữa các phòng, ví dụ, anh ta có thể muốn một căn phòng phải có "cánh cửa" vào phòng tắm, phòng khách để trực tiếp đến nhà bếp, vv (có nghĩa là, các phòng phải được đặt cạnh nhau), và đây là nơi mà mọi thứ trở nên phức tạp.

Tôi khá chắc chắn rằng những gì tôi muốn định cấu hình NP-problem, vì vậy tôi yêu cầu các mẹo để xây dựng một triển khai tốt, nhưng không nhất thiết phải tối ưu. Ý tưởng tôi có là sử dụng đồ thị để thể hiện mối quan hệ giữa các phòng, nhưng tôi không thể tìm ra cách tôi có thể điều chỉnh các thuật toán đóng gói hiện có để phù hợp với hạn chế mới này. Ai giúp tôi với?

Answer 1

Tôi không có câu trả lời đầy đủ cho bạn, nhưng tôi có gợi ý: Ràng buộc kết nối của bạn sẽ tạo thành cái được gọi là planar graph (nếu không, giải pháp là không thể với một ngôi nhà một tầng)). Các phòng trong giải pháp cuối cùng sẽ tương ứng với các khu vực được bao quanh bởi các cạnh trong dual of the constraint graph, vì vậy tất cả những gì bạn cần làm sau đó được thực hiện kép, và điều chỉnh hình dạng của các cạnh của nó, mà không giới thiệu giao lộ, để phù hợp với kích thước. Lưu ý rằng bạn sẽ cần phải giới thiệu một đỉnh để đại diện cho 'bên ngoài' trong đồ thị ràng buộc, và đảm bảo nó không được bao quanh trong bộ đôi. Bạn cũng có thể cần phải giới thiệu các cạnh bổ sung trong đồ thị ràng buộc để đảm bảo tất cả các phòng đều được kết nối (và thêm các phòng cho hành lang, v.v.).

Answer 2

Bạn có thể tìm thấy this thú vị. Đó là một ngữ pháp để xây dựng biệt thự Palladian.

Để áp dụng một cái gì đó như vậy cho vấn đề của bạn, tôi sẽ có cách để xây dựng một cách ngẫu nhiên, và sau đó có thể thực hiện thay đổi ngẫu nhiên với nó, và sử dụng một thuật toán mô phỏng ủ.