清華大學部再出神人，汽車被盜，用“貪心演算法”瞬間找到偷車賊

史教授說當然啊，于是警察就說那你找到了再打電話給我們吧，然后就開車走了。

惹誰

都不要惹會演算法的人

今天要講的故事的主人公，是來自圣母大學部計算機系的副教授史戈宇。就在之前，他還經歷了一場驚心動魄的劫車事件，

度假旅游遇劫匪

在某一個周末，史教授計劃著開車帶一家人去百慕大度假旅行，一家人從印第安納的South Bend出發，中午12點左右到達了芝加哥中國城。

當時史教授發現Mazda CX-9提示胎壓例外，于是決定開車前往附件的加油站給輪胎充氣。

但由于加油站的設備簡陋，沒有胎壓讀數，史教授想著要不換個加油站試試，

跟我們平常出去關門一樣，上車后史教授覺得右前輪的氣門帽好像沒擰緊，于是決定下車看看，

剛下車，就有兩個20來歲的黑人從后面的一輛車下來并靠近史教授，其中一個人直接用一把槍指著他：“See the gun? Give me your wallet. Give me your key.”另一個劫匪則鉆進了駕駛室并且讓所有人下車，

因為車里還有小孩和孕婦，安全起見，史教授很配合劫匪，把錢包給了他們，劫匪要史教授趕緊把車鑰匙給他。與此同時，車里的另一個劫匪也在催車里的人下車。

史教授發現他們并沒有關上駕駛座的門，于是趁機把行動電話扔到了門上的夾袋里，希望對后續追蹤能有所幫助。

報警911 警察無作為

大家都下車后，劫匪也一溜煙開車跑了，而史教授一家的行李，包括護照綠卡還留在尾箱，

由于劫匪并沒有搶走史教授太太的行動電話，她的行動電話就成了史教授一家人的唯一通訊工具，

被搶之后史教授立馬撥打了911，第一次大約等了十幾秒并沒有被接通，直到第三次電話才打通。

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

于是他繼續撥打911，這一次接線員在聽了案情描述后，幫他轉接到了芝加哥中央警察局，但中央警察局的接線員又表示：”This is a true emergency and you should call 911 directly.“（你應該打給911啊）

打個電話卻跟踢皮球一樣，史教授非常生氣，說道：我打了，但是是他們把我轉過來的！

于是，接線員又幫轉回了911，最后的接線員終于說派警察過來，此時離搶劫發生已經過去了大約十分鐘，

過了大約十分鐘，與美國大片里的大量警車閃著警燈蜂擁而至的場景不同，只來了一輛警車，下來了兩個警察，仔細的詢問了案發的經過，包括有沒有看清劫匪的長相、年齡等。

史教授：“我說你們能不能先幫我去追一下車子，這些資訊我慢慢給你提供，“

警察：”別擔心，一旦獲得了所需的所有資訊，就會將史教授的車牌資訊輸入系統并發布給執行的警察，“

最后，等警察處理完所有的事情時，距車子被劫走已經過去了整整半小時，

警察發現加油站有監控，于是進到店里準備看監控。但沒過一會，他們就放棄了，因為他們倆不知道怎么上傳視訊……還告訴史教授會有偵探來處理這件事，他們只能幫到這里了，

兩警察剛準備上車離去時，又跑過來問史教授：“你的Mazda CX-9 是臺兩門的對吧?”

史教授聽了表示已經完全無語了，敢情你就沒把我之前的話聽進去？

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

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

然后警察立刻沖回車里拿起對講機說：“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。

所以在新的行動電話上登入需要首先通過自己的行動電話或者辦公室電話驗證，但這兩條途徑都沒有辦法使用，但由于周末學校也沒人，史教授也放棄了，

夢引起的找車思路

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

回到家后，史教授找朋友借了臺電腦，立刻趕回學校，利用辦公室的電話通過了two step verification,，登入了find my phone的網頁，

雖然last seen的日期是當天，但已經無法顯示實時位置了，看來劫匪對電子產品的追蹤功能還是非常了解，找車是無望了，

回到家后，身心疲憊的史教授很快就睡著了。史教授做了個夢，

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

這個夢也讓他想起了一件事：當時在買車的時候，他們討價還價了很久，到最后價格實在壓不下來時，就讓對方給免費裝了一個Mazda Mobile Start (MMS)，可以利用行動電話遠程發動汽車引擎，給車輛上鎖和開鎖，”

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

史教授馬上打開電腦搜了一下，發現果然MMS還有一個附帶功能，就是幫你找到停車地點，

于是他立刻在行動電話上登入這個app，但發現密碼始終不正確，最后他去網上找了MMS的說明，閱讀后發現了可能沒續租……

于是史教授嘗在網上續租了一年的服務，果然，他順利的登入進了app。

“不得不說，馬自達的IT實在是太爛了，從軟體工程角度來說，沒有續租導致的無法登入居然顯示密碼錯誤，這是UI設計的反面典型。

只是這樣也就算了，當我在app里找到CarFinder的界面，他的顯示就是一個紅點和一個大圈，紅點代表車的位置，大圈代表車的范圍，然后右上角有距離顯示81.8英里和相對誤差+/- 22 英尺，沒有地圖，沒有提供GPS坐標。”

所以，史教授除了能知道他和車的直接距離和相對位置，別的什么都不知道（后來發現其實那個相對位置也只有距離車很近的時候才會比較準，距離遠的時候完全可能是錯的）。

他還順便看了一下引擎的狀態，是OFF的，說明車子被停在了某個地方，

也算是有車的線索了，史教授立馬打電話給911，結果接線員說這事兒不緊急，要他直接聯系芝加哥中央警察局。

史教授又打給芝加哥警局，接電話的警員表示這個事情你得告訴負責你的案子的偵探啊，但今天周末他不在辦公室里，我幫你轉到他語音信箱吧，這樣他上班就能第一時間知道。

史教授聽了，雖然憤怒，但還是耐著性子說：“這事難道不是越早解決越好嘛？”

“那行吧，你把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，也就是沿著一個方向開，直到距離不再明顯變小（這是說明我們前進的方向已經幾乎垂直于我們和目標之間連線），就轉到垂直方向的街道再繼續搜尋，

在小區中兜了一段時間以后，終于在S Eberhart Ave在101st St和102nd St之間某個位置直接距離顯示為200英尺，說明離目標已經很近了，

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

轉來轉去，他們最后發現，原來在S Vernon Ave和S Eberhart Ave之間還有一條小路，這條路并沒有名字，在google地圖上甚至沒有顯示，但在上面這張衛星圖里面可以看到這條路的存在（紅色標記左側的第一條路），

于是他們從101st St上轉入了這條小路，入口是這樣的，

史教授他們保持緩慢的速度進入了小路，進入就發現MMS里提示的距離又開始明顯下降，直到開過倒數第三間車庫的時候，車庫門是關著的，但距離顯示小于5英尺，MMS發出提示音，看來車子就在里面！

沒有過多的停留，在轉到102nd St上后，史教授撥打了911，告訴接線員找到了被劫車輛。接線員問清了位置和所在的車輛資訊后，讓他們在原地等待警察，

就在他們緊張的等待時，史教授發現自己與被劫車輛的距離已經變成了1.5英里，而且引擎已經啟動，說明車輛正在行駛中！

懊悔之余，史教授撥打了911，并且決定跟上馬自達！但不幸的是，MMS并不是設計用來追蹤行駛狀態下的車輛的，因此車的位置和距離更新不是實時的，

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

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

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

在接下來的一個多小時里，史教授和警察一共通了三次電話：第一次，警察問我那個追蹤軟體在哪里，是不是google地圖? 第二次，警察說距離很近了，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!”

那當然，我們史教授可是個牛人！說出來嚇死你們！

史弋宇

現任圣母大學部計算機系終身副教授，博士生導師，并兼任電子系終身副教授, 該校美國國家科學基金委新型可持續人工智能產學研究中心主任，之前任密蘇里大學部羅拉分校助理教授，博士生導師，美國國家科學基金委基于網路的軟體系統產學研究中心副主任。

史教授于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是個凸優化問題，他始終能測距離。

學霸不可怕，會演算法的學霸最可怕！惹誰都不能惹會演算法的人！（還有，我們真不是給馬自達打廣告啊）