Я работаю над проектом дизайна небольшого дома, и одна из его наиболее важных частей - это раздел, где пользователь может дать некоторую информацию о том, как он хочет свои комнаты (например, дом размером 10 х 10 метров, имеющий 3x3 гостиная, 3x3 кухня, две 4 x 5 спален и ванная 4x2), а затем программа создает карту дома в соответствии с выполненными заказами.
В настоящее время я не беспокоюсь о том, чтобы рисовать карту, просто устраивая комнаты таким образом, чтобы они не перекрывались (да, выход может быть довольно уродливым). Я уже сделал некоторые поиски и обнаружил, что то, что я хочу, очень похоже на проблему упаковки , в которой есть некоторые , которые справляются с этой проблемой довольно хорошо (хотя это проблема NP-complete).
Но тогда у меня было еще одно ограничение: пользователь может указать "ссылки" между комнатами, например, он может пожелать, чтобы в комнате должна быть "дверь" в ванную комнату, в гостиную - прямо на кухню, и т.д. (т.е. комнаты должны быть размещены бок о бок), и здесь все усложняется.
Я уверен, что то, что я хочу, настраивает NP-проблему, поэтому я прошу советов по созданию хорошей, но не обязательно оптимальной реализации. Идея, которую я имею, - использовать графики для представления отношений между комнатами, но я не могу понять, как я могу адаптировать существующие алгоритмы упаковки, чтобы соответствовать этому новому ограничению. Кто-нибудь может мне помочь?
