Проблема заключается в следующем:
У нас есть двумерный массив / сетка чисел, каждое из которых представляет некоторую «выгоду» или «прибыль». У нас также есть два фиксированных целых числа и h (для «ширины» и «высоты».) И фиксированного целого числа n .
Теперь мы хотим наложить прямоугольников с размерами w × h на сетку так, чтобы общая сумма значений ячеек в этих прямоугольниках была максимизирована.
На следующем рисунке приведен пример двумерной сетки с наложенными на нее двумя такими прямоугольниками (на рисунке не показано оптимальное решение, только одно возможное наложение, где и n = 2 )
Прямоугольники не могут пересекаться (в противном случае нам просто нужно найти оптимальное положение для одного прямоугольника и затем поместить все прямоугольники в это положение).
В приведенном выше примере общая сумма значений в ячейках будет
Похоже ли это на какую-либо известную проблему комбинаторной оптимизации? так что я могу начать читать и пытаться найти способы ее решить.
Еще немного предыстории для интересующихся:
До сих пор единственными идеями, которые у меня были, являются либо жадный алгоритм (который найдет наилучшее местоположение для первого прямоугольника, затем найдет неперекрывающуюся область для второго прямоугольника и т. Д.), Либо некоторая метаэвристика, такая как генетические алгоритмы.
На самом деле я хочу решить эту проблему с помощью сетки, содержащей около миллиона ячеек и десятки тысяч (или даже сотен тысяч) прямоугольников, хотя нет необходимости решать ее в течение короткого времени (т.е. это было бы приемлемо для алгоритм занимает несколько часов или даже дней.) Я не ожидаю точного решения, но я хочу получить такое, которое будет как можно лучше с учетом этих ограничений.
Ура!
источник
Ответы:
У моей последней формулировки был фатальный недостаток, который потребовал бы экспоненциального количества узлов «ограничения».
источник
Вы можете сформулировать это как гигантский экземпляр целочисленного линейного программирования (ILP), а затем применить готовый решатель ILP (lp_solve, CPLEX и т. Д.). Они дадут вам лучшее решение, которое они могут найти. Учитывая размер вашего проблемного экземпляра, я не знаю, будет ли это достаточно эффективным, но это было бы легко попробовать.
источник