清华大学再出神人，汽车被盗，用“贪心算法”瞬间找到偷车贼
加油站外观如图所示：
红圈处就是气泵所在地。当时停车的位置也和图中的黑色轿车几乎一致。当时加油站里的车并不少，而且也有些人在店里买东西，没有任何危险的征兆。
史教授下车后发现气泵其实非常简陋，需要投 4 个 quarter 才能使用，而且并没有提供胎压读数。
研究了半天后去店里问问店员，然而店员也是一脸懵逼
“Sorry I know nothing about cars（对不起我对车一窍不通）。”
这时候 史教授决定换个加油站试试。上车后想起来似乎右前轮的气门帽并没有拧紧，打算下车拧紧。
但刚下车，就有两个身材不高大约20来岁的黑人从后面的一辆车上下来并靠近，其中 一个直接用一把枪指着史教授低声说
“See the gun? Give me your wallet. Give me your key（看见枪了么，给我钱包和车钥匙）.” 并且反复重复，神情紧张。另一个则钻进了驾驶室让所有人下车。
考虑到车里还有孕妇和小孩，为了安全起见，很配合交出了钱包。
史教授发现劫匪并没有关上驾驶座的门，就趁此机会把手机扔到了门上的夹袋里。 在大家都下车后，他们一溜烟的就把车开跑了，而他们所有的行李，包括护照，绿卡等等，都还在车尾箱里。
报警911 警察无作为
由于劫匪并没有抢走史教授太太的手机，她的手机就成了史教授一家人的唯一通讯工具。被抢之后史教授立马拨打了911，第一次大约等了十几秒并没有被接通，直到第三次电话才打通。
911 接线员：This is 911. What is your emergency?（这里是911，你们遇到了什么情况？）
我: I’m at a Shell gas station at Ruble St near I-94. My vehicle was hijacked by at least two men, one with a gun.（我在 I-94 高速入口边的壳牌加油站，我的车被至少两个劫匪持枪抢劫了。）
911 接线员：What is your license plate number?（你的车牌号是什么？）
我告知我的 plate number。
911 接线员：Okay. Let me check your license plate number first. Uh, sorry, I cannot find it in the system.（好的，让我先查一下车牌号。对不起，我在系统里找不到这个车牌号。）
我：Can you send some cops here first?（您能先联系警察吗？）
911 接线员：I cannot find your license plate number sir. I cannot do anything. You will need to go to a local police station and file the report.（先生，找不到你的车牌号我什么也做不了，你得去当地警察局报案做笔录。）
此时离抢劫发生已经过去了大约十分钟。
又等了大约十分钟，只来了一辆警车。车上下来了两个警察，仔细的询问了案发的经过，包括有没有看清劫匪的长相，年龄等。
史教授：“你们能不能先帮我去追一下车子，这些信息我慢慢给你提供。“
”Don’t Worry Sir. Once we have all the information we need we will enter your plate info into the system and blast it so every police car will be aware of it（别担心先生，一旦我们有了足够的信息，我们就会把你的车牌号等记在系统里，这样所有警察都会注意到你的车）“。
大概十分钟后他终于问完了。直到这时，他们才终于开始通过电台通告车辆信息，离我的车被劫走已经过了 整整半个小时。
于是他们打算开车离去。
刚上车又下来问: Your Mazda CX-9 is two-door right（你的马自达 CX-9 有两个车门对么）?
史教授已经完全无语了……Sir, it’s a four-door SUV（警官，我的车是一辆有四个车门的 SUV）.
OMG. It’s an SUV? Fuck.（我的妈，你丢了了个 SUV？干。）
然后立刻冲回车里拿起对讲机说: It is not a small car. It’s a four-door SUV.（被抢劫的车不是小轿车，是一个四门 SUV。）
这时候车被抢已经过去了四十多分钟。但史教授想起了一个关键问题，希望对他们的追踪有所帮助。
Sir, I left my phone in the car. Can you track it?（警官，我把手机放车里了，你们能追踪手机吗？）
警察顿时一脸兴奋: Is it an iPhone? Do you have the tracking function on?（你的手机是 iPhone 吗？你开定位功能了吗？）
No, Sir. It’s a Huawei phone.（不是，是个华为手机。）
What phone?（什么手机？）
Huawei. H-U-A-W-E-I（华为。喝-乌-阿-华，屋-诶-为。）
I’ve never heard of it. Can you track it?（我没听说过这个牌子。你能追踪这个手机吗？）
Yes, but it will take time for me to do so. Can’t you just track my cell phone signal?（能，但是我需要时间。你们就不能追踪我的手机信号么？）
No. You are misled by movies. It’s impossible to track a phone through cellular signals.（不能，你是电影看多了。蜂窝网络信号是不能追踪的）
如此史教授只能试试手机里安卓的追踪功能，之前怕找不到手机，他这个功能一直开着的。
然而要登入账户，需要使用学校的email，但是学校的email系统开启了基于 Duo的two step verification, 因此在新的手机上登录时需要首先通过他的手机或者办公室电话验证。
想想周末也没有人，于是放弃。
转机出现
于是打Uber回家。
到了家里找朋友借了台电脑，又立刻赶回学校，利用办公室的电话通过了 two step verification, 登录了 find my phone 的网页。不出我所料，虽然 last seen 的日期是当天，但已经无法显示实时位置了， 找车是无望了。
故事本来也应该到此结束，但是史教授做了个梦，事情有了新的转机。
在意识到这是个梦的同时，想到了一件事：当时在买车的时候，和 dealer 讨价还价了很久，到最后价格实在压不下来时，就让他们给免费装了一个 Mazda Mobile Start (MMS)，可以利用手机远程发动汽车引擎，给车辆上锁和开锁。
”我的判断是既然能用手机远程控制车子，那在安装这个 MMS 的时候也一定启动了 GPS 定位的功能。“
史教授马上打开电脑搜了一下，发现果然MMS还有一个附带功能，就是帮你找到停车地点。
于是他立刻在手机上登录这个app，但发现密码始终不正确。最后他去网上找了MMS的说明，阅读后发现了可能没续租……
于是史教授尝在网上续租了一年的服务，果然，他顺利的登录进了app。
“不得不说，马自达的IT实在是太烂了。从软件工程角度来说，没有续租导致的无法登录居然显示密码错误，这是UI设计的反面典型。
只是这样也就算了，当我在app里找到CarFinder的界面，他的显示就是一个红点和一个大圈，红点代表车的位置，大圈代表车的范围，然后右上角有距离显示81.8英里和相对误差+/- 22 英尺。没有地图，没有提供GPS坐标。”
所以史教授除了能知道自己和车的直接距离和相对位置，别的什么都不知道（后来发现其实那个相对位置也只有距离车很近的时候才会比较准，距离远的时候完全可能是错的）。顺便看了一下引擎的状态，是OFF的， 说明车子被停在了某个地方。
不管怎么样，总算有车的线索了。
立刻打 911，结果接线员说这事儿不紧急啊，你直接联系 Chicago Central Police Station 吧，我们不管。
打电话过去。接电话的警员说太好啦，这个事情你得告诉负责你的案子的侦探啊，不过今天周末他不在办公室里，我帮你转到他语音信箱吧，这样他上班就能第一时间知道。
史教授听了，虽然愤怒，但还是耐着性子说：“这事难道不是越早解决越好嘛？”
百里追凶
“那行吧，你把GPS坐标给我，我们派人去看看。”
史教授随后表示汽车没有坐标，只能看到车子和用户的距离以及相对的方向。
听到这话，对方又表示那警力有限，不能帮着你满大街找车。并且还给了一个非常有建设性的意见：不如你自己去找找？找到了以后可以给我们打电话呀，我们一定来解决剩下的事情。
史教授心想，看来警察是靠不住了。
早上六点，于是史教授不好意思的打了个电话给他的一个平时还挺机灵的学生小王，请他陪同一起去趟芝加哥找车。
小王听了，二话不说就赶了过来，史教授把驾驶任务交给了小王，自己开始在车上进行一些信息搜集和准备工作。
大概搜索了一下，史教授发现按照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，也就是沿着一个方向开，直到距离不再明显变小（这是说明我们前进的方向已经几乎垂直于我们和目标之间连线），就转到垂直方向的街道再继续搜寻。
Google Map显示的这一区域的卫星图：
转来转去，最后发现其实在 S Vernon Ave 和 S Eberhart Ave 之间还有一条小路，这条路并没有名字，在 Google Map 上甚至没有显示，但在上面这张卫星图里面可以看到这条路的存在（红色标记左侧的第一条路）。
从 101st St 上转入了这条小路，入口是这样的：
当时时间大概是早上八点多一点，周围一个人都没有。他们保持缓慢的速度进入了小路。一进入就发现 MMS 里提示的距离又开始明显下降，直到开过倒数第三间车库的时候，车库门是关着的，但距离显示小于 5 英尺, MMS 发出提示音， 车子就在里面！
打草惊蛇
一行人没有敢多停留，在转到102nd St上后，立刻拨打 911，告诉接线员找到了被劫车辆。接线员问清了位置和所在的车辆信息后，让原地等待，警察很快会到。
就在史教授紧张的在路边等待的时候，被劫车辆的引擎已经启动，说明 车辆正在行驶中。
懊悔之余，史教授拨打了911，并且决定跟上马自达！但不幸的是，MMS并不是设计用来追踪行驶状态下的车辆的，因此车的位置和距离更新不是实时的。
两人人漫无目的的在路上行驶，希望有机会能看到这辆马自达。十多分钟后，警察来了，史教授简单描述了如何寻找到被劫车辆的位置，并且告诉他们劫匪又跑了。
察从史教授手里借走了手机，让他们在路边等待，他们去追踪。史教授告诉了警察如何使用MMS定位，并再三强调只能相信距离，不要去看相对位置。
警察留了手机之后，很快就开走了。但史教授决定还是继续在附近寻找，而不是在路边等待，一方面是碰碰运气，另一方面则是出于安全考虑，不想要停留在一个地方。
在接下来的一个多小时里，史教授和警察一共通了三次电话：第一次，警察问我那个追踪软件在哪里，是不是谷歌地图? 第二次，警察说距离很近了，0.4英里， 但是没有看到车。史教授告诉他MMS还有个panic功能，手机上点击后可以让车发出很大的警报声；第三次，警察说没找到车，决定回来把手机还给史教授。
警察回来见到史教授后，还和他抱怨了一通MMS是多么的垃圾和难用，并询问他是否打算继续找？
史教授说当然啊，于是警察就说那你找到了再打电话给我们吧，然后就开车走了。
史教授拿回手机，更新一下状态，发现引擎已经处于了停止状态，说明车子又被停在了某个地方，距离显示是4.3英里。于是史教授和小王又开始重复早上那套简单但行之有效的greedy search方案。
锁定目标
皇天不负有心人，他们在位于2801 W 87th St的Citgo加油站里看到了被劫车辆（车子就停在下图中左边那辆白色汽车左边的位置）。
因为打着双闪，无法看清车内是否有人。
汲取之前的教训，他们把车也开进了加油站，为了确保能看到被劫车辆，他们停到了图里黑色汽车所在的位置，随后再次拨打了911。
这次史教授直接告诉接线员：我看到了被劫车辆。为了让警方重视，史教授故意说车里好像有人，他们还有枪。
果然，不到五分钟，第一辆警车就到了。在随后的几分钟里，来了七八辆警车，来的警察还都穿着防弹背心，手放在腰间的枪上。
一群警察小心翼翼的靠近那辆马自达，很快就确定了车里并没有人。
史教授也走了过去，打开后尾箱，发现里面有自己的书包，装着单反和几个镜头的相机包，史教授太太的包，以及不知道是谁的一双崭新的Nike boots。
丢失的东西包括多个证件，并且车里还弥漫着一股大麻的味道，后座上还留了一些吃剩的食物的袋子和可乐罐。
全部重要证件和大部分财物都在，甚至还多了一双Nike……
由于劫匪没有来的及清理车里的大量证物，警方提取了劫匪的DNA和指纹。
同时警察们也都被史教授能够自己如此迅速解决此事而惊叹：“They shouldn’t have messed up with computer science professors!”
劫匪完全没有来得及清理车里的大量证物，让警方可以提取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”，史教授说，其实就是一个螺旋搜索，确保他们始终在沿着距离下降的方向单调搜索一定可以收敛的。
同时这个算法也称贪心算法。是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
“设想平面内有个点x0，你的目标函数是f(x,x0）f 是euclidian distance between x and x0，欧式距离是个凸函数，全局最优解存在切唯一，x0。”
百度北京大数据实验室主任浣军教授认为，史教授用greedy approach是个凸优化问题，他始终能测距离。
学霸不可怕，会算法的学霸最可怕！惹谁都不能惹会算法的人！
来源：芝加哥吃货小分队
温馨提示：推广内容如有侵权请互联网是一个资源共享的生态圈，我们崇尚分享。 转载仅供思考 不代表【高数君】立场
其他平台转载请注明(来源：高数君 )
高 数 君