Помощь по алгоритму размещения комнат на ограниченном пространстве

Question

Я работаю над проектом дизайна небольшого дома, и одна из его самых важных частей - это раздел, где пользователь может дать некоторую информацию о том, как он хочет, чтобы его комнаты (например, дом с 10 х 10 метров, имеющий 3x3 гостиная, кухня 3x3, две спальни 4x5 и ванная комната 4x2), а затем программа создает карту дома в соответствии с выполненными требованиями.

Пока я не беспокоюсь о том, чтобы рисовать карту, просто расположив комнаты так, чтобы они не пересекались (да, результат может быть довольно уродливым). Я уже провел некоторые поиски и обнаружил, что то, что я хочу, очень похоже на проблему упаковки , которая имеет некоторые алгоритмы , которые справиться с этой проблемой довольно хорошо (хотя это NP-полная проблема).

Но тогда у меня было еще одно ограничение: пользователь может указать «ссылки» между комнатами, например, он может пожелать, чтобы в комнате была «дверь» в ванную, а в гостиной - прямо на кухню. и т. д. (то есть комнаты должны располагаться рядом), и здесь все усложняется.

Я почти уверен, что то, что я хочу, настраивает NP-проблему, поэтому я прошу советы по созданию хорошей, но не обязательно оптимальной реализации. У меня есть идея использовать графики для представления отношений между комнатами, но я не могу понять, как я могу адаптировать существующие алгоритмы упаковки, чтобы соответствовать этому новому ограничению. Кто-нибудь может мне помочь?

Answer 1

У меня нет полного ответа для вас, но у меня есть подсказка: ваши ограничения подключения будут формировать то, что известно как планарный граф (если они этого не делают, решение невозможнос одноэтажным домом).Помещения в конечном решении будут соответствовать областям, заключенным в ребра в графе графа ограничений , поэтому все, что вам нужно сделать, - это взять упомянутый сдвоенный элемент и отрегулировать форму его ребер, не вводя пересечений,чтобы соответствовать ограничениям размеров.Обратите внимание, что вам нужно будет ввести вершину для представления «снаружи» в графе ограничений и убедиться, что она не окружена в дуале.Вам также может понадобиться ввести дополнительные ребра в график ограничений, чтобы убедиться, что все комнаты соединены (и добавить комнаты для прихожих и т. Д.).

Answer 2

Вы можете найти это интересным. Это грамматика для строительства палладийских вилл.

Чтобы применить что-то подобное к вашей проблеме, я мог бы создать ее случайным образом, а затем иметь возможность вносить в нее случайные изменения и использовать алгоритм имитации отжига.