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

千萬別惹計算機教授。

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

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

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

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

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

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

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

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

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

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

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

劫匪隨后把錢包還給史教授，又讓他趕緊把車鑰匙交給劫匪。與此同時，車里的另一個劫匪繼續(xù)催促所有人下車。

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

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

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

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

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

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

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

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

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

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

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

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

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

于是他們打算開車離去。

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

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

這時史教授已經完全無語了：

“長官，是個四門的SUV?！?/p>

“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”

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

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

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

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

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

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

轉折：手機發(fā)動應用程序成為關鍵，史教授決定靠自己尋車

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

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

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

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

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

“我的判斷是既然能用手機遠程控制車子，那在安裝這個MMS的時候也一定啟動了 GPS定位的功能。”

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

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

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

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

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

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

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

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

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

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

當時是早上六點，于是史教授滿懷歉疚的打了個電話給他的一個平時還挺機靈的學生小王，請他陪同一起去趟芝加哥找車。小王二話不說就趕了過來，兩人在全家人充滿憂慮的目送中開車駛入了黎明前的黑暗里。

史教授把駕駛任務交給了小王，而他則開始在車上進行一些信息搜集和準備工作。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

車子就在里面！

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

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

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

打草驚蛇了。

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

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

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

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

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

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

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

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

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

這次史教授直接告訴接線員：我看到了被劫車輛，就在我不遠處，車里好像有人，他們還有槍。

“我知道不把情況說的嚴重一些，他們是不會認真嚴肅對待的”。

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

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

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

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

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

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

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

史弋宇

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

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

史教授目前的研究方向主要是人工智能的硬件實現(xiàn)和在醫(yī)療等領域的應用。他曾獲得美國國家自然基金委CAREER獎，IEEE Region 5個人成就獎，卡爾圣路易科學院發(fā)明獎等；多次在領域內頂級國際會議上獲得最佳論文提名。他獲得美國發(fā)明專利5項(其中一項于2009年獲得IBM專利獎，一項獲得臺北國際博覽會金獎）；在國際重要研究期刊和會議上發(fā)表學術論文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。

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

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

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

“設想平面內有個點x0，你的目標函數(shù)是f(x,x0）f 是euclidian distance between x and x0，歐式距離是個凸函數(shù)，全局最優(yōu)解存在切唯一，x0?！?/p>

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

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