Является ли эта комбинаторная задача оптимизации похожей на какую-либо известную проблему?

10

Проблема заключается в следующем:

У нас есть двумерный массив / сетка чисел, каждое из которых представляет некоторую «выгоду» или «прибыль». У нас также есть два фиксированных целых числа и h (для «ширины» и «высоты».) И фиксированного целого числа n .whn

Теперь мы хотим наложить прямоугольников с размерами w × h на сетку так, чтобы общая сумма значений ячеек в этих прямоугольниках была максимизирована.nw×h

На следующем рисунке приведен пример двумерной сетки с наложенными на нее двумя такими прямоугольниками (на рисунке не показано оптимальное решение, только одно возможное наложение, где и n = 2 )w=h=2n=2

Пример сетки

Прямоугольники не могут пересекаться (в противном случае нам просто нужно найти оптимальное положение для одного прямоугольника и затем поместить все прямоугольники в это положение).

В приведенном выше примере общая сумма значений в ячейках будет 2+4.2+2.4+3.14+2.31.4+13.1

Похоже ли это на какую-либо известную проблему комбинаторной оптимизации? так что я могу начать читать и пытаться найти способы ее решить.

Еще немного предыстории для интересующихся:

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

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

Ура!

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

Ответы:

2

У моей последней формулировки был фатальный недостаток, который потребовал бы экспоненциального количества узлов «ограничения».

rwrr,rk=n

Николас Манкузо
источник
Это то направление, к которому я сейчас склоняюсь, я поэкспериментирую с этим и приму решение, если оно будет тем, которое я в итоге использую, ура.
пятьдесят восьмого
2

Вы можете сформулировать это как гигантский экземпляр целочисленного линейного программирования (ILP), а затем применить готовый решатель ILP (lp_solve, CPLEX и т. Д.). Они дадут вам лучшее решение, которое они могут найти. Учитывая размер вашего проблемного экземпляра, я не знаю, будет ли это достаточно эффективным, но это было бы легко попробовать.

xrrxr=1rxr=0rcrxrcrrrxr=nxr+xs1r,s

DW
источник
Как вы думаете, эта проблема NP-сложная? Я не уверен, что у него нет временного решения, и решатели ILP вряд ли смогут завершить даже экземпляры среднего размера.
РБ
1
@RB, я понятия не имею, является ли это NP-трудным. См. Мой комментарий под вопросом о динамическом программировании для моей первой мысли о том, как попытаться найти алгоритм за полиномиальное время (но я не знаю, будет ли полученный алгоритм в P или нет). Что касается того, что могут сделать решатели ILP, единственный способ выяснить это - попробовать - иногда их производительность может удивлять.
DW