EEWorld
電子資訊 犀利解讀
技術乾貨 每日更新
人類總是崇敬知識，但並非崇敬所有知識，不少人曾問出過那個振聾發聵的問題：「高數有什麼用?買菜用得上嗎?」面對高數態度如此，更複雜的算法知識就更不用說了。不過，一位清華畢業計算機教授在美國的經歷證明了，算法或許不能在買菜時幫你省幾個小錢，但可以在遇到重大事件時，幫你賺回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.」 並且反覆重複說，神情緊張。另一個劫匪則鑽進了駕駛室讓所有人下車。
史教授考慮到車裡還有孕婦和小孩，為了安全起見，就很配合的把錢包遞給了劫匪，劫匪打開後從裡面拿出了所有的現金。
劫匪隨後把錢包還給史教授，又讓他趕緊把車鑰匙交給劫匪。與此同時，車裡的另一個劫匪繼續催促所有人下車。
「我發現他並沒有關上駕駛座的門，就趁此機會把我的手機扔到了門上的夾袋裡，希望對後續追蹤有所幫助。」
在大家都下車後，劫匪一溜煙的就把車開跑了，而史教授一家所有的行李，包括護照、綠卡等等，都還在車尾箱裡。
劫匪並沒有搶走史教授太太的手機，她的手機就成了史教授一家人的唯一通訊工具。
被搶之後史教授首先撥打911，第一次大約等了十幾秒並沒有被接通。於是第二次再打，還是沒有成功（所以關鍵時候911也不一定靠譜) 第三次再打，終於通了。
但911接線員卻告知：無法查詢到史教授的車牌信息（I cannot find your license plate number sir）。
「我被劫匪持槍搶了車，打911報警，居然還得自己去警察局做筆錄，估計等我搞完，車都已經被chop shop大卸八塊了。」
於是他繼續撥打911。這一次接線員好了一些，在史教授又一次描述了案情後，接線員幫轉到了芝加哥中央警察局，對方的接線員又問了一遍情況，說這個你應該打給911啊（This is a true emergency and you should call 911 directly.）
「我都想罵人了，忍住氣繼續說我打了，但是是他們把我轉過來的。」於是，接線員又幫轉回了911，最後的接線員終於說派警察過來，此時離搶劫發生已經過去了大約十分鐘。
又等了大約十分鐘，和史教授想像中大量警車閃著警燈蜂擁而至的場景不同，只來了一輛警車。車上下來了兩個警察，仔細的詢問了案發的經過，包括有沒有看清劫匪的長相、年齡等。
「我說你們能不能先幫我去追一下車子，這些信息我慢慢給你提供。但警察說，別擔心，一旦獲得了所需的所有信息，就會將史教授的車牌信息輸入系統並發布給執行的警察。
最後，當警察處理完時，離史教授的車被劫走已經過了整整半個小時。
接著，警察發現加油站裡布滿了監控攝像頭，於是進到店裡要看監控。但不一會兒那個警察就出來了，問另一個警察：我不知道怎麼上傳這些視頻，你會嗎？另一個警察回答：我也不會啊。他們於是告訴史教授：沒關係，會有偵探會來料理這個視頻， 我們的事情就辦到這裡啦！
於是他們打算開車離去。
但剛上車又下來問史教授：
「你的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的界面，他的顯示就是一個紅點和一個大圈，紅點代表車的位置，大圈代表車的範圍，然後右上角有距離顯示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之間還有一條小路，這條路並沒有名字，在谷歌地圖上甚至沒有顯示，但在上面這張衛星圖裡面可以看到這條路的存在（紅色標記左側的第一條路）。於是他們從101st St上轉入了這條小路，入口是這樣的。
當時時間大概是早上八點多一點，周圍一個人都沒有，史教授他們保持緩慢的速度進入了小路。
一進入就發現MMS裡提示的距離又開始明顯下降，直到開過倒數第三間車庫的時候，車庫門是關著的，但距離顯示小於5英尺，MMS發出提示音：
車子就在裡面！
他們二人沒有敢多停留，在轉到102nd St上後，史教授立刻撥打911，告訴接線員找到了被劫車輛。接線員問清了位置和所在的車輛信息後，讓他們在原地等待，警察很快會到。
就在他們緊張的在路邊等待的時候，小王提醒說，看看現在我們和被劫車輛的距離。史教授看了一下，大吃一驚：此時距離已經變成了1.5英裡，而且引擎已經啟動，說明車輛正在行駛中！
打草驚蛇了。
於是史教授一邊懊悔應該把車停到一個能看得到那個車庫的位置，一邊立刻決定要跟上馬自達。但不幸的是，MMS並不是設計用來追蹤行駛狀態下的車輛的，因此車的位置和距離更新不是實時的。
於是二人漫無目的的在路上行駛，希望有機會能看到這輛馬自達。就這樣找了十多分鐘後，兩個警察來了，史教授向他們簡單描述了如何尋找到被劫車輛的位置，並且告訴他們劫匪又跑了。
警察從史教授手裡借走了手機，讓他們在路邊等待，警察會去追蹤。這時史教授告訴了警察如何使用MMS定位，並再三強調只能相信距離，不要去看相對位置。
警察留了手機之後，很快就開走了。但史教授決定還是繼續在附近尋找，而不是在路邊等待，一方面是碰碰運氣，另一方面則是出於安全考慮，不想要停留在一個地方。
在接下來的一個多小時裡，史教授和警察一共通了三次電話：第一次，警察問我那個追蹤軟體在哪裡，是不是谷歌地圖? 第二次，警察說距離很近了，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。」
史教授的算法簡而言之是每一步都減少距離，所以是貪心算法。
所以啊，不要惹會算法的人！
來源：新智元，如涉及版權問題，請聯繫刪除。
聚焦行業熱點， 了解最新前沿
敬請關注EEWorld電子頭條
http://www.eeworld.com.cn/mp/wap
複製此連結至瀏覽器或長按下方二維碼瀏覽
以下微信公眾號均屬於
EEWorld（www.eeworld.com.cn）
歡迎長按二維碼關注！
EEWorld訂閱號：電子工程世界
EEWorld服務號：電子工程世界福利社