人類總是崇敬知識，但并非崇敬所有知識，不少人曾問出過那個振聾發(fā)聵的問題：" 高數(shù)有什么用 ? 買菜用得上嗎 ?" 面對高數(shù)態(tài)度如此，更復(fù)雜的算法知識就更不用說了。不過，一位清華畢業(yè)計算機(jī)教授在美國的經(jīng)歷證明了，算法或許不能在買菜時幫你省幾個小錢，但可以在遇到重大事件時，幫你賺回 1 臺車錢。

12 月下旬，清華畢業(yè)、現(xiàn)任圣母大學(xué)計算機(jī)系終身副教授、博士生導(dǎo)師、電子系終身副教授史弋宇原計劃從芝加哥經(jīng)紐約前往百慕大旅游，不巧的是，他們在途中遇到了 2 名持槍匪徒，不僅搶走了他的錢包，" 順便 " 還開走了他的車。萬幸，在警方已經(jīng)半放棄的情況下，他憑借自己強(qiáng)大的邏輯能力和算法思維，獨(dú)自找到了車子，雖然旅行泡湯，但至少損失挽回了大半。

事情起于當(dāng)天中午，當(dāng)時，他們在芝加哥中國城附近的加油站給輪胎充氣，趁他不在車上，2 個身材不高大約 20 來歲的黑人從后面車上下來，對他舉起了槍。之后，他們把所有人趕下車，錢拿走，大搖大擺地開走了，順帶帶走了史教授一家所有的行李，只給他們留了幾個空空的錢包。

之后警方登場了——和諸多美國電影一樣，扮演的是反面角色。第 1 次報警，911 表示無法查詢到史教授的車牌信息 ; 第 2 次報警，911 幫史教授轉(zhuǎn)接芝加哥中央警察局，警察局表示，這事歸 911 管 ; 第 3 次報警，終于有警察到場，但是在現(xiàn)場草草轉(zhuǎn)了一圈之后，他們就草草離去了。

警方不靠譜，史教授只能靠自己。在被搶時，史教授耍了個小心機(jī)，悄悄把手機(jī)留在了車子上，一開始，他寄望于手機(jī)定位能幫他找到車，然而劫匪對電子產(chǎn)品的追蹤功能非常清楚，相關(guān)功能已經(jīng)無法顯示實(shí)時位置。之后，他又想到了自己馬自達(dá)車上幾乎沒用過的 Maza Mobile Start ( MMS ) 功能。

這個設(shè)備的作用是讓車主用手機(jī)遠(yuǎn)程發(fā)動汽車引擎，給車輛上鎖和開鎖。那么，既然能用手機(jī)遠(yuǎn)程控制車子，在安裝這個 MMS 的時候也一定啟動了 GPS 定位的功能。史教授上網(wǎng)一看，果然，MMS 具備 "CarFiner" 的功能，可以大略顯示車輛位置和發(fā)動機(jī)的啟動狀態(tài)。之后，這個功能就成了找到車子的關(guān)鍵。

首先介紹一下這個功能，在 CarFiner 界面中會顯示 1 個紅點(diǎn)和 1 個大圈，紅點(diǎn)代表車的位置，大圈代表車的范圍，然后右上角有距離顯示 81.8 英里和相對誤差 +/- 22 英尺。沒有地圖，沒有提供 GPS 坐標(biāo)，換句話說，車主只能知道他和車的直接距離和相對位置。放在一般人身上，信息如此匱乏，基本上可以放棄了。然而，史教授的算法思維在這時候發(fā)揮了關(guān)鍵作用。

他先是按照 CarFiner 指示的相對距離，推斷出車子大概是在芝加哥南郊。至于對不對，只要上路隨便找 1 個方向開，距離縮短就是對的。結(jié)果上了朝芝加哥南郊的高速后，直線距離果然在快速減小，方向是正確的。

當(dāng)新車到達(dá)芝加哥南郊 I-94 130th st 出口時，他們和馬自達(dá)的距離已經(jīng)減小到了 2 英里，車子很可能就在出口下面某處。不過，于是史教授從該出口下去以后轉(zhuǎn)了一圈，發(fā)現(xiàn)周圍都是公園，而且距離也沒有繼續(xù)減小，于是又開回高速。根據(jù)這種方法，史教授一路走一路縮小范圍，最后對應(yīng)地圖，把目標(biāo)確定在了下圖中的 Roselan 中。

在小范圍內(nèi)，相對位置就不那么靠譜了，于是，史教授選擇了計算機(jī)算法中最直接的貪婪算法，也就是沿著一個方向開，直到距離不再明顯變小 ( 這是說明我們前進(jìn)的方向已經(jīng)幾乎垂直于我們和目標(biāo)之間連線 )，就轉(zhuǎn)到垂直方向的街道再繼續(xù)搜尋。

值得一提的是，在他們打到 Roselan 小區(qū)后，有 1 輛白色小車一直跟在他們后面，跟了好幾個街區(qū)，由于對方有槍，史教授和他招來幫忙的學(xué)生小王約定，無論如何不要停車，就算停車，也要保持在 D 襠，隨時準(zhǔn)備開動。

在小區(qū)內(nèi)轉(zhuǎn)悠半天后，他們終于在直線距離 200 英尺的地方，轉(zhuǎn)進(jìn)了 1 條小路。在這條小路上，MMS 顯示的距離一路縮短，當(dāng)開到盡頭倒數(shù)第 3 間緊閉著的車庫時，MMS 發(fā)出提示音：車子就在里面 !

史教授立刻通知了警察，為了避免打草驚蛇和確保自身安全，他們并沒有在那里過多停留，而是選擇開出大路等待。然而，沒等警察來到，MMS 上面突然顯示車輛發(fā)動，而且離他們越來越遠(yuǎn)。2 名警察到場知悉劫匪跑掉后，讓史教授在路邊等待，他們會去追蹤。

之后，警察再次開始了他們的愚蠢表演。在 3 通電話中，警方第 1 通是問史教授軟件怎么用 ; 第 2 次警察說他們已經(jīng)靠到了 400 米，史教授告訴他 MMS 還有個 panic 功能，手機(jī)上點(diǎn)擊后可以讓車發(fā)出很大的警報聲 ; 最后 1 次，警察說沒找到車，于是史教授只能自己繼續(xù)尋找。

好在，有了上午的成功經(jīng)驗(yàn)，史教授輕車熟路地用貪婪算法，很快在另外一地的加油站找到了被劫車輛。這次他們把車停在了可以看到被劫車輛的位置，才打了 911，而且為了防止警方 30-40 分鐘不到、1 次只派 2-3 個人的現(xiàn)象再度出現(xiàn)，他故意把情況報告的更加嚴(yán)重。

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

于是，整輛車 " 完璧歸趙 "，不僅如此，史教授還在車?yán)镎业搅艘恍┎粚儆谧约旱臇|西，比如 1 雙嶄新的 Nike、一些吃剩的飲食包裝，還有彌漫在車?yán)锏拇舐槲?。只花?1 天就找到被劫車輛，這種遠(yuǎn)超警方的效率，讓警察也不由得感慨道："They shouln ’ t have messe up with computer science professors!"

最后再來介紹一下本次行動的功臣——貪心算法。貪心算法又稱貪婪算法，是指在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，做出的是在某種意義上的局部最優(yōu)解。

貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。

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

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

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

“設(shè)想平面內(nèi)有個點(diǎn)x0，你的目標(biāo)函數(shù)是f(x,x0）f 是eucliian istance between x an x0，歐式距離是個凸函數(shù)，全局最優(yōu)解存在切唯一，x0?！?/p>

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

【微語】你在遠(yuǎn)方的校園里,用知識點(diǎn)亮未來,用堅韌書寫青春的華章。