别惹计算机系的！与歹徒、猪队友斗智斗勇的教授

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

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

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

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

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

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

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

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

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

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

值得一提的是，在他们打到 Roselan 小区后，有 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 shouln ’ t have messe up with computer science professors!"

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

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

史教授目前的研究方向主要是人工智能的硬件实现和在医疗等领域的应用。他曾获得美国国家自然基金委CAREER奖，IEEE Region 5 个人成就奖，卡尔圣路易科学院发明奖等；多次在领域内顶级国际会议上获得最佳论文提名。他获得美国发明专利5项(其中一项于2009年获得IBM专利奖，一项获得台北国际博览会金奖）；在国际重要研究期刊和会议上发表学术论文100余篇。他现任IEEE VLSI Circuits an System Letter的eputy Eitor-in-Chief，IEEE Trans. on CAD, ACM JETC, VLSI Integration等期刊的Associate Eitor, 以及ACM SIGDA的Eucation Chair。

关于文章中提到的，定位车辆的关键技术“计算机算法中最直接的greey approach”，史教授说，其实就是一个螺旋搜索，确保他们始终在沿着距离下降的方向单调搜索一定可以收敛的。

** 同时这个算法也称贪心算法** 。是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

“设想平面内有个点x0，你的目标函数是f(x,x0）f 是eucliian istance between x an x0，欧式距离是个凸函数，全局最优解存在切唯一，x0。”

百度北京大数据实验室主任浣军教授认为，史教授用greey approach是个凸优化问题，他始终能测距离。