清华毕业计算机教授遭持枪劫车！靠 “贪心算法” 追回秒杀美国警察

【新智元导读】不久前，圣母大学计算机系终身副教授一家人遭两名劫匪抢去汽车，在不到 24 小时之内，这名教授和博士生二人通过手机发动应用程序和计算机算法中的 “贪心算法”，成功将车找回。

千万别惹计算机教授。
最近，圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授史弋宇经历了一件惊心动魄的事：
12 月中下旬的周末，史教授原本计划开车带一家人由芝加哥 O’Hare 经纽约前往百慕大的度假旅行，在途中一座加油站停车检查车胎时，遇到了两名持枪劫匪。劫匪抢走了史教授的钱包和 Mazda CX-9 汽车，让这次旅行泡汤。
转折的地方在于，史教授利用马自达的手机发动应用程序（Mazda Mobile Start，MMS），成功定位到车辆的相对位置，并用计算机算法中最直接的 greedy approach（贪心算法），将车辆位置搜寻了出来。最终，在被抢不到 24 小时，史教授成功把车追回。
连现场的警察都感叹：
“They shouldn’t have messed up with computer science professors!”

被抢：两个劫匪持枪，抢走所有行李！

按原计划，史教授一家人开车从印第安纳的 South Bend 出发，大约中部时间 12:00 到达芝加哥中国城，当时发现 Mazda CX-9 提示胎压异常，因此史教授决定午饭后开车前往中国城附近的一家 Shell 加油站给轮胎充气。

当时加油站里的车并不少，而且也有些人在店里买东西，没有任何危险的征兆。
由于加油站的气泵非常简陋，需要投币 4 个 quarter 才能使用，而且并没有提供胎压读数，于是史教授决定换个加油站试试，但上车后他想起来似乎右前轮的气门帽并没有拧紧，打算下车拧紧。
刚下车，有两个身材不高大约 20 来岁的黑人从后面的一辆车上下来并靠近史教授，其中一个直接用一把枪指着他低声说 “See the gun? Give me your wallet. Give me your key.” 并且反复重复说，神情紧张。另一个劫匪则钻进了驾驶室让所有人下车。
史教授考虑到车里还有孕妇和小孩，为了安全起见，就很配合的把钱包递给了劫匪，劫匪打开后从里面拿出了所有的现金。
劫匪随后把钱包还给史教授，又让他赶紧把车钥匙交给劫匪。与此同时，车里的另一个劫匪继续催促所有人下车。
“我发现他并没有关上驾驶座的门，就趁此机会把我的手机扔到了门上的夹袋里，希望对后续追踪有所帮助。”
在大家都下车后，劫匪一溜烟的就把车开跑了，而史教授一家所有的行李，包括护照、绿卡等等，都还在车尾箱里。

报警：三次才打通 911，警察把车型都搞错了

劫匪并没有抢走史教授太太的手机，她的手机就成了史教授一家人的唯一通讯工具。
被抢之后史教授首先拨打 911，第一次大约等了十几秒并没有被接通。于是第二次再打，还是没有成功（所以关键时候 911 也不一定靠谱) 第三次再打，终于通了。
但 911 接线员却告知：无法查询到史教授的车牌信息（I cannot find your license plate number sir）。
“我被劫匪持枪抢了车，打 911 报警，居然还得自己去警察局做笔录，估计等我搞完，车都已经被 chop shop 大卸八块了。”
于是他继续拨打 911。这一次接线员好了一些，在史教授又一次描述了案情后，接线员帮转到了芝加哥中央警察局，对方的接线员又问了一遍情况，说这个你应该打给 911 啊（This is a true emergency and you should call 911 directly.）
“我都想骂人了，忍住气继续说我打了，但是是他们把我转过来的。” 于是，接线员又帮转回了 911，最后的接线员终于说派警察过来，此时离抢劫发生已经过去了大约十分钟。
又等了大约十分钟，和史教授想象中大量警车闪着警灯蜂拥而至的场景不同，只来了一辆警车。车上下来了两个警察，仔细的询问了案发的经过，包括有没有看清劫匪的长相、年龄等。
“我说你们能不能先帮我去追一下车子，这些信息我慢慢给你提供。但警察说，别担心，一旦获得了所需的所有信息，就会将史教授的车牌信息输入系统并发布给执行的警察。
最后，当警察处理完时，离史教授的车被劫走已经过了整整半个小时。
接着，警察发现加油站里布满了监控摄像头，于是进到店里要看监控。但不一会儿那个警察就出来了，问另一个警察：我不知道怎么上传这些视频，你会吗？另一个警察回答：我也不会啊。他们于是告诉史教授：没关系，会有侦探会来料理这个视频， 我们的事情就办到这里啦！
于是他们打算开车离去。
但刚上车又下来问史教授：
“你的 Mazda CX-9 是台两门的对吧?”
这时史教授已经完全无语了：
“长官，是个四门的 SUV。”
“OMG. It’s an SUV? F*ck”

Mazda CX-9（图据马自达官网）

然后警察立刻冲回车里拿起对讲机说：
It is not a small car. It’s a four-door SUV.
这时候离史教授的车被抢已经过去了四十多分钟，在这个时候史教授想起了一个关键问题：他把手机留在了车里！
警察顿时一脸兴奋：是 iPhone 手机吗？有没有开追踪功能？
“不，是台华为手机”
“什么手机？”
“华为，H-U-A-W-E-I”
“没听说过华为，它能追踪吗？”
“能，但是得花点时间。你们不能直接追踪手机信号吗？”
“不能，那都是电影里的情节，通过手机信号根本不能追踪手机。”
听到这里，史教授又想骂人了，如果不能追踪，那 Sprint’s Family Locator 和 AT&T's FamilyMap 的功能都是骗人的吗？明明三角追踪是很容易的。
由于史教授等登入手机账户，需要使用学校的 email，但是学校的 email 系统开启了基于 Duo 的 two step verification, 因此在新的手机上登录时需要首先通过自己的手机或者办公室电话验证，但这两条途径都没有办法使用。如果打电话给学校 IT，想想周末也没有人，于是放弃。
最后，史教授一家人打了个 Uber 之后，就回家了。

转折：手机发动应用程序成为关键，史教授决定靠自己寻车

到了家里已经傍晚，来不及吃晚饭，史教授找朋友借了台电脑，又立刻赶回学校，利用办公室的电话通过了 two step verification,，登录了 find my phone 的网页。不出所料，虽然 last seen 的日期是当天，但已经无法显示实时位置了，后来史教授发现其实这几个劫匪对电子产品的追踪功能非常清楚。
折腾了一天，回到家里很快史教授就睡觉了。故事本来也应该到此结束，但是他做了个梦，于是凌晨五点醒来时事情有了新的转机。
史教授梦到留在家里的那把车钥匙上有个远程遥控，摁一下车子就自己开回来了，而且所有行李都还在车上。
“在意识到这是个梦的同时，我也想到了一件事：当时在买车的时候，讨价还价了很久，到最后价格实在压不下来时，就让他们给免费装了一个 Mazda Mobile Start (MMS)，可以利用手机远程发动汽车引擎，给车辆上锁和开锁。”
其实装完后史教授就没怎么用过这个功能，但没想到它最终成了能找回车子的关键。
“我的判断是既然能用手机远程控制车子，那在安装这个 MMS 的时候也一定启动了 GPS 定位的功能。”
史教授马上打开电脑搜了一下，发现果然 MMS 还有一个附带功能，就是帮助你找到停车地点。于是他立刻在手机上登录这个 app，但发现密码始终不正确。重设了密码，依然提示密码错误。最后实在不行，去网上找了 MMS 的说明，仔细阅读后发现了另一种可能性：没有续租 MMS 服务，因此它被停用了。
史教授尝试着在网上续租了一年的服务，然后就很顺利的登录进了 app。“不得不说，马自达的 IT 实在是太烂了。从软件工程角度来说，没有续租导致的无法登录居然显示密码错误，这是 UI 设计的反面典型。只是这样也就算了，当我在 app 里找到 CarFinder 的界面，他的显示就是一个红点和一个大圈，红点代表车的位置，大圈代表车的范围，然后右上角有距离显示 81.8 英里和相对误差 +/- 22 英尺。没有地图，没有提供 GPS 坐标。”
所以，史教授除了能知道他和车的直接距离和相对位置，别的什么都不知道（后来发现其实那个相对位置也只有距离车很近的时候才会比较准，距离远的时候完全可能是错的）。他还顺便看了一下引擎的状态，是 OFF 的，说明车子被停在了某个地方。
不管怎么样，总算有车的线索了。史教授立刻打 911，结果接线员说这事儿不紧急啊，你直接联系芝加哥中央警察局吧，我们不管。
史教授又打给芝加哥警局，接电话的警员说太好啦，这个事情你得告诉负责你的案子的侦探啊，不过今天周末他不在办公室里，我帮你转到他语音信箱吧，这样他上班就能第一时间知道。
史教授耐着性子和他说：这个事情不太好拖吧，是不是越早越好？对方说：那行吧，你把 GPS 坐标给我，我们派人去看看。
但是汽车没有坐标，只能看到车子和用户的距离以及相对的方向。听到这话，对方说警力有限，不能帮着你满大街找车。
最后，对方给了一个非常有建设性的意见：不如你自己去找找？找到了以后可以给我们打电话呀，我们一定来解决剩下的事情。
警察靠不住就只能靠自己了。

波折：路上疑似被跟踪，离马自达只有不到 5 英尺

当时是早上六点，于是史教授满怀歉疚的打了个电话给他的一个平时还挺机灵的学生小王，请他陪同一起去趟芝加哥找车。小王二话不说就赶了过来，两人在全家人充满忧虑的目送中开车驶入了黎明前的黑暗里。
史教授把驾驶任务交给了小王，而他则开始在车上进行一些信息搜集和准备工作。
首先大概搜索了一下，发现按照 MMS 提示的直线距离，大概目标位置会是在芝加哥的南郊，一个以暴乱和枪击闻名的地区。
其次是安全距离。劫匪手里有枪，按照史教授当时目测的口径应该不超过 9mm，史教授还查了一下大概有效射程是 100 米左右。 这样的话，只要保持车辆始终在移动状态下，没有经过专业射击训练的枪手是很难击中车里的人的。而且，只要始终警惕 100 米范围内是否有人靠近就可以了。（新智元注：此案为个例，请勿效仿）
查完这些，史教授心里稍微安定了一些。
回过头来再看，史教授发现 MMS 相对位置提示有问题，主要是因为他们出发的时候 MMS 提示车子位于正北方，而芝加哥位于正西方，他判断劫匪肯定还把车留在芝加哥，因此决定忽略方位提示而直接前往芝加哥。结果上了高速就很明显看到直线距离在快速减小，说明方向是正确的。
在快到芝加哥南郊 I-94 130th st 出口时，距离减小到了 2 英里 。于是史教授从该出口下去以后转了一圈，发现周围都是公园，而且距离也没有继续减小，于是又开回 I-94, 继续前行，距离又开始减小，到了 Roseland 区域时，降到了 1 英里以下，但偏偏 I-94 在这里分叉了另一支高速 I-57 West，于是又只好转到了 I-57 并在下一个出口 Halsted St 下了高速。此时距离提示又增加到了 2 英里。
最终，史教授把车辆位置确定在了图中红色的区域里。

以下是该区域的放大地图：

下了高速以后，很快就进入了这片小区，并一度发现有一辆白色的小车一直跟在史教授后面。过了好几个街区以后，那辆车才消失不见。
史教授再次和学生约定：不管发生什么情况，尽量不要停车，如果一定要停车，一定要让车辆保持在 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.5 英里，而且引擎已经启动，说明车辆正在行驶中！
打草惊蛇了。
于是史教授一边懊悔应该把车停到一个能看得到那个车库的位置，一边立刻决定要跟上马自达。但不幸的是，MMS 并不是设计用来追踪行驶状态下的车辆的，因此车的位置和距离更新不是实时的。
于是二人漫无目的的在路上行驶，希望有机会能看到这辆马自达。就这样找了十多分钟后，两个警察来了，史教授向他们简单描述了如何寻找到被劫车辆的位置，并且告诉他们劫匪又跑了。
警察从史教授手里借走了手机，让他们在路边等待，警察会去追踪。这时史教授告诉了警察如何使用 MMS 定位，并再三强调只能相信距离，不要去看相对位置。
警察留了手机之后，很快就开走了。但史教授决定还是继续在附近寻找，而不是在路边等待，一方面是碰碰运气，另一方面则是出于安全考虑，不想要停留在一个地方。
在接下来的一个多小时里，史教授和警察一共通了三次电话：第一次，警察问我那个追踪软件在哪里，是不是谷歌地图? 第二次，警察说距离很近了，0.4 英里， 但是没有看到车。史教授告诉他 MMS 还有个 panic 功能，手机上点击后可以让车发出很大的警报声；第三次，也就是最后一次，警察说没找到车，决定回来把手机还给史教授。
警察回来见到史教授后，和他抱怨了一通 MMS 是多么的垃圾和难用，问他是否还打算继续找？史教授说当然啊，于是警察就说那你找到了再打电话给我们吧，然后就开车走了。
史教授拿回手机，更新一下状态，发现引擎已经处于了停止状态，说明车子又被停在了某个地方，距离显示是 4.3 英里。
于是史教授和小王又开始重复早上那套简单但行之有效的 greedy search 方案。很快，他们就在位于 2801 W 87th St 的 Citgo 加油站里看到了被劫车辆。车子就停在图中左边那辆白色汽车左边的位置，打着双闪，无法看清车内是否有人。

汲取之前的教训，这次他们把车也开进了加油站，停到了图里黑色汽车所在的位置，确保能看到被劫车辆，随后再次拨打了 911。
这次史教授直接告诉接线员：我看到了被劫车辆，就在我不远处，车里好像有人，他们还有枪。
“我知道不把情况说的严重一些，他们是不会认真严肃对待的”。
果然，这次过了不到五分钟，第一辆警车就到了。在随后的几分钟里，呼啦啦来了七八辆警车把加油站围了个水泄不通，下来的警察都穿着防弹背心，手放在腰间的枪上。一群警察小心翼翼的靠近那辆马自达，很快就确定了车里并没有人。
于是史教授也走了过去，打开后尾箱，发现里面有自己的书包，装着单反和几个镜头的相机包，史教授太太的包，以及不知道是谁的一双崭新的 Nike boots。
丢失的东西包括多个证件，并且车里还弥漫着一股大麻的味道，后座上还留了劫匪们吃剩下的一些食物的袋子和可乐罐。
好在，全部重要证件和大部分财物都在，甚至还追回了一部分并不是史教授的 “赃物”。劫匪完全没有来的及清理车里的大量证物，这让警方可以提取 DNA 和指纹。
最后连警察们都被史教授能够如此迅速解决此事而惊叹：“They shouldn’t have messed up with computer science professors!”

史教授：出身清华，“贪心算法” 成了关键一招

看完这个故事，有必要介绍一下史教授的背景。

史弋宇

史弋宇（博士）现任圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授, 该校美国国家科学基金委新型可持续人工智能产学研究中心主任。之前任密苏里大学罗拉分校助理教授，博士生导师，美国国家科学基金委基于网络的软件系统产学研究中心副主任。
史教授 2005 年在清华大学电子工程系获得学士学位，2009 年在美国加州大学洛杉矶分校（UCLA）电子工程系获得博士学位，2009－2010 在卡内基梅隆大学进行博士后研究工作。
史教授目前的研究方向主要是人工智能的硬件实现和在医疗等领域的应用。他曾获得美国国家自然基金委 CAREER 奖，IEEE Region 5 个人成就奖，卡尔圣路易科学院发明奖等；多次在领域内顶级国际会议上获得最佳论文提名。他获得美国发明专利 5 项 (其中一项于 2009 年获得 IBM 专利奖，一项获得台北国际博览会金奖）；在国际重要研究期刊和会议上发表学术论文 100 余篇。他现任 IEEE VLSI Circuits and System Letter 的 deputy Editor-in-Chief，IEEE Trans. on CAD, ACM JETC, VLSI Integration 等期刊的 Associate Editor, 以及 ACM SIGDA 的 Education Chair。
关于定位车辆的关键技术 “计算机算法中最直接的 greedy approach”，史教授说，其实就是一个螺旋搜索，确保他们始终在沿着距离下降的方向单调搜索一定可以收敛的。
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

百度北京大数据实验室主任浣军教授认为，史教授用 greedy approach 是个凸优化问题，他始终能测距离。
“设想平面内有个点 x0，你的目标函数是 f(x,x0）f 是 euclidian distance between x and x0，欧式距离是个凸函数，全局最优解存在切唯一，x0。”
史教授的算法简而言之是每一步都减少距离，所以是贪心算法。
所以啊，不要惹会算法的人！

（故事首发于公众号 “美国华人”，新智元获史教授及“美国华人” 授权编辑转载）