Лучший способ эффективного поиска регионов с высокой плотностью

Ответ 1

Алгоритм 1

Создайте 2D-массив размером 500x500, где каждая ячейка содержит счетчик количества частиц в этой ячейке. Затем сверните этот массив с ядром 50x50, результирующий массив будет иметь количество частиц в области 50x50 в каждой ячейке. Затем найдите ячейку с наибольшим значением.

Если вы используете поле 50x50 в качестве региона, ядро ​​можно разложить на две отдельные свертки, по одному для каждой оси. Результирующий алгоритм - это O (n ^ 2) пространство и время, где n - ширина и высота 2D-пространства, которое вы ищете.

Напоминаем, что одномерная свертка с функцией вагона может быть завершена в O (n) времени и пространстве, и это можно сделать на месте. Пусть x (t) - вход для t = 1..n, и y (t) - выход. Определим x (t) = 0 и y (t) = 0 для t < 1 и t > n. Определите, что ядро ​​f (t) равно 1 для 0..d-1 и 0 в другом месте. Определение свертки дает нам следующую формулу:

y (t) = sum я x (t-i) * f (i) = sum я = 0..d-1 x (t-i)

Похоже, что для этого требуется время O (n * d), но мы можем переписать его как повторение:

y (t) = y (t-1) + x (t) - x (t-d)

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

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

Это то же самое, что и решение justhalf, за исключением разложенной свертки, размер области не влияет на скорость алгоритма.

Алгоритм 2

Предположим, что существует хотя бы одна точка. Не ограничивая общности, рассмотрим двумерное пространство как всю плоскость. Пусть d - ширина и высота области. Пусть N - число точек.

Лемма: Существует область максимальной плотности, имеющая точку на левом ребре.

Доказательство.. Пусть R - область максимальной плотности. Пусть R '- одна и та же область, переведенная справа на расстояние между левым краем R и самой левой точкой в ​​R. Все точки в R также должны быть в R', поэтому R 'также является областью максимальной плотности.

Алгоритм

• Вставьте все точки в дерево K-D. Это можно сделать в O (N log ² N) времени.

• Для каждой точки рассмотрим область ширины d и высоту 2 d, где точка центрирована на левом краю области. Вызовите эту область R.

• Запросить дерево KD для точек в области R. Вызвать это множество S. Это можно сделать в O (N ^1/2 + | S |) времени.

• Найдите субрегион dxd из R, содержащий наибольшее количество точек в S. Это можно сделать в O (| S | log | S |) раз, отсортировав S по y-координате и затем выполнив линейное сканирование.

Результирующий алгоритм имеет время O (N ^3/2 + N | S | log | S |).

Сравнение

Алгоритм # 1 превосходит алгоритм №2, когда плотность высокая. Алгоритм №2 только выше, когда плотность частиц очень низкая, а плотность, при которой алгоритм №2 превосходит по мере увеличения общего размера платы.

Заметим, что непрерывный случай можно считать равным нулю, и в этот момент работает только алгоритм № 2.

Ответ 2

Я не знаю, какой метод грубой силы вы используете, но самый грубый способ был бы O(n^2 d^2), итерируя каждую область в O(n^2) времени, затем подсчитайте количество частиц в этой области в O(d^2) время, когда d - размер вашего региона.

Эта проблема точно такая же, как эта проблема: Rat Attack, так как область области фиксирована, и поэтому плотность такая же, как и счет, для которого решение O(n^2 + k*d^2), где

• n - размер всей области (длина стороны)
• k - число частиц
• d - размер каждой области (длина стороны)

по этому алгоритму:

• Для каждой частицы обновите подсчет областей O(d^2), затронутых этой частицей
• Итерации по всем O(n^2) возможным областям, найдите максимум

как показано в этот код, я скопирую соответствующую часть здесь для справки:

using namespace std;

int mat [1024 + 3] [1024 + 3]; // Here n is assumed to be 1024

int main ()
{
    int testCases; scanf ("%d", &testCases);

    while ( testCases-- ) {

        Set(mat, 0);

        int d; scanf ("%d", &d); // d is the size of the region
        int k; scanf ("%d", &k); // k is the number of particles

        int x, y, cost;

        for ( int i = 0; i < k; i++ ) {
            scanf ("%d %d %d", &x, &y, &cost); // Read each particle position

            // Update the count of the d^2 region affected by this particle
            for ( int j = max (0, x - d); j <= min (x + d, 1024); j++ ) {
                for ( int k = max (0, y - d); k <= min (y + d, 1024); k++ ) mat [j] [k] += cost;
            }
        }

        int resX, resY, maxi = -1;

        // Find the maximum count over all regions
        for ( int i = 0; i < 1025; i++ ) {
            for ( int j = 0; j < 1025; j++ ) {
                if ( maxi < mat [i] [j] ) {
                    maxi = mat [i] [j];
                    resX = i;
                    resY = j;
                }
            }
        }

        printf ("%d %d %d\n", resX, resY, maxi);

    }
    return 0;
}

Я поместил свои комментарии в код, чтобы объяснить это вам.

Ответ 3

Разделите область на 1000x1000 и подсчитайте количество частиц в каждом (перекрывающемся) 2x2. Вы можете разбить их просто путем нормализации 0..1, масштабирования 0..999 и отбрасывания до целого. Графы могут быть легко сохранены как 2D-массив целых чисел (ushort, uint или ulong... mmmm tea). Это эквивалентно простому пространственному пространственному разбиению, используемому при широкополосном обнаружении столкновения.