算法範式

算法：按步驟解決問題的過程。

An algorithm is a step-by-step procedure for solving a problem.

範式：思考問題的模式。

"Pattern of thought" which governs scientific apprehension during a certain period of time.

算法範式：為問題建構高效解決方案的正常方法。

General approaches to the construction of efficient solutions to problems。

算法範式可以被看做為解決一類問題的高層算法。

算法範式提供的模闆可适用于解決更廣泛的問題。

通過最高層的語言可以将範式轉換成通用的元件或資料結構。

對算法産生結果所需的時間和空間的需求可以做精确的分析。

常見的算法範式有：

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#brute_force_paradigm">暴力破解法（Brute Force Paradigm）</a>

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#divide_and_conquer_paradigm">分治法（Divide and Conquer Paradigm）</a>

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#dynamic_programming_paradigm">動态規劃法（Dynamic Programming Paradigm）</a>

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#greedy_paradigm">貪心算法（Greedy Paradigm）</a>

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#backtracking_paradigm">回溯法（Backtracking Paradigm）</a>

<a href="http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html#branch_and_bound_paradigm">分支限界法（Branch and Bound Paradigm）</a>

暴力破解法簡單直接，根據問題聲明的定義，找到所有可變化的因子（Divisor），窮舉所有可能解決問題的方法，逐個嘗試。

是以，根據暴力破解法的定義，理論上講任何問題都可以使用暴力破解法來解決，隻是在實際應用中算法對時間和空間的需求則無法滿足。

将暴力破解法應用于資料查找，由于查找比較次數與給定目标的規模直接相關，是以也稱為線性查找（Linear Search）。

線性查找有很多典型應用：

<a href="http://www.cnblogs.com/gaochundong/p/comparison_sorting_algorithms.html#selection_sort" target="_blank">選擇排序（Selection Sort）</a>

<a href="http://www.cnblogs.com/gaochundong/p/comparison_sorting_algorithms.html#bubble_sort" target="_blank">冒泡排序（Bubble Sort）</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html" target="_blank">順序查找（Sequential Search）</a>

<a href="http://www.cnblogs.com/gaochundong/p/string_matching.html#naive_string_matching_algorithm" target="_blank">暴力字元串比對（Naive String Match）</a>

分治法（Divide-and-Conquer），即 "分而治之"，是将原問題劃分成 n 個規模較小而結構與原問題相似的子問題，遞歸地解決這些問題，然後再合并其結果，以得到原問題的解。

當我們遇到一個大問題時，總是習慣把問題的規模變小，這樣便于分析讨論。這些規模變小後的問題和原來的問題是同質的，除了規模變小，其它的都是一樣的，本質上它還是同一個問題，規模變小後的問題其實是原問題的子問題。

分治模式在每一層上都有三個步驟：

分解（Divide）：将原問題分解成一系列與原問題同質的子問題；

解決（Conquer）：遞歸地解決各個子問題。若子問題足夠小，則直接求解；

合并（Combine）：将子問題的結果合并成原問題的解。

分治法所能解決的問題一般具有以下幾個特征：

可以将問題分解為若幹個規模較小的相同問題；

問題的規模縮小到一定程度後就可以很容易地解決；

問題分解出的子問題的解可以合并為該問題的解；

問題所分解出的各個子問題是互相獨立的，即子問題之間不再包含公共的孫問題。

分治法的典型應用：

<a href="http://www.cnblogs.com/gaochundong/p/comparison_sorting_algorithms.html#merge_sort" target="_blank">合并排序（Merge Sort）</a>

<a href="http://www.cnblogs.com/gaochundong/p/comparison_sorting_algorithms.html#quick_sort" target="_blank">快速排序（Quick Sort）</a>

<a href="http://www.cnblogs.com/gaochundong/p/binary_search.html" target="_blank">二分查找（Binary Search）</a>

動态規劃的過程可以描述為多階段最優化解決問題的過程，每一次的決策依賴于目前的狀态，随即又引起狀态的轉移，以此類推在變化的狀态中産生出決策序列。

動态規劃方法中的關鍵詞包括：階段（Stage）、狀态（State）、決策（Decision）、遞推關系（Recurrent Relation）。

動态規劃首先将待求解的問題分解為若幹個子問題（階段），按順序求解子問題。前一子問題的解為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。以此類推解決各子問題，最後一個子問題的解就是初始問題的解。

動态規劃所能解決的問題一般具有以下幾個特征：

最優化原理（Mathematical Optimization）：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構（Optimal Substructure），即滿足最優化原理。

無後效性：即某階段狀态一旦确定，就不受這個狀态以後決策的影響。也就是說，某狀态以後的過程不會影響以前的狀态，隻與目前狀态有關。

有重疊子問題（Overlapping Subproblems）：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。

特征 3 并不是動态規劃适用的必要條件，但是如果沒有這條性質，動态規劃算法同其他算法相比就不具備優勢。

動态規劃的基本步驟：

劃分階段：按照問題的時間或空間特征，把問題分為若幹個階段。注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。

确定狀态和狀态變量：将問題發展到各個階段時所處于的各種客觀情況用不同的狀态表示出來。狀态的選擇要滿足無後效性。

确定決策并寫出狀态轉移方程：因為決策和狀态轉移有着天然的聯系，狀态轉移就是根據上一階段的狀态和決策來導出本階段的狀态。是以如果确定了決策，狀态轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀态之間的關系來确定決策方法和狀态轉移方程。

尋找邊界條件：給出的狀态轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

所謂貪心算法是指，在對問題求解時，總是做出在目前看來最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解。

貪心算法沒有固定的算法架構，算法設計的關鍵是貪心政策的選擇。貪心政策适用的前提是：局部最優政策能導緻産生全局最優解。是以實際上，貪心算法适用的情況很少。

貪心算法不是對所有問題都能得到整體最優解，選擇的貪心政策必須具備無後效性，即某個狀态以後的過程不會影響以前的狀态，隻與目前狀态有關。是以對所采用的貪心政策一定要仔細分析其是否滿足無後效性。

貪心算法的基本思路：

建立數學模型來描述問題。

把求解的問題分成若幹個子問題。

對每一子問題求解，得到子問題的局部最優解。

把子問題的解局部最優解合成原來問題的一個解。

回溯法描述了一種選優搜尋過程，按選優條件向前搜尋，以達到目标。但當探索到某一步時，發現原先的選擇并不優或達不到目标，就退回一步重新選擇，這種走不通就退回再走的方法稱為回溯法，而滿足回溯條件的某個狀态的點稱為 "回溯點"。

回溯法可以了解為隐式的深度優先搜尋算法。其在包含問題的所有解的解空間樹中，按照深度優先搜尋的政策，從根節點出發深度探索解空間樹。當探索到某一節點時，要先判斷該節點是否包含問題的解，如果包含，就從該節點出發繼續探索下去，如果該節點不包含問題的解，則逐層向其祖先節點回溯。

許多複雜的，規模較大的問題都可以使用回溯法，有 "通用解題方法" 的美稱。

回溯法的一般步驟：

針對給定問題，确定問題的解空間，問題的解空間應至少包含問題的一個（最優）解；

确定節點的擴充搜尋規則；

以深度優先方式搜尋解空間，并在搜尋過程中用剪枝函數避免無效搜尋；

所謂 "分支" 就是采用廣度優先搜尋算法，依次搜尋節點的所有分支，抛棄不滿足限制條件的節點，然後從餘下的節點中選擇一個節點作為下一個搜尋節點繼續搜尋。

分支限界法的搜尋政策是：在擴充節點處，先生成其所有的兒子節點（分支），然後再從目前的活節點表中選擇下一個擴充節點。為了有效地選擇下一擴充節點，以加速搜尋的程序，在每一活節點處，計算一個函數值（限界），并根據這些已計算出的函數值，從目前活節點表中選擇一個最有利的節點作為擴充節點，使搜尋朝着解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。

<a href="http://hawstein.com/posts/dp-novice-to-advanced.html" target="_blank">動态規劃：從新手到專家</a>

<a href="http://hawstein.com/posts/dp-knapsack.html" target="_blank">動态規劃之背包問題</a>

<a href="http://www.felix021.com/blog/read.php?1587" target="_blank">最長遞增子序列 O(NlogN)算法</a>

<a href="http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html" target="_blank">五大常用算法之一：分治算法</a>

<a href="http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html" target="_blank">五大常用算法之二：動态規劃算法</a>

<a href="http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html" target="_blank">五大常用算法之三：貪心算法</a>

<a href="http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html" target="_blank">五大常用算法之四：回溯法</a>

<a href="http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741378.html" target="_blank">五大常用算法之五：分支限界法</a>

<a href="http://www.cnblogs.com/sdjl/articles/1274312.html" target="_blank">通過金礦模型介紹動态規劃</a>

<a href="http://www.cnblogs.com/Gavin_Liu/archive/2011/05/04/2012284.html" target="_blank">漫談算法（三）NP問題</a>

<a href="http://www.cnblogs.com/Creator/archive/2011/05/17/2048302.html" target="_blank">基礎算法系列總結：動态規劃</a>

<a href="http://www.cnblogs.com/Creator/archive/2011/06/07/2074227.html" target="_blank">基礎算法系列總結：貪心算法</a>

<a href="http://www.cnblogs.com/Creator/archive/2011/05/20/2052341.html" target="_blank">基礎算法系列總結：回溯算法</a>

<a href="http://www.cnblogs.com/Creator/archive/2011/05/21/2053033.html" target="_blank">基礎算法系列總結：分支限界算法</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-1/" target="_blank">Dynamic Programming | Set 1 (Overlapping Subproblems Property)</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-2-optimal-substructure-property/" target="_blank">Dynamic Programming | Set 2 (Optimal Substructure Property)</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/" target="_blank">Dynamic Programming | Set 3 (Longest Increasing Subsequence)</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/" target="_blank">Dynamic Programming | Set 4 (Longest Common Subsequence)</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/" target="_blank">Dynamic Programming | Set 5 (Edit Distance)</a>

<a href="http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/" target="_blank">Dynamic Programming | Set 6 (Min Cost Path)</a>

<a href="http://courses.csail.mit.edu/6.006/spring11/lectures/lec18.pdf" target="_blank">6.006- Introduction to Algorithms - Lecture 18</a>

本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/algorithmic_paradigms.html，如需轉載請自行聯系原作者