ПРОБЛЕМА ПЕРЕДЕЛА ПЕРЕДАЧА

Question

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

Подводя итог, что мне нужно сделать, предположим, что у меня есть место, похожее на следующее:

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

в котором каждая угловая ячейка составляет 4х4, а центральная - 3х3 (так что оставшиеся - 3x4 и 4x3). Тогда у меня есть набор элементов, которые можно разместить внутри этих блоков, которые могут варьироваться от 1x1 до 3x3 (я не думаю, что какое -либо 4x4 еще не нужно, но это ничего не должно ничего изменить). Конечно, эти элементы не могут пересечь линии и должны полностью лежать в одном блоке.

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

Бонусный вопрос: предполагая другие блоки в дополнение к этим 9 (может быть, другие 3-4), как я мог расставить приоритеты по сравнению с новыми? (Я имею в виду, просто не использует дополнительный блок, пока не будет достигнут порог заполнения).

Конечно, я ищу общую идею, без реализации :)

Answer 1

Это 2d Корзина корзина Проблема выглядит так, как это Np тяжело.

Вот пара ваших вариантов:

• Грубая сила или, еще лучше, ветвь и связан. Вообще не масштабируется (вообще!), Но найдет вам оптимальное решение (возможно, не в нашей жизни).

• Детерминированный алгоритм: сортируйте блоки по наибольшему размеру или самой большой стороне и пройдите через этот список один за другим и назначите ему лучшее оставшееся место. Это закончит очень быстро, но решение может быть далеко не оптимальным (или осуществимым). Вот хорошая картина, показывающая пример, что может пойти не так. Но если вы хотите сделать это просто, это путь.

• Мета-гивритика, начиная с результата детерминированного алгоритма. Это даст вам очень хороший результат в разумное время, лучше, чем люди. В зависимости от того, сколько времени вы его даете, и с трудностью проблемы, она может быть или не быть оптимальным решением. Есть пара библиотек, например Слюни планируют (Java с открытым исходным кодом).