Трудный медианный вопрос

Для n точек выберите точку в данном списке, так что сумма расстояний до этой точки минимальна по сравнению со всеми остальными.

Расстояние измеряется следующим образом.

Для точки (x, y) все 8 смежных точек имеют расстояние 1.

(x+1,y)(x+1,y+1),(x+1,y-1),(x,y+1),(x,y-1),(x-1,y)(x-1,y+1),(x-1,y-1)

ИЗМЕНИТЬ

Более четкое объяснение.

Функция foo определяется как

foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))

Найти точку x такую, что sum ([foo (x, y) для y в list_of_points)) минимальна.

Пример

Ввод:

12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6

Выход

-1 -6

Например: Расстояние между (4,5) и 6,7) равно 2.

Это можно сделать в O (n ^ 2) раз, проверив сумму каждой пары. Есть ли лучший алгоритм для этого?

Ответ 1

Обновить: иногда не удается найти оптимальный вариант, я оставлю это здесь, пока не найду проблему.

это O(n): nth - O (n) (ожидаемый, а не худший), итерация по списку - O (n). Если вам нужен строгий O(), то выберите средний элемент с сортировкой, но тогда это будет O (n * log (n)).

Примечание. Легко модифицировать его, чтобы вернуть все оптимальные точки.

import sys

def nth(sample, n):
    pivot = sample[0]
    below = [s for s in sample if s < pivot]
    above = [s for s in sample if s > pivot]
    i, j = len(below), len(sample)-len(above)
    if n < i:      return nth(below, n)
    elif n >= j:   return nth(above, n-j)
    else:          return pivot

def getbest(li):
    ''' li is a list of tuples (x,y) '''
    l = len(li)
    lix = [x[0] for x in li]
    liy = [x[1] for x in li]

    mid_x1 = nth(lix, l/2) if l%2==1 else nth(lix, l/2-1)
    mid_x2 = nth(lix, l/2)
    mid_y1 = nth(liy, l/2) if l%2==1 else nth(liy, l/2-1)
    mid_y2 = nth(liy, l/2)

    mindist = sys.maxint
    minp = None
    for p in li:
        dist = 0 if mid_x1 <= p[0] <= mid_x2 else min(abs(p[0]-mid_x1), abs(p[0]-mid_x2))
        dist += 0 if mid_y1 <= p[1] <= mid_y2 else min(abs(p[1]-mid_y1), abs(p[1]-mid_y2))
        if dist < mindist:
            minp, mindist = p, dist
    return minp

Он основан на решении одномерной задачи - для списка чисел найдем число, для которого минимальное суммарное расстояние.

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

Обновление: мой алгоритм nth кажется очень медленным, возможно, есть лучший способ переписать его, sort превосходит его с помощью < 100000 элементов, поэтому, если вы сравниваете скорость, просто добавьте sort(lix); sort(liy); и

def nth(sample, n):
    return sample[n]

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

import random
def example(length):
    l = []
    for x in range(length):
        l.append((random.randint(-100, 100), random.randint(-100,100)))
    return l

def bruteforce(li):
    bestsum = sys.maxint
    bestp = None
    for p in li:
        sum = 0
        for p1 in li:
            sum += max(abs(p[0]-p1[0]), abs(p[1]-p1[1]))
        if sum < bestsum:
            bestp, bestsum = p, sum
    return bestp

Ответ 2

Я могу представить схему лучше, чем O (n ^ 2), по крайней мере в общем случае.

Создайте quadtree из ваших входных точек. Для каждого node в дереве вычислите число и среднее положение точек внутри этого node. Затем для каждой точки вы можете использовать квадрант, чтобы вычислить его расстояние до всех остальных точек менее чем за время O (n). Если вы вычисляете расстояние от точки p до далекого квадранта node v, а v не перекрывает диагональю 45 градусов от p, то полное расстояние от p до всех точек из v легко вычислить ( для v, которые более горизонтальны, чем вертикально отделены от p, это просто v.num_points * |p.x - v.average.x| и аналогичным образом использует y координаты, если v преимущественно вертикально разделяется). Если v перекрывает одну из 45-градусных диагоналей, рекурсия на ее компонентах.

Это должно бить O (n ^ 2), по крайней мере, когда вы можете найти сбалансированную квадрину для представления своих точек.