一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 764|回复: 6
收起左侧

[算法题] 请问这道FB面经题怎么做

[复制链接] |试试Instant~ |关注本帖
milanelllo13 发表于 2015-7-5 14:27:06 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 milanelllo13 于 2015-7-5 14:28 编辑

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.    (昨天在一位同学发的面经总结看到的)。想请教一下解法~  谢谢!

                                       
                                
                        
               

stellari 发表于 2015-7-5 14:48:18 | 显示全部楼层
这道题你得先确认“distance”是怎么定义的。比如:是Euclidean distance还是Taxicab distance ? 如果是后者的话,common point取(med(xi), med(yi))即可。其中med(Ni) 代表所有坐标点第N维上的值的中位数。

回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-5 14:52:51 | 显示全部楼层
stellari 发表于 2015-7-5 14:48
这道题你得先确认“distance”是怎么定义的。比如:是Euclidean distance还是Taxicab distance ? 如果是后 ...

谢谢!那如果是Euclidean distance 有不brute force的方法吗?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-5 16:00:55 | 显示全部楼层
milanelllo13 发表于 2015-7-5 14:52
谢谢!那如果是Euclidean distance 有不brute force的方法吗?

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

使用道具 举报

zhuli19901106 发表于 2015-7-6 00:18:37 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-6 00:23 编辑
stellari 发表于 2015-7-5 16:00
在Euclidean情况下,这样的点称为“几何中位点”,又叫“托里拆利点”。如果不加任何限制,无法用确定性 ...

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

使用道具 举报

readman 发表于 2015-7-6 03:14:21 | 显示全部楼层
本帖最后由 readman 于 2015-7-6 03:17 编辑
zhuli19901106 发表于 2015-7-6 00:18
看见这个猛然想起了POJ上的一道老题,当时搜的关键字是费马点。
http://poj.org/problem?id=2420
就是 ...

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

使用道具 举报

road 发表于 2015-7-6 04:33:25 | 显示全部楼层
Integer (quadratic)programming problem.
可以先用quadratic programming 快速搜索出一个大概的解 在周围grid point 线性寻找
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 02:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表