Оптимизировать 3D размещение комнат? - PullRequest
Новая
       26

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

4 голосов
/ 13 июля 2011

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

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

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

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

Ответы [ 2 ]

2 голосов
/ 14 июля 2011

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

2 голосов
/ 13 июля 2011

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

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

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