vlambda博客
学习文章列表

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

人类总是崇敬知识,但并非崇敬所有知识,不少人曾问出过那个振聋发聩的问题:“高数有什么用?买菜用得上吗?”面对高数态度如此,更复杂的算法知识就更不用说了。不过,一位清华毕业计算机教授在美国的经历证明了,算法或许不能在买菜时帮你省几个小钱,但可以在遇到重大事件时,帮你赚回1台车。

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

史教授一家人开车从印第安纳的South Bend出发,大约中部时间12:00 到达芝加哥中国城,当时发现Mazda CX-9提示胎压异常,因此史教授决定午饭后开车前往中国城附近的一家Shell加油站给轮胎充气。史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回不巧的是,他们在途中遇到了2名持枪匪徒,不仅抢走了他的钱包,“顺便”还开走了他的车。

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

警方不靠谱,史教授只能靠自己。在被抢时,史教授耍了个小心机,悄悄把手机留在了车子上,一开始,他寄望于手机定位能帮他找到车,然而劫匪对电子产品的追踪功能非常清楚,相关功能已经无法显示实时位置。之后,他又想到了自己马自达车上几乎没用过的Mazda  Mobile Start (MMS)功能。

他先是按照CarFinder指示的相对距离,推断出车子大概是在芝加哥南郊。至于对不对,只要上路随便找1个方向开,距离缩短就是对的。结果上了朝芝加哥南郊的高速后,直线距离果然在快速减小,方向是正确的。

当车到达芝加哥南郊I-94 130th  st出口时,他们和马自达的距离已经减小到了2英里,车子很可能就在出口下面某处。不过,于是史教授从该出口下去以后转了一圈,发现周围都是公园,而且距离也没有继续减小,于是又开回高速。根据这种方法,史教授一路走一路缩小范围,最后对应地图,把目标确定在了下图中的Roseland中。

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回以下是该区域的放大地图:  史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

下了高速以后,很快就进入了这片小区,并一度发现有一辆白色的小车一直跟在史教授后面。过了好几个街区以后,那辆车才消失不见。

史教授再次和学生约定:不管发生什么情况,尽量不要停车,如果一定要停车,一定要让车辆保持在D档随时准备开动。

接着,整个事件中最有技术含量的部分来了:

因为相对方位并不靠谱,史教授选择了计算机算法中最直接的greedy approach,也就是沿着一个方向开,直到距离不再明显变小(这是说明我们前进的方向已经几乎垂直于我们和目标之间连线),就转到垂直方向的街道再继续搜寻。

  史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

就这样在一片破败的小区中兜了一段时间以后,终于在S Eberhart Ave在101st St和102nd St之间某个位置直接距离显示为200英尺,说明离目标已经很近了。

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

但奇怪的是,他们并没有在路边看到被抢的Mazda,在周围其他街道上时提示距离也大于200英尺,史教授完全没有办法让距离进一步减小了。

转来转去,最后发现,其实在S Vernon Ave和S Eberhart Ave之间还有一条小路,这条路并没有名字,在谷歌地图上甚至没有显示,但在上面这张卫星图里面可以看到这条路的存在(红色标记左侧的第一条路)。于是他们从101st St上转入了这条小路,入口是这样的。

史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

当时时间大概是早上八点多一点,周围一个人都没有,史教授他们保持缓慢的速度进入了小路。

一进入就发现MMS里提示的距离又开始明显下降,直到开过倒数第三间车库的时候,车库门是关着的,但距离显示小于5英尺,MMS发出提示音:

  车子就在里面!

他们二人没有敢多停留,在转到102nd St上后,史教授立刻拨打911,告诉接线员找到了被劫车辆。接线员问清了位置和所在的车辆信息后,让他们在原地等待,警察很快会到。

于是,整辆车“完璧归赵”,不仅如此,史教授还在车里找到了一些不属于自己的东西,比如1双崭新的Nike、一些吃剩的饮食包装,还有弥漫在车里的大麻味。只花了1天就找到被劫车辆,这种远超警方的效率,让警察也不由得感慨道:“They  shouldn’t have messed up with computer science professors!”

最后再来介绍一下本次行动的功臣——贪心算法。贪心算法又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,做出的是在某种意义上的局部最优解。

  史上最牛!清华毕业教授在芝加哥遭持枪劫车!靠“贪心算法”追回

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。




往期精彩: