请问这道FB面经题怎么做

Given set of points in 2d grid space. Find a grid point such that sum of distance  from all the points to this common point is minimum.    （昨天在一位同学发的面经总结看到的）。想请教一下解法~  谢谢！

• 
  

                                       
                                
                        
               

这道题你得先确认“distance”是怎么定义的。比如：是Euclidean distance还是Taxicab distance ? 如果是后者的话，common point取(med(xi), med(yi))即可。其中med(Ni) 代表所有坐标点第N维上的值的中位数。

stellari 发表于 2015-7-5 14:48
这道题你得先确认“distance”是怎么定义的。比如：是Euclidean distance还是Taxicab distance ? 如果是后 ...

谢谢！那如果是Euclidean distance 有不brute force的方法吗？

milanelllo13 发表于 2015-7-5 14:52
谢谢！那如果是Euclidean distance 有不brute force的方法吗？

在Euclidean情况下，这样的点称为“几何中位点”，又叫“托里拆利点”。如果不加任何限制，无法用确定性的算法找到。一般只能借助各种逼近算法求近似值。不过具体到这道题，看样子“这个点必须在某个格点位置上”，或者甚至“这个点必须是某个set中的点”（是否如此要向面试官确认清楚）。在这些限制下，可能是有确定性的算法可以做的。

stellari 发表于 2015-7-5 16:00
在Euclidean情况下，这样的点称为“几何中位点”，又叫“托里拆利点”。如果不加任何限制，无法用确定性 ...

看见这个猛然想起了POJ上的一道老题，当时搜的关键字是费马点。
http://poj.org/problem?id=2420
就是用你说的随机算法，四个方向搜，一边不断选取更优解，一边缩小步长，直到符合精度要求为止。

zhuli19901106 发表于 2015-7-6 00:18
看见这个猛然想起了POJ上的一道老题，当时搜的关键字是费马点。
http://poj.org/problem?id=2420
就是 ...

这个, as far as i know...在set就不用离散化了吧.., 做个多边形, 圈起来, 然后三角化, 挨个试试...

Integer (quadratic)programming problem.
可以先用quadratic programming 快速搜索出一个大概的解 在周围grid point 线性寻找