算法 我要抢电梯!!!

zlx_star · 2012年07月23日 · 最后由 jyz19880823 回复于 2012年07月24日 · 2901 次阅读

请原谅,题目起得有点那啥了,不过我想寻求大家的帮助是真心的。

今天下班等电梯的时候。看到大厦里面的五个电梯,突然鬼使神差地想到一个问题:怎样才能最快抢到电梯。(我承认我不够绅士!😄

进入正题,问题抽象出来就是:平面上有五个点,求到这五个点距离总和最近的点?

直觉告诉我:最近的那个点应该是包含这五个点的最小圆的圆心。但是为什么呢?

回来的路上一直想这个问题,导致错过了公交车。跪求思路~~~

我直觉 lz 的直觉不靠谱. 因为有两点可以再确定的最小圆内"活动" 常规解法是 求 f(x,y)= for i in N (x-xi)^2 + (y-yi)^2 的极小值。 二元函数极值

#1 楼 @yeerkunth 数学都还给老师了,能通俗点解释下吗?

@zlx_star 一个特列可以推到你的直觉,五个点中,其中四点呈正方形,第五点和前面四点任意一点重合,落在正方形的一个角。根据你的直觉目标点是正方形的对角线交点.可是有两点重合的那个点作为目标点对角线交点更短。可以自己画下就知道了. 通俗来讲就是求重心. 希望这篇对你有帮助。

你这个就是最短路径问题,学算法时有学过,Dijkstra 算法。 而且这个算法是很有实际用处的,比如: 电子机械手焊接电路板上的多个点,求得最短路径,可以最大化焊接速度。还有很多地图寻路应用等。

我觉得还需要看一下哪部电梯快到了。不过可以肯定的是如果高峰期在“包含这五个点的最小圆的圆心”等电梯的话,结果是一个也上不去。选一部电梯,挤到最前面才是王道。

#3 楼 @yeerkunth 很喜欢文章里面那个物理学解题的思路 #4 楼 @feitian124 难怪这么熟悉,现在算法知识都弱化了 #5 楼 @caryl 是啊,实际情况还要考虑风险和收益!

为啥是和呢

需要 登录 后方可回复, 如果你还没有账号请 注册新账号