來源 | 異步 | 文末贈書
春節假期已經結束了，但來勢洶洶的武漢肺炎成功將大家困在家中，不得不選擇遠程辦公。
從1月20日官方公佈感染武漢新型冠狀病毒患者激增之後，讓大家突然失去了自由，將近半個月都不能出門。但實質上這場病毒的襲擊在12月底就已經開始了。
面對新型病毒的強傳染性和長潛伏期，我們確實被打了個猝不及防。如果能夠早發現早重視，後續局面便不會如此被動。
遠在大洋的彼岸，加拿大的一個名叫BlueDot的健康監測就通過AI驅動的算法，在12月31日就早早向其客戶發出了疫情的消息。
他們通過使用AI驅動的算法，搜索了外語新聞報道、動植物疾病網絡以及官方公告，並向其客戶提前發出警告，使得他們避開了如武漢等感染概率較大的危險區域。
BlueDot的創始人兼首席執行官Kamran Khan表示，通過訪問全球機票數據，算法可以幫助預測下一個受感染居民的去向和時間。
“我們所做的是使用自然語言處理和機器學習來訓練該引擎進行識別。”Khan說：“一旦完成自動數據篩選，人工分析就將接手。流行病學家從科學的角度檢查得出的結論是否合理，然後將報告發送給政府，企業和公共衛生客戶。”
通過這套AI驅動的算法，他們成功地預測了該病毒在首次出現後的幾天內將從武漢傳播到曼谷、漢城、臺北和東京。
算法的重要性，從業者早已心中有數。如今，算法和AI的結合，竟然在流行病的爆發預警上也發揮了作用，這不僅為傳染病防範工作提供了新的探索方向，更為算法的應用落地拓寬了新的邊界。
我們常說算法很重要，在這種危急關頭，更能體驗其的實用性和重要性。對初學者來說，算法是枯燥難懂的，那今天異步君給大家介紹一些比較常用的算法思想，一起來看看吧！
八大算法思想
初學者入門算法往往會覺得種類繁多，無從下手。但很多非常有效的算法，實際上只是某個通用算法的特殊實現，掌握了通用算法的思想在應用的時候就能舉一反三。業界目前公認的常用算法思想有8種，分別是枚舉、遞推、遞歸、分治、貪心、試探、 迭代和模擬。
1、枚舉法
枚舉算法思想的最大特點是，在面對任何問題時它會去嘗試每一種解決方法。在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那麼這個結論是可靠的，這種歸納方法叫作枚舉法。
枚舉算法的思想：將問題的所有可能的答案一一列舉，然後根據條件判斷此答案是否合適，保留合適的，丟棄不合適的。在C語言中，枚舉算法一般使用while循環實現。使用枚舉算法解題的基本思路如下。
① 確定枚舉對象、枚舉範圍和判定條件。
② 逐一列舉可能的解，驗證每個解是否是問題的解。
枚舉算法一般按照如下3個步驟進行：
① 題解的可能範圍，不能遺漏任何一個真正解，也要避免有重複。
② 判斷是否是真正解的方法。
③ 使可能解的範圍降至最小，以便提高解決問題的效率。
2、遞推法
與枚舉算法思想相比，遞推算法能夠通過已知的某個條件，利用特定的關係得出中間推論，然後逐步遞推，直到得到結果為止。由此可見，遞推算法要比枚舉算法聰明，它不會嘗試每種可能的方案。
遞推算法基礎
遞推算法可以不斷利用已有的信息推導出新的東西，在日常應用中有如下兩種遞推算法。
① 順推法：從已知條件出發，逐步推算出要解決問題的方法。例如斐波那契數列就可以通過順推法不斷遞推算出新的數據。
② 逆推法：從已知的結果出發，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程。
3、遞歸法
因為遞歸算法思想往往用函數的形式來體現，所以遞歸算法需要預先編寫功能函數。這些函數是獨立的功能，能夠實現解決某個問題的具體功能，當需要時直接調用這個函數即可。
遞歸算法基礎
在計算機編程應用中，遞歸算法對解決大多數問題是十分有效的，它能夠使算法的描述變得簡潔而且易於理解。遞歸算法有如下3個特點。
① 遞歸過程一般通過函數或子過程來實現。
② 遞歸算法在函數或子過程的內部，直接或者間接地調用自己的算法。
③ 遞歸算法實際上是把問題轉化為規模縮小了的同類問題的子問題，然後再遞歸調用函數或過程來表示問題的解。
在使用遞歸算法時，應該注意如下4點：
① 遞歸是在過程或函數中調用自身的過程。
② 在使用遞歸策略時，必須有一個明確的遞歸結束條件，這稱為遞歸出口。
③ 遞歸算法通常顯得很簡潔，但是運行效率較低，所以一般不提倡用遞歸算法設計程序。
④ 在遞歸調用過程中，系統用棧來存儲每一層的返回點和局部量。如果遞歸次數過多，則容易造成棧溢出，所以一般不提倡用遞歸算法設計程序。
4、分治法
分治算法採取了各個擊破的方法，將一個規模為 N 的問題分解為 K 個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。只要求出子問題的解，就可得到原問題的解。
分治算法基礎
在編程過程中，經常遇到處理數據相當多、求解過程比較複雜、直接求解法會比較耗時的問題。在求解這類問題時，可以採用各個擊破的方法。
具體做法：先把這個問題分解成幾個較小的子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個大問題的解。如果這些子問題還是比較大，還可以繼續再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治算法的基本思想。
使用分治算法解題的一般步驟如下：
① 分解，將要解決的問題劃分成若干個規模較小的同類問題。
② 求解，當子問題劃分得足夠小時，用較簡單的方法解決。
③ 合併，按原問題的要求，將子問題的解逐層合併構成原問題的解。
5、貪心法
貪心算法也被稱為貪婪算法，它在求解問題時總想用在當前看來是最好方法來實現。這種算法思想不從整體最優上考慮問題，僅僅是在某種意義上的局部最優求解。
雖然貪心算法並不能得到所有問題的整體最優解，但是面對範圍相當廣泛的許多問題時，能產生整體最優解或者是整體最優解的近似解。由此可見，貪心算法只是追求某個範圍內的最優，可以稱之為“溫柔的貪婪”。
貪心算法基礎
貪心算法從問題的某一個初始解出發，逐步逼近給定的目標，以便儘快求出更好的解。當達到算法中的某一步不能再繼續前進時，就停止算法，給出一個近似解。由貪心算法的特點和思路可看出，貪心算法存在以下3個問題。
① 不能保證最後的解是最優的。
② 不能用來求最大或最小解問題。
③ 只能求滿足某些約束條件的可行解的範圍。
貪心算法的基本思路如下：
① 建立數學模型來描述問題。
② 把求解的問題分成若干個子問題。
③ 對每一子問題求解，得到子問題的局部最優解。
④ 把子問題的局部最優解合併成原來解問題的一個解。
實現該算法的基本過程如下：
（1）從問題的某一初始解出發。
（2）while能向給定總目標前進一步。
（3）求出可行解的一個解元素。
（4）由所有解元素組合成問題的一個可行解。
6、試探法
試探法也叫回溯法，試探法的處事方式比較委婉，它先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一進行枚舉和檢驗。
當發現當前候選解不可能是正確的解時，就選擇下一個候選解。如果當前候選解除了不滿足問題規模要求外能夠滿足所有其他要求時，則繼續擴大當前候選解的規模，並繼續試探。
如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在試探算法中，放棄當前候選解，並繼續尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，並繼續試探的過程稱為向前試探。
試探法算法基礎
使用試探算法解題的基本步驟如下所示。
① 針對所給問題，定義問題的解空間。
② 確定易於搜索的解空間結構。
③ 以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。
試探法為了求得問題的正確解，會先委婉地試探某一種可能的情況。在進行試探的過程中，一旦發現原來選擇的假設情況是不正確的，立即會自覺地退回一步重新選擇，然後繼續向前試探，如此這般反覆進行，直至得到解或證明無解時才死心。
假設存在一個可以用試探法求解的問題P，該問題表達為：對於已知的由n元組（y1，y2，…，yn）組成的一個狀態空間E={（y1，y2，…，yn）∣yi∈Si，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。
其中，Si是分量yi的定義域，且|Si|有限，i=1，2，…，n。E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最簡單方法是使用枚舉法，即對E中的所有n元組逐一檢測其是否滿足D的全部約束，如果滿足，則為問題P的一個解。但是這種方法的計算量非常大。
對於現實中的許多問題，所給定的約束集D具有完備性，即i元組（y1，y2，…，yi）滿足D中僅涉及y1，y2，…，yj的所有約束，這意味著j（j
換句話說，只要存在0jn−1，使得（y 1，y 2，…，yj）違反D中僅涉及y1，y2，…，yj的約束之一，則以（y1，y2，…，yj）為前綴的任何n元組（y1，y2，…，yj，yj+1，…，yn）一定也違反D中僅涉及y 1，y 2，…，yi的一個約束，ni>;j。
因此，對於約束集D具有完備性的問題P，一旦檢測斷定某個j元組（y1，y2，…，yj）違反D中僅涉及y1，y2，…，yj的一個約束，就可以肯定，以（y1，y2，…，yj）為前綴的任何n元組（y1，y2，…，yj，yj+1，…，yn）都不會是問題P的解，因而就不必去搜索它們、檢測它們。試探法是針對這類問題而推出的，比枚舉算法的效率更高。
7、迭代法
迭代法也稱輾轉法，是一種不斷用變量的舊值遞推新值的過程，在解決問題時總是重複利用一種方法。與迭代法相對應的是直接法（或者稱為一次解法），即一次性解決問題。迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬於近似迭代法，功能都比較類似。
迭代算法基礎
迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點，讓計算機對一組指令（或一定步驟）進行重複執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。
在使用迭代算法解決問題時，需要做好如下3個方面的工作。
（1）確定迭代變量
在可以使用迭代算法解決的問題中，至少存在一個迭代變量，即直接或間接地不斷由舊值遞推出新值的變量。
（2）建立迭代關係式
迭代關係式是指如何從變量的前一個值推出其下一個值的公式或關係。通常可以使用遞推或倒推的方法來建立迭代關係式，迭代關係式的建立是解決迭代問題的關鍵。
（3）對迭代過程進行控制
在編寫迭代程序時，必須確定在什麼時候結束迭代過程，不能讓迭代過程無休止地重複執行下去。通常可分為如下兩種情況來
控制迭代過程：① 所需的迭代次數是個確定的值，可以計算出來，可以構建一個固定次數的循環來實現對迭代過程的控制；
② 所需的迭代次數無法確定，需要進一步分析出用來結束迭代過程的條件。
8、模擬法
模擬是對真實事物或者過程的虛擬。在編程時為了實現某個功能，可以用語言來模擬那個功能，模擬成功也就相應地表示編程成功。
模擬算法的思想
模擬算法是一種基本的算法思想，可用於考查程序員的基本編程能力，其解決方法就是根據題目給出的規則對題目要求的相關過程進行編程模擬。
在解決模擬類問題時，需要注意字符串處理、特殊情況處理和對題目意思的理解。在C語言中，通常使用函數srand()和rand()來生成隨機數。
其中，函數srand()用於初始化隨機數發生器，然後使用函數rand()來生成隨機數。如果要使用上述兩個函數，則需要在源程序頭部包含time.h文件。
在程序設計過程中，可使用隨機函數來模擬自然界中發生的不可預測情況。在解題時，需要仔細分析題目給出的規則，要儘可能地做到全面考慮所有可能出現的情況，這是解模擬類問題的關鍵點之一。
在看完了這8大算法思想後，大家對算法有了一定了解。但僅憑一篇文章，在職場是遠遠無法立足的！要想吃透算法，還需要系統化學習。異步君今天就為大家推薦3本算法領域的名家名作！
人工智能算法 （卷1）：基礎算法
作者： [美] 傑弗瑞·希頓（Jeffery Heaton）
● 算法是人工智能技術的核心，本書介紹了人工智能的基礎算法；
● 涉及維度法、距離度量算法、模擬退火算法、Nelder-Mead 算法和線性迴歸算法等；
● 適合作為人工智能入門讀者以及對人工智能算法感興趣的讀者 閱讀參考。
趣學算法
● 介紹經典的算法設計策略、實戰演練、算法分析及優化拓展；
● 共45個大型實例，包括經典的構造實例和實際應用實例；
（搶讀版 ）圖解數據結構與算法
● 本書共7章，採用圖解+步驟的方式介紹了數據結構中的常見概念以及相應算法，其內容涵蓋了基本的數據結構、遞歸與動態規劃、樹、堆、圖、比較排序、非比較排序等。
● 本書注重於從理論上來幫助讀者掌握相應內容，不涉及具體的編碼實現，特別適合沒有編碼基礎的讀者閱讀。
-END-
今日福利
《趣學算法》
如何獲得：在看+參與話題留言+轉發本文至朋友圈，2月15日，異步君將抽取2名讀者贈送《趣學算法》。
今日互動話題：
“你在學算法時遇到哪些困難？”
閱讀更多 異步社區 的文章
