Оптимизировать 3D размещение комнат?

Question

Дан график, где узлы представляют комнаты 3х3х1, а вершины представляют потребность в близости. Как их разместить в трехмерном пространстве, чтобы оптимизировать общую близость?

Пример (случайная) структура данных:

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

(Я не совсем уверен, где мне следует задавать этот вопрос, поскольку он отличается от того, что я вижу в stackru. Меня интересуют программные решения / эвристические алгоритмы.)

Answer 1

Пахнет как дальний родственник проблемы с упаковкой 3D- бина, которая является NP-полной. Попробуйте построить эвристику (сначала подходит, уменьшится лучше всего, ...), а затем метаэвристику (поиск по Табу, имитация отжига, генетические алгоритмы, ...). Для этого существует программное обеспечение с открытым исходным кодом, такое как Drools Planner, openTS, jgap,...

Answer 2

Я полагаю, вы хотите смежности.

В обратном поиске ведите очередь комнат, упорядоченную по количеству других комнат, к которым они подключены на графике (эвристика с самой ограниченной переменной). Затем для каждой комнаты в очереди:

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