跟谁学,算法建功!清华结业教授美国被抢车,差人力不从心自己用“贪心算法”找回,威少


人类总是敬重常识,但并非敬重一切常识,不少人曾问出过那个振聋发聩的问题:“高数有什么用?买菜用得上吗?”面临高数情绪如此,更杂乱的算法常识就更不用说了。不过,一位清华毕业计算机教授在美国的阅历证明了,算法或许不能在买菜时帮你省几个小钱,但能够在遇到重大事情时,帮你赚回1台车钱。


 千万别惹计算机教授 


最近,圣母大学计算机系终身副教授,博士生导师,并兼任电子系终身副教跟谁学,算法建功!清华毕业教授美国被抢车,差人无能为力自己用“贪心算法”找回,威少授史弋宇阅历了一件触目惊心的事:


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.” 而且重复重复说,神态严峻。另一个劫匪则钻进了驾驭室让一切人下车。


史教授考虑到车里还有孕妈妈和小孩,为了安全起见,就很合作的把钱包递给了劫匪,劫匪翻开后从里边拿出了一切的现金。


劫匪随后把钱包还给史教授,又让他赶忙把车钥匙交给劫匪。与此一同,车里的另一个劫匪继续敦促一切人下车。


“我发现他并没有关上驾驭座的门,就趁此时机把我的手机扔到了门上的夹袋里,期望对后续追寻有所协助。”


在天堂网AV2017咱们都下车后,劫匪一溜烟的就把车开跑了,而史教授一家一切的行李,包含护照、绿卡等等,都还在车尾箱里。


 报警:三次才打通911,差人把车型都搞错了 


劫匪并没有抢走史教授太太的手机,她的手机就成了史教授一家人的仅有通讯东西。


被抢之后史教授首要拨打911,第一次大约等了十几秒并没有被接通。所以第2次再打,仍是没有成功(所以要害时分911也不必定靠谱) 第三次再打,总算通了。


但911接线员却奉告:无法查询到史教授的车牌信息(I cannot find your license plate number sir)。


“我被劫匪持枪抢了车,打91猎杀失望山1报警,竟然还得自己去差人局做笔录,估量等我搞完,车都现已被chop shop大卸八块了。”


所以他继续拨打911。这一次接线员好了一些,在史教授又一次描绘了案情后,接线员帮转到了芝加哥中心差人局,对方的接线员又问了一遍状况,说这个你应该打给911啊(This is a true emergency and you should call 911 directly.)


“我都想谩骂了,忍住气继续说我打了,可是是他们把我转过来的。”所以,接线员又帮转回了91傻子楚南1,终究的接线员总算说派差人过来,此刻离掠夺发作现已曩昔了大约十分钟。


又等了大约十分钟,和史教授幻想中很多警车闪着警灯蜂拥而至的场景不同,只来了一辆警车。车上下来了两个差人,细心的问询了案发的通过,包含有没有看清醉蛇小子劫匪的长相、年纪等。


“我说你们能不能先帮我去追一下车子,这些信息我渐渐给你供给。但差人说,别担忧,一旦取得了所需的一切信息,就会将史教授的车牌信息输入体系并发布给履行的差人。


终究,当差人处理完时,离史教授的车被劫走现已过了整整半个小时。


接着,差人发现加油站里布满了监控摄像头,所以进到店里要看监控。但不一瞬间那个差人就出来了,问另一个差人:我不知道怎样上传这些视频,你会吗?另一个差人答复:我也不会啊。他们所以通知史教授:不要紧,会有侦察会来照料这个视频, 咱们的工作就办到这儿啦!


所以他们计划开车离去。


但刚上车又下来问史教授:


“你的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的界面,他的显现便是一个红点和一个大圈,红点代表快穿h文车的方位,大圈代表车的规模,然后右上角有间隔显现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定位,并再三着重只能信任间隔,不要去看相对方位。


差人留了手机之后,很快就开走了。但史教授决议仍是继续在邻近寻觅,而不是在路旁边等候,一方面是碰碰命运,另一方面则是出于安全考虑,不想要逗留在一个当地。


在接下来的一个多小时里,史教授和差人总共通了三次电话:第一次,差人问我那个追寻软件在哪里,是不是谷歌地图? 第2次,差人说间隔很近了,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。”


史教授的算法简而言之是每一步都削减间隔,所以是贪心算法。


所以啊,不要惹会算法的人!

————

修改 ∑ Gemini

来历:新智元

微信大众号“算法数学之美”,由算法与数学之美团队打造的另一个大众号,欢迎咱们扫码重视!


更多精彩:

怎么向5岁小孩解说什么是支撑向量机(SVM)?

天然底数e的含义是什么?

费马大定理,集阿格内尔跟谁学,算法建功!清华毕业教授美国被抢车,差人无能为力自己用“贪心算法”找回,威少惊险与武侠于一体

简略的解说,让你秒懂“最优化” 问题

一分钟看懂一维空间到十维空间

☞ 本科、硕士和博士到底有什么区别?

小波改换浅显解说

☞微积分必背公式

☞影响计算机算法国际的十位大师

☞数据发掘之七种常用的办法

算法数学之美微信大众号欢迎赐稿

稿件触及数学、物理、算法、计算机、编程等相关范畴,经选用咱们将奉上稿费。

投稿邮箱:math_alg@163.com

点击展开全文

上一篇:

下一篇:

相关推荐