清華畢業(yè)計算機(jī)教授遭持槍劫車！靠“貪心算法”追回秒殺美國警察

不久前，圣母大學(xué)計算機(jī)系終身副教授一家人遭兩名劫匪搶去汽車，在不到24小時之內(nèi)，這名教授和博士生二人通過手機(jī)發(fā)動應(yīng)用程序和計算機(jī)算法中的“貪心算法”，成功將車找回。

千萬別惹計算機(jī)教授。

最近，圣母大學(xué)計算機(jī)系終身副教授，博士生導(dǎo)師，并兼任電子系終身副教授史弋宇經(jīng)歷了一件驚心動魄的事：

12月中下旬的周末，史教授原本計劃開車帶一家人由芝加哥O’Hare經(jīng)紐約前往百慕大的度假旅行，在途中一座加油站停車檢查車胎時，遇到了兩名持槍劫匪。劫匪搶走了史教授的錢包和Mazda CX-9汽車，讓這次旅行泡湯。

轉(zhuǎn)折的地方在于，史教授利用馬自達(dá)的手機(jī)發(fā)動應(yīng)用程序（Mazda Mobile Start，MMS），成功定位到車輛的相對位置，并用計算機(jī)算法中最直接的greedy approach（貪心算法），將車輛位置搜尋了出來。最終，在被搶不到24小時，史教授成功把車追回。

連現(xiàn)場的警察都感嘆：

“They shouldn’t have messed up with computer science professors!”

被搶：兩個劫匪持槍，搶走所有行李！

按原計劃，史教授一家人開車從印第安納的South Bend出發(fā)，大約中部時間12:00 到達(dá)芝加哥中國城，當(dāng)時發(fā)現(xiàn)Mazda CX-9提示胎壓異常，因此史教授決定午飯后開車前往中國城附近的一家Shell加油站給輪胎充氣。

當(dāng)時加油站里的車并不少，而且也有些人在店里買東西，沒有任何危險的征兆。

由于加油站的氣泵非常簡陋，需要投幣4個quarter才能使用，而且并沒有提供胎壓讀數(shù)，于是史教授決定換個加油站試試，但上車后他想起來似乎右前輪的氣門帽并沒有擰緊，打算下車擰緊。

剛下車，有兩個身材不高大約20來歲的黑人從后面的一輛車上下來并靠近史教授，其中一個直接用一把槍指著他低聲說“See the gun? Give me your wallet. Give me your key.” 并且反復(fù)重復(fù)說，神情緊張。另一個劫匪則鉆進(jìn)了駕駛室讓所有人下車。

史教授考慮到車?yán)镞€有孕婦和小孩，為了安全起見，就很配合的把錢包遞給了劫匪，劫匪打開后從里面拿出了所有的現(xiàn)金。

劫匪隨后把錢包還給史教授，又讓他趕緊把車鑰匙交給劫匪。與此同時，車?yán)锏牧硪粋€劫匪繼續(xù)催促所有人下車。

“我發(fā)現(xiàn)他并沒有關(guān)上駕駛座的門，就趁此機(jī)會把我的手機(jī)扔到了門上的夾袋里，希望對后續(xù)追蹤有所幫助?！?/p>

在大家都下車后，劫匪一溜煙的就把車開跑了，而史教授一家所有的行李，包括護(hù)照、綠卡等等，都還在車尾箱里。

報警：三次才打通911，警察把車型都搞錯了

劫匪并沒有搶走史教授太太的手機(jī)，她的手機(jī)就成了史教授一家人的唯一通訊工具。

被搶之后史教授首先撥打911，第一次大約等了十幾秒并沒有被接通。于是第二次再打，還是沒有成功（所以關(guān)鍵時候911也不一定靠譜) 第三次再打，終于通了。

但911接線員卻告知：無法查詢到史教授的車牌信息（I cannot find your license plate number sir）。

“我被劫匪持槍搶了車，打911報警，居然還得自己去警察局做筆錄，估計等我搞完，車都已經(jīng)被chop shop大卸八塊了?！?/p>

于是他繼續(xù)撥打911。這一次接線員好了一些，在史教授又一次描述了案情后，接線員幫轉(zhuǎn)到了芝加哥中央警察局，對方的接線員又問了一遍情況，說這個你應(yīng)該打給911?。═his is a true emergency and you should call 911 directly.）

“我都想罵人了，忍住氣繼續(xù)說我打了，但是是他們把我轉(zhuǎn)過來的?！庇谑?，接線員又幫轉(zhuǎn)回了911，最后的接線員終于說派警察過來，此時離搶劫發(fā)生已經(jīng)過去了大約十分鐘。

又等了大約十分鐘，和史教授想象中大量警車閃著警燈蜂擁而至的場景不同，只來了一輛警車。車上下來了兩個警察，仔細(xì)的詢問了案發(fā)的經(jīng)過，包括有沒有看清劫匪的長相、年齡等。

“我說你們能不能先幫我去追一下車子，這些信息我慢慢給你提供。但警察說，別擔(dān)心，一旦獲得了所需的所有信息，就會將史教授的車牌信息輸入系統(tǒng)并發(fā)布給執(zhí)行的警察。

最后，當(dāng)警察處理完時，離史教授的車被劫走已經(jīng)過了整整半個小時。

接著，警察發(fā)現(xiàn)加油站里布滿了監(jiān)控攝像頭，于是進(jìn)到店里要看監(jiān)控。但不一會兒那個警察就出來了，問另一個警察：我不知道怎么上傳這些視頻，你會嗎？另一個警察回答：我也不會啊。他們于是告訴史教授：沒關(guān)系，會有偵探會來料理這個視頻， 我們的事情就辦到這里啦！

于是他們打算開車離去。

但剛上車又下來問史教授：

“你的Mazda CX-9 是臺兩門的對吧?”

這時史教授已經(jīng)完全無語了：

“長官，是個四門的SUV。”

“OMG. It’s an SUV? F*ck”

Mazda CX-9

然后警察立刻沖回車?yán)锬闷饘χv機(jī)說：

It is not a small car. It’s a four-door SUV.

這時候離史教授的車被搶已經(jīng)過去了四十多分鐘，在這個時候史教授想起了一個關(guān)鍵問題：他把手機(jī)留在了車?yán)铮?/p>

警察頓時一臉興奮：是iPhone手機(jī)嗎？有沒有開追蹤功能？

“不，是臺華為手機(jī)”

“什么手機(jī)？”

“華為，H-U-A-W-E-I”

“沒聽說過華為，它能追蹤嗎？”

“能，但是得花點時間。你們不能直接追蹤手機(jī)信號嗎？”

“不能，那都是電影里的情節(jié)，通過手機(jī)信號根本不能追蹤手機(jī)?！?/p>

聽到這里，史教授又想罵人了，如果不能追蹤，那Sprint’s Family Locator 和 AT&T's FamilyMap的功能都是騙人的嗎？明明三角追蹤是很容易的。

由于史教授等登入手機(jī)賬戶，需要使用學(xué)校的email，但是學(xué)校的email系統(tǒng)開啟了基于Duo的two step verification, 因此在新的手機(jī)上登錄時需要首先通過自己的手機(jī)或者辦公室電話驗證，但這兩條途徑都沒有辦法使用。如果打電話給學(xué)校IT，想想周末也沒有人，于是放棄。

最后，史教授一家人打了個Uber之后，就回家了。

轉(zhuǎn)折：手機(jī)發(fā)動應(yīng)用程序成為關(guān)鍵，史教授決定靠自己尋車

到了家里已經(jīng)傍晚，來不及吃晚飯，史教授找朋友借了臺電腦，又立刻趕回學(xué)校，利用辦公室的電話通過了two step verification,，登錄了find my phone的網(wǎng)頁。不出所料，雖然last seen的日期是當(dāng)天，但已經(jīng)無法顯示實時位置了，后來史教授發(fā)現(xiàn)其實這幾個劫匪對電子產(chǎn)品的追蹤功能非常清楚。

折騰了一天，回到家里很快史教授就睡覺了。故事本來也應(yīng)該到此結(jié)束，但是他做了個夢，于是凌晨五點醒來時事情有了新的轉(zhuǎn)機(jī)。

史教授夢到留在家里的那把車鑰匙上有個遠(yuǎn)程遙控，摁一下車子就自己開回來了，而且所有行李都還在車上。

“在意識到這是個夢的同時，我也想到了一件事：當(dāng)時在買車的時候，討價還價了很久，到最后價格實在壓不下來時，就讓他們給免費(fèi)裝了一個Mazda Mobile Start (MMS)，可以利用手機(jī)遠(yuǎn)程發(fā)動汽車引擎，給車輛上鎖和開鎖?！?/p>

其實裝完后史教授就沒怎么用過這個功能，但沒想到它最終成了能找回車子的關(guān)鍵。

“我的判斷是既然能用手機(jī)遠(yuǎn)程控制車子，那在安裝這個MMS的時候也一定啟動了 GPS定位的功能?！?/p>

史教授馬上打開電腦搜了一下，發(fā)現(xiàn)果然MMS還有一個附帶功能，就是幫助你找到停車地點。于是他立刻在手機(jī)上登錄這個app，但發(fā)現(xiàn)密碼始終不正確。重設(shè)了密碼，依然提示密碼錯誤。最后實在不行，去網(wǎng)上找了MMS的說明，仔細(xì)閱讀后發(fā)現(xiàn)了另一種可能性：沒有續(xù)租MMS服務(wù)，因此它被停用了。

史教授嘗試著在網(wǎng)上續(xù)租了一年的服務(wù)，然后就很順利的登錄進(jìn)了app?！安坏貌徽f，馬自達(dá)的IT實在是太爛了。從軟件工程角度來說，沒有續(xù)租導(dǎo)致的無法登錄居然顯示密碼錯誤，這是UI設(shè)計的反面典型。只是這樣也就算了，當(dāng)我在app里找到CarFinder的界面，他的顯示就是一個紅點和一個大圈，紅點代表車的位置，大圈代表車的范圍，然后右上角有距離顯示81.8英里和相對誤差+/- 22 英尺。沒有地圖，沒有提供GPS坐標(biāo)。”

所以，史教授除了能知道他和車的直接距離和相對位置，別的什么都不知道（后來發(fā)現(xiàn)其實那個相對位置也只有距離車很近的時候才會比較準(zhǔn)，距離遠(yuǎn)的時候完全可能是錯的）。他還順便看了一下引擎的狀態(tài)，是OFF的，說明車子被停在了某個地方。

不管怎么樣，總算有車的線索了。史教授立刻打911，結(jié)果接線員說這事兒不緊急啊，你直接聯(lián)系芝加哥中央警察局吧，我們不管。

史教授又打給芝加哥警局，接電話的警員說太好啦，這個事情你得告訴負(fù)責(zé)你的案子的偵探啊，不過今天周末他不在辦公室里，我?guī)湍戕D(zhuǎn)到他語音信箱吧，這樣他上班就能第一時間知道。

史教授耐著性子和他說：這個事情不太好拖吧，是不是越早越好？對方說：那行吧，你把GPS坐標(biāo)給我，我們派人去看看。

但是汽車沒有坐標(biāo)，只能看到車子和用戶的距離以及相對的方向。聽到這話，對方說警力有限，不能幫著你滿大街找車。

最后，對方給了一個非常有建設(shè)性的意見：不如你自己去找找？找到了以后可以給我們打電話呀，我們一定來解決剩下的事情。

警察靠不住就只能靠自己了。

波折：路上疑似被跟蹤，離馬自達(dá)只有不到5英尺

當(dāng)時是早上六點，于是史教授滿懷歉疚的打了個電話給他的一個平時還挺機(jī)靈的學(xué)生小王，請他陪同一起去趟芝加哥找車。小王二話不說就趕了過來，兩人在全家人充滿憂慮的目送中開車駛?cè)肓死杳髑暗暮诎道铩?/p>

史教授把駕駛?cè)蝿?wù)交給了小王，而他則開始在車上進(jìn)行一些信息搜集和準(zhǔn)備工作。

首先大概搜索了一下，發(fā)現(xiàn)按照MMS提示的直線距離，大概目標(biāo)位置會是在芝加哥的南郊，一個以暴亂和槍擊聞名的地區(qū)。

其次是安全距離。劫匪手里有槍，按照史教授當(dāng)時目測的口徑應(yīng)該不超過9mm，史教授還查了一下大概有效射程是100米左右。 這樣的話，只要保持車輛始終在移動狀態(tài)下，沒有經(jīng)過專業(yè)射擊訓(xùn)練的槍手是很難擊中車?yán)锏娜说?。而且，只要始終警惕100米范圍內(nèi)是否有人靠近就可以了。（新智元注：此案為個例，請勿效仿）

查完這些，史教授心里稍微安定了一些。

回過頭來再看，史教授發(fā)現(xiàn)MMS相對位置提示有問題，主要是因為他們出發(fā)的時候MMS提示車子位于正北方，而芝加哥位于正西方，他判斷劫匪肯定還把車留在芝加哥，因此決定忽略方位提示而直接前往芝加哥。結(jié)果上了高速就很明顯看到直線距離在快速減小，說明方向是正確的。

在快到芝加哥南郊I-94 130th st出口時，距離減小到了2英里 。于是史教授從該出口下去以后轉(zhuǎn)了一圈，發(fā)現(xiàn)周圍都是公園，而且距離也沒有繼續(xù)減小，于是又開回I-94, 繼續(xù)前行，距離又開始減小，到了Roseland區(qū)域時，降到了1英里以下，但偏偏I(xiàn)-94在這里分叉了另一支高速 I-57 West，于是又只好轉(zhuǎn)到了I-57并在下一個出口 Halsted St下了高速。此時距離提示又增加到了2英里。

最終，史教授把車輛位置確定在了圖中紅色的區(qū)域里。

以下是該區(qū)域的放大地圖：

下了高速以后，很快就進(jìn)入了這片小區(qū)，并一度發(fā)現(xiàn)有一輛白色的小車一直跟在史教授后面。過了好幾個街區(qū)以后，那輛車才消失不見。

史教授再次和學(xué)生約定：不管發(fā)生什么情況，盡量不要停車，如果一定要停車，一定要讓車輛保持在D檔隨時準(zhǔn)備開動。

接著，整個事件中最有技術(shù)含量的部分來了：

因為相對方位并不靠譜，史教授選擇了計算機(jī)算法中最直接的greedy approach，也就是沿著一個方向開，直到距離不再明顯變?。ㄟ@是說明我們前進(jìn)的方向已經(jīng)幾乎垂直于我們和目標(biāo)之間連線），就轉(zhuǎn)到垂直方向的街道再繼續(xù)搜尋。

就這樣在一片破敗的小區(qū)中兜了一段時間以后，終于在S Eberhart Ave在101st St和102nd St之間某個位置直接距離顯示為200英尺，說明離目標(biāo)已經(jīng)很近了。

但奇怪的是，他們并沒有在路邊看到被搶的Mazda，在周圍其他街道上時提示距離也大于200英尺，史教授完全沒有辦法讓距離進(jìn)一步減小了。

轉(zhuǎn)來轉(zhuǎn)去，最后發(fā)現(xiàn)，其實在S Vernon Ave和S Eberhart Ave之間還有一條小路，這條路并沒有名字，在谷歌地圖上甚至沒有顯示，但在上面這張衛(wèi)星圖里面可以看到這條路的存在（紅色標(biāo)記左側(cè)的第一條路）。于是他們從101st St上轉(zhuǎn)入了這條小路，入口是這樣的。

當(dāng)時時間大概是早上八點多一點，周圍一個人都沒有，史教授他們保持緩慢的速度進(jìn)入了小路。

一進(jìn)入就發(fā)現(xiàn)MMS里提示的距離又開始明顯下降，直到開過倒數(shù)第三間車庫的時候，車庫門是關(guān)著的，但距離顯示小于5英尺，MMS發(fā)出提示音：

車子就在里面！

撲空：打草驚蛇，劫匪把車子開走了

他們二人沒有敢多停留，在轉(zhuǎn)到102nd St上后，史教授立刻撥打911，告訴接線員找到了被劫車輛。接線員問清了位置和所在的車輛信息后，讓他們在原地等待，警察很快會到。

就在他們緊張的在路邊等待的時候，小王提醒說，看看現(xiàn)在我們和被劫車輛的距離。史教授看了一下，大吃一驚：此時距離已經(jīng)變成了1.5英里，而且引擎已經(jīng)啟動，說明車輛正在行駛中！

打草驚蛇了。

于是史教授一邊懊悔應(yīng)該把車停到一個能看得到那個車庫的位置，一邊立刻決定要跟上馬自達(dá)。但不幸的是，MMS并不是設(shè)計用來追蹤行駛狀態(tài)下的車輛的，因此車的位置和距離更新不是實時的。

于是二人漫無目的的在路上行駛，希望有機(jī)會能看到這輛馬自達(dá)。就這樣找了十多分鐘后，兩個警察來了，史教授向他們簡單描述了如何尋找到被劫車輛的位置，并且告訴他們劫匪又跑了。

警察從史教授手里借走了手機(jī)，讓他們在路邊等待，警察會去追蹤。這時史教授告訴了警察如何使用MMS定位，并再三強(qiáng)調(diào)只能相信距離，不要去看相對位置。

警察留了手機(jī)之后，很快就開走了。但史教授決定還是繼續(xù)在附近尋找，而不是在路邊等待，一方面是碰碰運(yùn)氣，另一方面則是出于安全考慮，不想要停留在一個地方。

在接下來的一個多小時里，史教授和警察一共通了三次電話：第一次，警察問我那個追蹤軟件在哪里，是不是谷歌地圖? 第二次，警察說距離很近了，0.4英里， 但是沒有看到車。史教授告訴他MMS還有個panic功能，手機(jī)上點擊后可以讓車發(fā)出很大的警報聲；第三次，也就是最后一次，警察說沒找到車，決定回來把手機(jī)還給史教授。

警察回來見到史教授后，和他抱怨了一通MMS是多么的垃圾和難用，問他是否還打算繼續(xù)找？史教授說當(dāng)然啊，于是警察就說那你找到了再打電話給我們吧，然后就開車走了。

史教授拿回手機(jī)，更新一下狀態(tài)，發(fā)現(xiàn)引擎已經(jīng)處于了停止?fàn)顟B(tài)，說明車子又被停在了某個地方，距離顯示是4.3英里。

于是史教授和小王又開始重復(fù)早上那套簡單但行之有效的greedy search方案。很快，他們就在位于2801 W 87th St的Citgo加油站里看到了被劫車輛。車子就停在圖中左邊那輛白色汽車左邊的位置，打著雙閃，無法看清車內(nèi)是否有人。

汲取之前的教訓(xùn)，這次他們把車也開進(jìn)了加油站，停到了圖里黑色汽車所在的位置，確保能看到被劫車輛，隨后再次撥打了911。

這次史教授直接告訴接線員：我看到了被劫車輛，就在我不遠(yuǎn)處，車?yán)锖孟裼腥?，他們還有槍。

“我知道不把情況說的嚴(yán)重一些，他們是不會認(rèn)真嚴(yán)肅對待的”。

果然，這次過了不到五分鐘，第一輛警車就到了。在隨后的幾分鐘里，呼啦啦來了七八輛警車把加油站圍了個水泄不通，下來的警察都穿著防彈背心，手放在腰間的槍上。一群警察小心翼翼的靠近那輛馬自達(dá)，很快就確定了車?yán)锊]有人。

于是史教授也走了過去，打開后尾箱，發(fā)現(xiàn)里面有自己的書包，裝著單反和幾個鏡頭的相機(jī)包，史教授太太的包，以及不知道是誰的一雙嶄新的Nike boots。

丟失的東西包括多個證件，并且車?yán)镞€彌漫著一股大麻的味道，后座上還留了劫匪們吃剩下的一些食物的袋子和可樂罐。

好在，全部重要證件和大部分財物都在，甚至還追回了一部分并不是史教授的“贓物”。劫匪完全沒有來的及清理車?yán)锏拇罅孔C物，這讓警方可以提取DNA和指紋。

最后連警察們都被史教授能夠如此迅速解決此事而驚嘆：“They shouldn’t have messed up with computer science professors!”

史教授：出身清華，“貪心算法”成了關(guān)鍵一招

看完這個故事，有必要介紹一下史教授的背景。

史弋宇

史弋宇（博士）現(xiàn)任圣母大學(xué)計算機(jī)系終身副教授，博士生導(dǎo)師，并兼任電子系終身副教授, 該校美國國家科學(xué)基金委新型可持續(xù)人工智能產(chǎn)學(xué)研究中心主任。之前任密蘇里大學(xué)羅拉分校助理教授，博士生導(dǎo)師，美國國家科學(xué)基金委基于網(wǎng)絡(luò)的軟件系統(tǒng)產(chǎn)學(xué)研究中心副主任。

史教授2005年在清華大學(xué)電子工程系獲得學(xué)士學(xué)位，2009年在美國加州大學(xué)洛杉磯分校（UCLA）電子工程系獲得博士學(xué)位，2009－2010在卡內(nèi)基梅隆大學(xué)進(jìn)行博士后研究工作。

史教授目前的研究方向主要是人工智能的硬件實現(xiàn)和在醫(yī)療等領(lǐng)域的應(yīng)用。他曾獲得美國國家自然基金委CAREER獎，IEEE Region 5個人成就獎，卡爾圣路易科學(xué)院發(fā)明獎等；多次在領(lǐng)域內(nèi)頂級國際會議上獲得最佳論文提名。他獲得美國發(fā)明專利5項(其中一項于2009年獲得IBM專利獎，一項獲得臺北國際博覽會金獎）；在國際重要研究期刊和會議上發(fā)表學(xué)術(shù)論文100余篇。他現(xiàn)任IEEE VLSI Circuits and System Letter的deputy Editor-in-Chief，IEEE Trans. on CAD, ACM JETC, VLSI Integration等期刊的Associate Editor, 以及ACM SIGDA的Education Chair。

關(guān)于定位車輛的關(guān)鍵技術(shù)“計算機(jī)算法中最直接的greedy approach”，史教授說，其實就是一個螺旋搜索，確保他們始終在沿著距離下降的方向單調(diào)搜索一定可以收斂的。

貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。

百度北京大數(shù)據(jù)實驗室主任浣軍教授認(rèn)為，史教授用greedy approach是個凸優(yōu)化問題，他始終能測距離。

“設(shè)想平面內(nèi)有個點x0，你的目標(biāo)函數(shù)是f(x,x0）f 是euclidian distance between x and x0，歐式距離是個凸函數(shù)，全局最優(yōu)解存在切唯一，x0。”

史教授的算法簡而言之是每一步都減少距離，所以是貪心算法。

所以啊，不要惹會算法的人！