千万别惹计算机教授。
最近，美国圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授史弋宇经历了一件惊心动魄的事：
12月中下旬的周末，史教授原本计划开车带一家人由芝加哥奥黑尔经纽约前往百慕大度假旅行，在途中一座加油站停车检查车胎时，遇到了两名持枪劫匪。劫匪抢走了史教授的钱包和马自达CX-9汽车，让这次旅行泡汤。
转折的地方在于，史教授利用马自达的手机车锁应用程序，成功定位到车辆的相对位置，并用计算机算法中最直接的“贪心算法”，将车辆位置搜寻了出来。最终，在被抢不到24小时后，史教授成功把车追回。
连现场的警察都感叹：他们不应该去招惹一个计算机教授！
本文转载自微信公众号“超级数学建模”（ID：supermodeling），原文发于2019年1月5日，标题为《清华大学再出神人，汽车被盗，用“贪心算法”瞬间找到偷车贼》，不代表瞭望智库观点。 1 被抢：两个劫匪持枪， 抢走所有行李！ 按原计划，史教授一家人开车从印第安纳的南本德市出发，大约中部时间12:00到达芝加哥中国城，当时他发现他的马自达CX-9提示胎压异常，因此史教授决定午饭后开车前往中国城附近的一家壳牌加油站给轮胎充气。  当时加油站里的车并不少，而且也有些人在店里买东西，没有任何危险的征兆。 由于加油站的气泵非常简陋，而且没有提供胎压读数，于是史教授决定换个加油站试试，但上车后他想起来似乎右前轮的气门帽没有拧紧，打算下车拧紧。 刚下车，就有两个身材不高，大约20来岁的黑人从后面一辆车上下来并靠近史教授，其中一个直接用一把枪指着他低声说：“看见我的枪了吗？快把你的钱包和钥匙交出来！”并且反复说，神情紧张。另一个劫匪则钻进了驾驶室让所有人下车。 考虑到车里还有孕妇和小孩，为了安全起见，史教授就很配合地把钱包递给了劫匪，劫匪打开后从里面拿出了所有现金。 劫匪随后把钱包还给史教授，又让他赶紧把车钥匙交给劫匪。与此同时，车里的另一个劫匪继续催促所有人下车。 “我发现他并没有关上驾驶座的门，就趁此机会把我的手机扔到了门上的夹袋里，希望对后续追踪有所帮助。” 在大家都下车后，劫匪一溜烟就把车开跑了，而史教授一家所有的行李，包括护照、绿卡等等，都还在车尾箱里。 2 报警：三次才打通911， 警察把车型都搞错了 劫匪并没有抢走史教授太太的手机，她的手机就成了史教授一家人的唯一通讯工具。 被抢之后史教授首先拨打911，第一次大约等了十几秒，没有被接通。于是再打，还是没有成功（所以关键时候911也不一定靠谱) ，第三次再打，终于通了。 但911接线员却告诉他，无法查询到他的车牌信息。 “我被劫匪持枪抢了车，打911报警，居然还得自己去警察局做笔录，估计等我搞完，车都已经被拆车厂大卸八块了。” 于是他继续拨打911，这一次接线员好了一些，在史教授又一次描述了案情后，接线员帮转到了芝加哥中央警察局，对方的接线员又问了一遍情况，说“这个你应该打给911啊！” “我都想骂人了，忍住气继续说我打了，但是他们把我转过来的。”于是，接线员又帮转回了911，最后的接线员终于说派警察过来，此时离抢劫发生已经过去了大约十分钟。 又等了大约十分钟，和史教授想象中大量警车闪着警灯蜂拥而至的场景不同，只来了一辆警车。车上下来了两个警察，仔细询问了案发经过，包括有没有看清劫匪的长相、是否知道劫匪年龄等。 “史教授问他们，能不能先帮他追回汽车，之后再慢慢提供相关信息。但警察说，别担心，一旦获得了所需的所有信息，就会将史教授的车牌信息输入系统并发布给执行的警察。 最后，当警察处理完时，离史教授的车被劫走已经过了整整半个小时。 接着，警察发现加油站里布满了监控摄像头，于是进店看监控。但不一会儿，那个警察就出来了，问另一个警察：“我不知道怎么上传这些视频，你会吗？”另一个警察回答：“我也不会啊。”于是，他们告诉史教授：“没关系，会有其他警察来料理这个视频， 我们的事情就办到这里啦！” 于是他们打算开车离去。 但刚上车又下来问史教授：“你的马自达 CX-9 是台两门的对吧?” 这时史教授已经完全无语了：“长官，是四门的SUV。” “噢，天呐，居然是四门的。” 然后警察立刻冲回车里拿起对讲机说：“不是小车，是四门的SUV。” 这时候离史教授的车被抢已经过去了四十多分钟，这时史教授想起了一个关键问题：他把手机留在了车里！ 警察顿时一脸兴奋：是iPhone手机吗？有没有开追踪功能？ “不，是台华为手机” “什么手机？” “华为，H-U-A-W-E-I” “没听说过华为，它能追踪吗？” “能，但是得花点时间。你们不能直接追踪手机信号吗？” “不能，那都是电影里的情节，通过手机信号根本不能追踪手机。” 听到这里，史教授又想骂人了，如果不能追踪，那Sprint’s Family Locator 和 AT&T's FamilyMap的功能（Sprint和AT&T分别为美国的移动通信运营商，这里指的是他们的定位追踪服务）都是骗人的吗？明明三角追踪是很容易的。 由于史教授登入手机账户，需要使用学校的电子邮件，但是学校的电邮系统开启了双重验证功能, 因此在新的手机上登录时需要首先通过自己的手机或者办公室电话验证，但这两条途径都没有办法使用。如果打电话给学校网络维护部门，想想周末也没有人，于是放弃。 最后，史教授一家人叫了个出租车回家了。 3 转折：手机发动应用程序成为关键， 史教授决定靠自己寻车 到家已经傍晚了，来不及吃晚饭，史教授找朋友借了台电脑，又立刻赶回学校，利用办公室的电话通过了双重验证,登录了能定位手机的网页。不出所料，虽然最后访问的日期是当天，但已经无法显示实时位置了，后来史教授发现其实这几个劫匪对电子产品的追踪功能非常清楚。 折腾了一天，很快史教授就睡着了。故事本来也应到此结束，但他做了个梦，梦到他留在家里的那把车钥匙上有个远程遥控，摁一下之后，车子就自己开回来了，而且所有行李都还在车上。 “在意识到这是个梦的同时，我也想到了一件事：当时在买车的时候，讨价还价了很久，到最后价格实在压不下来时，就让他们给免费装了一个手机车锁(MMS)，可以利用手机远程发动汽车引擎，给车辆上锁和开锁。” 其实装完后史教授就没怎么用过这个功能，但没想到它最终成了能找回车子的关键。 “我的判断是既然能用手机远程控制车子，那在安装这个车锁的时候也一定启动了 GPS定位的功能。” 史教授马上打开电脑搜了一下，发现果然MMS还有一个附带功能，就是帮助你找到停车地点。于是他立刻在手机上登录这个app，但发现密码始终不正确。重设了密码，依然提示密码错误。最后实在不行，去网上找了MMS的说明，仔细阅读后发现了另一种可能性：没有续租MMS服务，因此它被停用了。 史教授尝试着在网上续租了一年的服务，然后就很顺利的登录进了app。“当我在app里找到车辆追踪的界面，他的显示就是一个红点和一个大圈，红点代表车的位置，大圈代表车的范围，然后右上角有距离显示81.8英里（约等于131公里）和相对误差+/- 22 英尺（约等于6.7米）。没有地图，没有提供GPS坐标。” 所以，史教授除了能知道他和车的直接距离和相对位置，别的什么都不知道（后来发现其实那个相对位置也只有距离车很近的时候才会比较准，距离远的时候完全可能是错的）。他还顺便看了一下引擎的状态，处于熄火的状态，说明车子被停在了某个地方。 不管怎么样，总算有车的线索了。史教授立刻打911，结果接线员说这事不紧急，你直接联系芝加哥中央警察局吧，我们不管。 史教授又打给芝加哥警局，接电话的警员说太好啦，这个事情你得告诉负责你的案子的侦探啊，不过今天周末他不在办公室里，我帮你转到他语音信箱吧，这样他上班就能第一时间知道。 史教授耐着性子和他说：这个事情不太好拖吧，是不是越早越好？对方说：那行吧，你把GPS坐标给我，我们派人去看看。 但是汽车没有坐标，只能看到车子和用户的距离以及相对的方向。听到这话，对方说警力有限，不能帮着你满大街找车。 最后，对方给了一个非常有建设性的意见：不如你自己去找找？找到了以后可以给我们打电话呀，我们一定来解决剩下的事情。 警察靠不住就只能靠自己了。 4 波折：路上疑似被跟踪， 离自己的车只有不到5英尺 当时是早上六点，于是史教授满怀歉疚的打了个电话给他的一个平时还挺机灵的学生小王，请他一起去趟芝加哥。小王二话不说就赶了过来，两人在全家人充满忧虑的目送中开车驶入了黎明前的黑暗里。 史教授把驾驶任务交给了小王，而他则开始在车上进行一些信息搜集和准备工作。 首先搜索了一下，发现按照MMS提示的直线距离，大概目标位置会是在芝加哥南郊，一个以暴乱和枪击闻名的地区。 其次是安全距离。劫匪手里有枪，按照史教授当时目测的口径应该不超过9mm，史教授还查了一下大概有效射程是100米左右。 这样的话，只要保持车辆始终在移动状态下，没有经过专业射击训练的枪手是很难击中车里人的。而且，只要始终警惕100米范围内是否有人靠近就可以了（注：此案为个例，请勿效仿）。 查完这些，史教授心里稍微安定了。 回过头来再看，史教授发现MMS相对位置提示有问题，主要是因为他们出发的时候MMS提示车子位于正北方，而芝加哥位于正西方，他判断劫匪肯定还把车留在芝加哥，因此决定忽略方位提示直接前往芝加哥。结果上了高速就很明显看到直线距离在快速减小，说明方向是正确的。 在快到芝加哥南郊I-94高速第103街出口时，距离减小到了2英里（1英里约等于1.6公里）。于是史教授从该出口下去以后转了一圈，发现周围都是公园，而且距离也没有继续减小，于是又开回I-94高速路, 继续前行，距离又开始减小，到了罗斯兰区域时，降到了1英里以下，但偏偏I-94高速在这里分叉了另一条高速 I-57 ，于是又只好转到I-57并在下一个出口下了高速。此时距离提示又增加到了2英里。 最终，史教授把车辆位置确定在了图中红色的区域里。  以下是该区域的放大地图：  下了高速以后，很快就进入了这片小区，并一度发现有一辆白色的小车一直跟在史教授后面。过了好几个街区以后，那辆车才消失不见。 史教授再次和学生约定：不管发生什么情况，尽量不要停车，如果一定要停车，一定要让车辆保持在前进档随时准备开动。 接着，整个事件中最有技术含量的部分来了： 因为相对方位并不靠谱，史教授选择了计算机算法中最直接的“贪心算法”，也就是沿着一个方向开，直到距离不再明显变小（这说明我们前进的方向已经几乎垂直于我们和目标之间连线），就转到垂直方向的街道再继续搜寻。  就这样在一片破败的小区中兜了一段时间以后，终于在南艾伯哈特大街在第101号大街和第102号大街之间某个位置直接距离显示为200英尺（约60米），说明离目标已经很近了。  但奇怪的是，他们并没有在路边看到被抢的马自达，在周围其他街道上时提示距离也大于200英尺，史教授完全没有办法让距离进一步减小了。 转来转去，最后发现，其实在南弗农大街和南艾伯哈特大街之间还有一条小路，这条路并没有名字，在谷歌地图上甚至没有显示，但在上面这张卫星图里面可以看到这条路的存在（红色标记左侧的第一条路）。于是他们从第101号大街上转入了这条小路，入口是这样的。  当时时间大概是早上八点多，周围一个人都没有，史教授他们保持缓慢的速度进入了小路。 一进入就发现MMS里提示的距离又开始明显下降，直到开过倒数第三间车库的时候，车库门是关着的，但距离显示小于5英尺（约等于1.5米），MMS发出提示音：车子就在里面！ 5 扑空：打草惊蛇， 劫匪把车子开走了 他们二人没有敢多停留，在转到第102号大街后，史教授立刻拨打911，告诉接线员找到了被劫车辆。接线员问清了位置和所在的车辆信息后，让他们在原地等待，警察很快会到。 就在他们紧张的在路边等待的时候，小王提醒说，看看现在我们和被劫车辆的距离。史教授看了一下，大吃一惊：此时距离已经变成了1.5英里（约等于2.4公里），而且引擎已经启动，说明车辆正在行驶中！ 打草惊蛇了。 于是史教授一边懊悔应该把车停到一个能看得到那个车库的位置，一边立刻决定要跟上马自达。但不幸的是，MMS并不是设计用来追踪行驶状态下的车辆的，因此车的位置和距离更新不是实时的。 于是二人漫无目的的在路上行驶，希望有机会能看到这辆马自达。就这样找了十多分钟后，两个警察来了，史教授向他们简单描述了如何寻找到被劫车辆的位置，并且告诉他们劫匪又跑了。 警察从史教授手里借走了手机，让他们在路边等待，警察会去追踪。这时史教授告诉了警察如何使用MMS定位，并再三强调只能相信距离，不要去看相对位置。 警察留了手机之后，很快就开走了。但史教授决定还是继续在附近寻找，而不是在路边等待，一方面是碰碰运气，另一方面则是出于安全考虑，不想停留在一个地方。 在接下来的一个多小时里，史教授和警察一共通了三次电话：第一次，警察问那个追踪软件在哪里，是不是谷歌地图? 第二次，警察说距离很近了，0.4英里， 但没有看到车。史教授告诉他MMS还有个报警功能，手机上点击后可以让车发出很大的警报声；第三次，也就是最后一次，警察说没找到车，决定回来把手机还给史教授。 警察回来见到史教授后，和他抱怨了一通MMS是多么的垃圾和难用，问他是否还打算继续找？史教授说当然啊，于是警察就说那你找到了再打电话给我们吧，然后就开车走了。 史教授拿回手机，更新一下状态，发现引擎已经处于了停止状态，说明车子又被停在了某个地方，距离显示是4.3英里。 于是史教授和小王又开始重复早上那套简单但行之有效的“贪心算法”。很快，他们就在位于2801W87th St的希戈加油站里看到了被劫车辆。车子就停在图中左边那辆白色汽车左边的位置，打着双闪，无法看清车内是否有人。  汲取之前的教训，这次他们把车也开进了加油站，停到了图里黑色汽车所在的位置，确保能看到被劫车辆，随后再次拨打了911。 这次史教授直接告诉接线员：我看到了被劫车辆，就在我不远处，车里好像有人，他们还有枪。 “我知道不把情况说的严重一些，他们是不会认真严肃对待的”。 果然，这次过了不到五分钟，第一辆警车就到了。在随后的几分钟里，呼啦啦来了七八辆警车把加油站围了个水泄不通，下来的警察都穿着防弹背心，手放在腰间的枪上。一群警察小心翼翼靠近那辆马自达，很快就确定了车里并没有人。 于是史教授也走了过去，打开后尾箱，发现里面有自己的书包，装着单反和几个镜头的相机包，史教授太太的包，以及不知道是谁的一双崭新的耐克鞋。 丢失的东西包括多个证件，并且车里还弥漫着一股大麻的味道，后座上还留了劫匪们吃剩下的一些食物的袋子和可乐罐。 好在，全部重要证件和大部分财物都在，甚至还追回了一部分并不是史教授的“赃物”。劫匪完全没有来的及清理车里的大量证物，这让警方可以提取DNA和指纹。 最后连警察们都被史教授能够如此迅速解决此事而惊叹：他们不应该去招惹一个计算机教授！ 6 史教授：出身清华， “贪心算法”成了关键一招 看完这个故事，有必要介绍一下史教授的背景。  史弋宇 史弋宇（博士）现任圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授, 该校美国国家科学基金委新型可持续人工智能产学研究中心主任。之前任密苏里大学罗拉分校助理教授，博士生导师，美国国家科学基金委基于网络的软件系统产学研究中心副主任。 史教授2005年在清华大学电子工程系获得学士学位，2009年在美国加州大学洛杉矶分校（UCLA）电子工程系获得博士学位，2009－2010在卡内基梅隆大学进行博士后研究工作。 史教授目前的研究方向主要是人工智能的硬件实现和在医疗等领域的应用。他曾获得美国国家自然基金委CAREER奖，电气和电子工程师协会 Region 5 个人成就奖，卡尔圣路易科学院发明奖等；多次在领域内顶级国际会议上获得最佳论文提名。他获得美国发明专利5项(其中一项于2009年获得IBM专利奖，一项获得台北国际博览会金奖）；在国际重要研究期刊和会议上发表学术论文100余篇。他现任世界电气和电子工程师协会旗下电路和系统通讯期刊的副主编及美国计算机学会等其他期刊的助理编辑， 以及ACM SIGDA的教育主席。 关于定位车辆的关键技术——计算机算法中的“贪心算法”，史教授说，其实就是一个螺旋搜索，确保他们始终在沿着距离下降的方向单调搜索一定可以收敛的。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。  百度北京大数据实验室主任浣军教授认为，史教授用的贪心算法是个凸优化问题，他始终能测距离。 史教授的算法简而言之是每一步都减少距离，所以是“贪心算法”。 所以啊，不要惹会算法的人！
| 
发表于 2019-1-14 13:29:40
收藏