(Я не вижу очевидного лучшего алгоритма или структуры данных для этого; это может быть один из тех вопросов, когда они хотят услышать ваш мыслительный процесс больше, чем ваше решение.)
Из двух очевидных подходов:
- Итерация по всем локациям и измерение расстояния до всех событий для расчета стоимости локации
- Перебор всех событий и добавление к стоимости мест в круге вокруг них
последний представляется наиболее эффективным. Вы никогда не смотрите на бесполезные места, и чтобы распределить ценность, вам нужно только вычислить один октант круга и затем отразить его для остальной части круга.
Вам, очевидно, нужно пространство памяти для хранения прямоугольной сетки значений местоположений, так что это соображение. И если вы заранее не знаете размер города, вам придется один раз повторить ввод, чтобы выбрать размер сетки. (Напротив, первый метод почти не требует места в памяти).
В зависимости от сложности, вы будете повторять события k , и для каждого из них вам нужно будет рассчитать количество мест, связанных с r 2. . Вы можете сохранять максимум, пока вы перебираете события, поэтому поиск максимального значения не увеличивает сложность времени. (В первом методе вам, очевидно, придется вычислять все те же значения w / (d + 1) , без преимущества зеркального отражения одного октанта круга плюс как минимум расстояние от всех дополнительные бесполезные локации.)
Если количество событий и пострадавших районов вокруг них невелико по сравнению с размером города, преимущество второго метода очевидно. Если существует большое количество событий и / или r велико, разница может быть незначительной.
Могут быть некоторые математические приемы, чтобы решить, какие события проверять первыми, какие игнорировать, или когда останавливать, но для этого вам нужно знать некоторые подробности, например, могут ли два события произойти в одном месте. Там может, например, быть преимуществом в сортировке событий по стоимости и в первую очередь смотреть на события с наибольшей ценностью, потому что в какой-то момент может стать очевидным, что события за пределами «горячей точки» вокруг текущего максимума могут быть проигнорированы. Но многое будет зависеть от специфики данных.
ОБНОВЛЕНИЕ
Распределяя ценность события по местам вокруг него, вам, очевидно, не нужно рассчитывать расстояния более одного раза; например если r = 3 , вы сделаете эту сетку 7 & times; 7 с весами 1 / d :
0 0 0 0.250 0 0 0
0 0.261 0.309 0.333 0.309 0.261 0
0 0.309 0.414 0.500 0.414 0.309 0
0.250 0.333 0.500 1.000 0.500 0.333 0.250
0 0.309 0.414 0.500 0.414 0.309 0
0 0.261 0.309 0.333 0.309 0.261 0
0 0 0 0.250 0 0 0
Который содержит только восемь разных значений. Затем вы использовали бы его в качестве шаблона для наложения поверх сетки в месте события, а также умножили стоимость события на весы и добавили их к стоимости каждого местоположения.
ОБНОВЛЕНИЕ
Я рассмотрел возможность того, что только места с событием могут быть местоположением с наивысшей ценностью, и без ограничения r это будет правдой. Это сделало бы проблему совершенно другой. Тем не менее, легко создать контрпример; рассмотреть, например, эти события:
- - 60 - -
- - - - -
60 - - - 60
- - - - -
- - 60 - -
Если предел r больше 4, они будут создавать эту стоимость в местах вокруг них:
61.92 73.28 103.3 73.28 61.92
73.28 78.54 82.08 78.54 73.28
103.3 82.08 80.00 82.08 103.3
73.28 78.54 82.08 78.54 73.28
61.92 73.28 103.3 73.28 61.92
А места с наивысшей ценностью 103,3 - это места событий. Однако, если мы установим предел r = 2 , мы получим:
40 30 60 30 40
30 49.7 30 49.7 30
60 30 80 30 60
30 49.7 30 49.7 30
40 30 60 30 40
А в центре, где нет события, теперь находится максимум с ценностью 80.
Это означает, что необходимо учитывать места без событий, по крайней мере, в пределах выпуклой оболочки вокруг скопления событий. Конечно, если обнаружено, что два кластера событий превышают 2 & times; На расстоянии друг от друга они могут рассматриваться как отдельные зоны. В этом случае вам не нужно будет создавать сетку для всего города, а отдельные меньшие сетки вокруг каждого кластера.
Таким образом, общий подход будет:
- Создать квадратную сетку размером 2 & times; r с весами.
- Разделить события на кластеры с расстоянием, превышающим 2 & times; R между ними.
- Для каждого кластера событий создайте наименьшую прямоугольную сетку, которая соответствует событиям.
- Для каждого события используйте сетку весов, чтобы распределить ценность по прямоугольной сетке.
- Добавляя ценность для местоположений, следите за максимальной стоимостью.