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!”

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

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

往期精彩：