?????? 算法是對完成特定問題的程序執行序列描述，表象為從問題初始狀態到問題結束狀態的所有路徑之中尋找可行路徑，若無先驗經驗，根據執行方式不同可以劃分為無規則和有規則（啟發式）方法。

?????? 無規則方法為窮舉，改進方法為遞推和迭代；有規則方法有分治、貪心、動態規劃、分支定界法等。

?????? 窮舉法：適用于解決極小規模或者復雜度線性增長，而線性規模不會很大的狀態。

?????? 遞推法：利用問題本身的遞推關系 先求解遞推關系再求解問題的一種方法。一般可解決問題都能得出通項公式或者遞推公式。

?????? 迭代法：輾轉法。不斷用變量的新值來代替舊值的過程。其重要的過程為 確定迭代變量 、確定迭代關系式、并對迭代過程進行控制。

?

一：直接遍歷態（窮舉法）

?????? 程序運行狀態是可以遍歷的，遍歷算法執行每一個狀態，最終會找到一個最優的可行解。

?

二：分治法

?????? 對于輸入規模很大的問題，直接求解問題非常困難，可把其N個輸入劃分成K個不通子集的集合，能夠得到K個不通的子問題，并分別求出各個子問題。在得出子問題的解后，還可以找到合適的方法合并問題的解。? 過程為 劃分——求解子問題（解法一般與原問題相同）——合并。

???? ? 其算法代表有：快速排序、歸并排序、線性時間選擇、漢諾塔問題；

?????????????? 多項式乘法、大整數乘法（快速傅里葉變換）、Strassen矩陣乘法、棋盤覆蓋、最接近點對問題、循環賽日程表。

??? ?? 斯特拉森乘法：對矩陣運算的改進算法。

????????????? 把大矩陣分割成小矩陣的方法，T(n)= d(n<=k) | 7t(n/2)+cn^2 (n>k)

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

?? ? ? ? 1) 該問題的規模縮小到一定的程度就可以容易地解決

?? ? ? ? 2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

?? ? ? ? 3) 利用該問題分解出的子問題的解可以合并為該問題的解；

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

（???? 第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；

???????? 第二條特征是應用分治法的前提它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；

???????? 第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或者動態規劃。

???????? 第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。）

??????? 思路：實際上就是類似于數學歸納法，找到解決本問題的求解方程公式，然后根據方程公式設計遞歸程序。

?

三：貪心法

???????? 貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

??????? 貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的過程不會影響以前的狀態，只與當前狀態有關。所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

??????? 算法思路：

?????????? 1.建立數學模型來描述問題

?????????? ⒉把求解的問題分成若干個子問題。

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

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

??????? 一般步驟：
??????????????? 1.? 選取一定打貪心策略，從問題的某個初始解開始；
??????????????? 2.? 不斷循環，根據局部最優策略，得到一個當前的最優解，縮小問題的范圍或者規模；
??????????????? 3.? 將所有的局部解綜合，得到整個問題的解。

??????? 目標函數：在程序設計中有一類問題，它有N種可能的輸入，而它的解由這種N個輸入的摸個子集構成。只是這類子集應該滿足某些給定的條件，我們稱之為“約束條件”。滿足約束條件的子集為 該問題的“可行解”。為了衡量可行解的好壞，實現確定一個標準，這些標準以函數形式給出，成為“目標函數”。那些使目標函數取極大值的可行解，稱為“最優解”。

??????? 對于這一類需求最優解的問題，根據 約束條件 和 目標函數 的數學模型的特性 或者求解方法的不同，可以將其細分為線性規劃、整數規劃、動態規劃等問題。對于其中的某些問題，貪心法更加直接。??

??????? 貪心策略適用的前提是：局部最優策略能導致產生全局最優解。???????

?? ? ?? 實際上，貪心算法適用的情況很少。一般，對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

??????? 貪心算法還是很常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。

??????? 可惜的是，它需要證明后才能真正運用到題目的算法中。

??????? 一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
?
?????? ? 其算法代表有：
????????????? 得到全局最優的貪心法：求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。
?????????????
????????????????????????????????? Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟發式。
???? ?? 貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。很多的智能算法（也叫啟發式算法），本質上就是貪心算法和隨機化算法結合——這樣的算法結果雖然也是局部最優解，但是比單純的貪心算法更靠近最優解。例如遺傳算法，模擬退火算法。


四：動態規劃法
??????? 一個問題由多個階段決策組成，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的方法。
??????? 問題的滿足條件：問題的狀態必須滿足最優化原理；問題的狀態必須滿足無后效性（無后效性：在下一時刻的狀態只與當前狀態有關，而與當前之前的狀態無關）（我去，這就是一個一階馬爾科夫鏈！！！）。

???????????????? 初始狀態 ——>|決策1| ——>|決策2| ——>|決策3|.............. ——>結束狀態
???????

??????? 基本思想與策略：

?? ???????????? 基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

?? ?????????? 由于動態規劃解決的問題多數有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維數組中。

?? ?????????? 與分治法最大的差別是：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。

?

??????? 適用的情況：能采用動態規劃求解的問題的一般要具有3個性質：

??????????? (1) 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

??????????? (2) 無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。

??????????? (3)有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）。

???????????

求解的基本步驟：

?? ?????????? 動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。

??????????????初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態

?? ? ? ? ? ? ? ? ? ? ?圖1 動態規劃決策過程示意圖

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

??? (2)確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無后效性。

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

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

一般，只要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程（包括邊界條件）。

?

?????? 實際應用中可以按以下幾個簡化的步驟進行設計：

?? ?（1）分析最優解的性質，并刻畫其結構特征。

?? ?（2）遞歸的定義最優解。

?? ?（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值

?? ?（4）根據計算最優值時得到的信息，構造問題的最優解

?

算法實現的說明

?? ? ? ? ? ? ? 動態規劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。

?? ??????????? 使用動態規劃求解問題，最重要的就是確定動態規劃三要素：

?? （1）問題的階段

??? （2）每個階段的狀態

?? ?（3）從前一個階段轉化到后一個階段之間的遞推關系。

?? ?? 遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。

?? ???? 確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。

?? ? ? ? ?f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

//動態規劃 for(j=1; j<=m; j=j+1) // 第一個階段xn[j] = 初始值;for(i=n-1; i>=1; i=i-1)// 其他n-1個階段for(j=1; j>=f(i); j=j+1)//f(i)與i有關的表達式xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};t = g(x1[j1:j2]); // 由子問題的最優解求解整個問題的最優解的方案print(x1[j1]);for(i=2; i<=n-1; i=i+1）{ t = t-xi-1[ji];for(j=1; j>=f(i); j=j+1)if(t=xi[ji])break; }

經典算法實例：管道鋪設的動態規劃、矩陣連乘問題

?

矩陣連乘的動態規劃代碼：

//使用最小運算代價的算法體現了動態規劃的優點：在選擇解時將k限制在i<=k<=j的范圍內， //并令差值j-i自小而大遞增，即先解最小的子問題把解保存起來，然后利用小問題的解來求解大問題的解。 void matrixChainOrder(int r[], int** M ,int n) {for (int i = 1; i < n; ++i){M[i][i] = 0;}int j = 0;for (int Level = 1; Level < n; ++Level){for (int i = 1; i < n - Level; ++i){j = i + Level;{m[i][j] = MAXINT;for (int k = i; k <= j - 1;++k){if (m[i][j] > m[i][k] + m[k + 1][j] + r[i] * r[k + 1] * r[j + 1])m[i][j] > m[i][k] + m[k + 1][j] + r[i] * r[k + 1] * r[j + 1];}}}}printf("M[1][n]"); }

?

五：回朔法/分支界定法

???????? 回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。?

?? 一般步驟：

（1）針對所給問題，定義問題的解空間；

（2）確定易于搜索的解空間結構；一般為解的空間樹。

（3）以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。

基本思想：

???????? 在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯（可聯合剪枝過程）。（其實回溯法就是對隱式圖的深度優先搜索算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。

?????? 經典算法：八皇后問題。

?????? 分支定界法：——>轉下一篇！！！

????????

六、EM方法

????????? EM方法：從最大似然到EM算法淺解。

求最大似然函數估計值的一般步驟：

（1）寫出似然函數；（2）對似然函數取對數，并整理；（3）求導數，令導數為0，得到似然方程；（4）解似然方程，得到的參數即為所求；

EM算法（Expectation-maximization）：

???? 期望最大算法是一種從不完全數據或有數據丟失的數據集（存在隱含變量）中求解概率模型參數的最大似然估計方法。

EM的算法流程：

初始化分布參數θ；

重復以下步驟直到收斂：

??????? E步驟：根據參數初始值或上一次迭代的模型參數來計算出隱性變量的后驗概率，其實就是隱性變量的期望。作為隱藏變量的現估計值：

??????? M步驟：將似然函數最大化以獲得新的參數值：

EM方法的另外一種理解：參數輪換法；

EM算法有很多的應用，最廣泛的就是GMM混合高斯模型、聚類、HMM等等。具體可以參考JerryLead的cnblog中的Machine Learning專欄：（EM算法）The EM Algorithm 混合高斯模型（Mixtures of Gaussians）和EM算法 K-means聚類算法。

?

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法设计之—直接 遍历/穷举法、贪心算法、动态规划、回溯法、EM方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。