Для трех точек в 2D:
P1(x1,y1),
P2(x2,y2),
P3(x3,y3)
Мне нужно найти точку P(x,y), такую, что максимум манхэттенских расстояний
max(dist(P,P1),
dist(P,P2),
dist(P,P3))
будет минимальным.
Любые идеи об алгоритме?
Я бы предпочел бы точный алгоритм.
Существует точный, нетериративный алгоритм проблемы; как указал Кноте, расстояние Манхэттена является вращательно эквивалентным чебышевскому расстоянию, а P тривиально вычислимо для чебышевского расстояния как среднее из крайних координат.
Точки, достигаемые от P в пределах расстояния Манхэттена x, образуют алмаз вокруг P. Поэтому нам нужно найти минимальный алмаз, который охватывает все точки, а его центр будет P.
Если мы поворачиваем систему координат на 45 градусов, алмаз представляет собой квадрат. Поэтому проблему можно свести к нахождению наименьшего квадрата окружности точек.
Центр наименьшего охватывающего квадрата можно найти как центр самого маленького прямоугольника (который тривиально вычисляется как max и min координат). Существует бесконечное количество наименьших закрывающих квадратов, так как вы можете сдвинуть центр вдоль более короткого края минимального прямоугольника и по-прежнему иметь минимальный квадрат. Для наших целей мы можем просто использовать тот, центр которого совпадает с охватывающим прямоугольником.
Итак, в алгоритмической форме:
Тогда x_c и y_c дают координаты P.
Если приблизительное решение в порядке, вы можете попробовать простой алгоритм оптимизации. Вот пример, в Python
import random
def opt(*points):
best, dist = (0, 0), 99999999
for i in range(10000):
new = best[0] + random.gauss(0, .5), best[1] + random.gauss(0, .5)
dist_new = max(abs(new[0] - qx) + abs(new[1] - qy) for qx, qy in points)
if dist_new < dist:
best, dist = new, dist_new
print new, dist_new
return best, dist
Объяснение: Мы начинаем с точки (0, 0) или любой другой случайной точки и изменяем ее несколько тысяч раз, каждый раз сохраняя лучшее из новой и ранее лучшей точки. Постепенно это будет приблизительно соответствовать оптимальному.
Примечание, которое просто выбирает среднее или медианное из трех точек, или решение для x и y независимо не работает при минимизации максимального расстояния в манхэттене. Противопоставление: рассмотрите точки (0,0), (0,20) и (10,10) или (0,0), (0,1) и (0,100). Если мы выберем среднее из наиболее разделенных точек, это даст (10,5) для первого примера, и если мы возьмем медиану, это будет (0,1) для второго примера, у которого оба имеют более высокий максимальный манхэттен чем оптимальный.
Обновление: Похоже, что решение для x и y независимо, а среднее значение самых отдаленных точек действительно работает, при условии, что выполняется некоторая предварительная обработка и постобработка, как указано thiton.