Лучший способ решить эту проблему с сеткой?

Question

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

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

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

Answer 1

Прямоугольник и круг очень разные.

Если вы ищете лучший прямоугольный регион, ваш метод грубой силы будет O(nk) (n = общее количество плиток, k = количество плиток внутри области), который можно легко улучшить до O(n) кэшируя некоторые частичные суммы вдоль строк / столбцов - это лучшее, что вы можете сделать, так как вы должны просмотреть каждую плитку хотя бы один раз. Если вам нужно делать это часто с изменяющимся регионом или фрагментами, пространственная структура данных будет быстрее, чем O (n), за счет некоторой начальной настройки.

В случае круга, если центр круга ограничен краями плитки, я не уверен, как бы вы улучшили свой алгоритм O(nk) грубой силы.

Однако, если круг действительно может быть где-нибудь , как вы заявили, вы не можете наивно грубо взломать каждую возможную позицию круга, потому что существует бесконечно возможное положение!

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

Answer 2

Для нахождения суммы в прямоугольнике в регулярной сетке, на самом деле есть простой алгоритм для этого в O (n).Пусть G - это сетка, а g (x, y) - значение в ячейке (x, y)

Пусть H - новая сетка, такая, что h (x, y) = сумма g (i, j) для всех я <= х;j <= y (вы можете сделать это за линейное время). </p>

Теперь сумма в прямоугольнике (x1, y1) .. (x2, y2) равна h (x2, y2) -h (x1, y2) -h (x2, y1) + h (x1, y1).

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

Answer 3

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

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

Возможно, я что-то упускаю, конечно.

Answer 4

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

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

Например, скажем, у вас есть только девять кругов в плане плана 3х3, и их суммы:

10 10 10
10  1  1
1   1  1

Тогда вы знаете, что самое большее, что может быть у любого круга, это 31, и круг из 31 должен перекрывать 4 круга в верхнем левом углу: 0,0 0,1, 1,0 и 1,1 (строка , col позиции сверху слева).

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

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