算法立功！清华毕业教授美国被抢车 警察无能为力自己用“贪心算法”找回

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

12月下旬，清华毕业、现任圣母大学计算机系终身副教授、博士生导师、电子系终身副教授史弋宇原计划从芝加哥经纽约前往百慕大旅游，不巧的是，他们在途中遇到了2名持枪匪徒，不仅抢走了他的钱包，“顺便”还开走了他的车。万幸，在警方已经半放弃的情况下，他凭借自己强大的逻辑能力和算法思维，独自找到了车子，虽然旅行泡汤，但至少损失挽回了大半。

事情起于当天中午，当时，他们在芝加哥中国城附近的加油站给轮胎充气，趁他不在车上，2个身材不高大约20来岁的黑人从后面车上下来，对他举起了枪。之后，他们把所有人赶下车，钱拿走，大摇大摆地开走了，顺带带走了史教授一家所有的行李，只给他们留了几个空空的钱包。

之后警方登场了——和诸多美国电影一样，扮演的是反面角色。第1次报警，911表示无法查询到史教授的车牌信息;第2次报警，911帮史教授转接芝加哥中央警察局，警察局表示，这事归911管;第3次报警，终于有警察到场，但是在现场草草转了一圈之后，他们就草草离去了。

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

这个设备的作用是让车主用手机远程发动汽车引擎，给车辆上锁和开锁。那么，既然能用手机远程控制车子，在安装这个MMS的时候也一定启动了 GPS定位的功能。史教授上网一看，果然，MMS具备“CarFinder”的功能，可以大略显示车辆位置和发动机的启动状态。之后，这个功能就成了找到车子的关键。

首先介绍一下这个功能，在CarFinder界面中会显示1个红点和1个大圈，红点代表车的位置，大圈代表车的范围，然后右上角有距离显示81.8英里和相对误差+/- 22 英尺。没有地图，没有提供GPS坐标，换句话说，车主只能知道他和车的直接距离和相对位置。放在一般人身上，信息如此匮乏，基本上可以放弃了。然而，史教授的算法思维在这时候发挥了关键作用。

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

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

（图片来源于新智元）

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

值得一提的是，在他们打到Roseland小区后，有1辆白色小车一直跟在他们后面，跟了好几个街区，由于对方有枪，史教授和他招来帮忙的学生小王约定，无论如何不要停车，就算停车，也要保持在D裆，随时准备开动。

在小区内转悠半天后，他们终于在直线距离200英尺的地方，转进了1条小路。在这条小路上，MMS显示的距离一路缩短，当开到尽头倒数第3间紧闭着的车库时，MMS发出提示音：车子就在里面!

史教授立刻通知了警察，为了避免打草惊蛇和确保自身安全，他们并没有在那里过多停留，而是选择开出大路等待。然而，没等警察来到，MMS上面突然显示车辆发动，而且离他们越来越远。2名警察到场知悉劫匪跑掉后，让史教授在路边等待，他们会去追踪。

之后，警察再次开始了他们的愚蠢表演。在3通电话中，警方第1通是问史教授软件怎么用;第2次警察说他们已经靠到了400米，史教授告诉他MMS还有个panic功能，手机上点击后可以让车发出很大的警报声;最后1次，警察说没找到车，于是史教授只能自己继续寻找。

好在，有了上午的成功经验，史教授轻车熟路地用贪婪算法，很快在另外一地的加油站找到了被劫车辆。这次他们把车停在了可以看到被劫车辆的位置，才打了911，而且为了防止警方30-40分钟不到、1次只派2-3个人的现象再度出现，他故意把情况报告的更加严重。

果然，这次过了不到五分钟，第一辆警车就到了。在随后的几分钟里，呼啦啦来了七八辆警车把加油站围了个水泄不通，下来的警察都穿着防弹背心，手放在腰间的枪上。一群警察小心翼翼的靠近那辆马自达，很快就确定了车里并没有人。

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

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

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