棘手的中位数问题

Question

给定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(list_of_points中的y的[foo(x,y)])最小.

例

输入:

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

产量

-1 -6

例如:(4,5)和6,7之间的距离是2.

这可以通过检查每对的总和在O(n ^ 2)时间内完成.有没有更好的算法呢？

Answer 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