Минимизировать максимальное расстояние в манхэттене от точки до набора точек

Ответ 1

Существует точный, нетериративный алгоритм проблемы; как указал Кноте, расстояние Манхэттена является вращательно эквивалентным чебышевскому расстоянию, а P тривиально вычислимо для чебышевского расстояния как среднее из крайних координат.

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

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

Центр наименьшего охватывающего квадрата можно найти как центр самого маленького прямоугольника (который тривиально вычисляется как max и min координат). Существует бесконечное количество наименьших закрывающих квадратов, так как вы можете сдвинуть центр вдоль более короткого края минимального прямоугольника и по-прежнему иметь минимальный квадрат. Для наших целей мы можем просто использовать тот, центр которого совпадает с охватывающим прямоугольником.

Итак, в алгоритмической форме:

• Поворот и масштабирование системы координат путем присвоения x '= x/sqrt (2) - y/sqrt (2), y' = x/sqrt (2) + y/sqrt (2)
• Вычислить x'_c = (max (x'_i) + min (x'_i))/2, y'_c = (max (y'_i) + min (y'_i))/2
• Поворот назад с помощью x_c = x'_c/sqrt (2) + y'_c/sqrt (2), y_c = - x'_c/sqrt (2) + y'_c/sqrt (2)

Тогда x_c и y_c дают координаты P.

Ответ 2

Если приблизительное решение в порядке, вы можете попробовать простой алгоритм оптимизации. Вот пример, в 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.