算法設計與分析

1、分治法

分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸的解這些子問題，然后將各子問題的解合并得到原問題的解。

分治法所能解決的問題一般具有以下幾個特征：
　 1) 該問題的規模縮小到一定的程度就可以容易地解決
　 2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
　 3) 利用該問題分解出的子問題的解可以合并為該問題的解；
　 4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

分治法的基本步驟：
分治法在每一層遞歸上都有三個步驟：
　　分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
　　解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
　　合并：將各個子問題的解合并為原問題的解。

平衡子問題：分治算法中，劃分出的子問題的規模應基本一致　　
2、動態規劃算法：

動態規劃：通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用于有重疊子問題和最優子結構性質的問題。

基本思想：若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。 通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。 這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

與分治法區別：動態規劃算法與分治法類似，都使用了將問題實例歸納為更小的、相似的子問題，并通過求解子問題產生一個全局最優值的思路，但動態規劃不是分治法：關鍵在于分解出來的各個子問題的性質不同。分治法要求各個子問題是獨立的(即不包含公共的子問題)，因此一旦遞歸地求出各個子問題的解后，便可自下而上地將子問題的解合并成原問題的解。如果各子問題是不獨立的，那么分治法就要做許多不必要的工作，重復地解公共的子問題。動態規劃與分治法的不同之處在于動態規劃允許這些子問題不獨立(即各子問題可包含公共的子問題)，它對每個子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。
問題特征：

(1)最優子結構：當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質。

(2)重疊子問題：在用遞歸算法自頂向下解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。動態規劃算法正是利用了這種子問題的重疊性質，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。

算法步驟：

(1)分析最優值的結構，刻畫其結構特征；

(2)遞歸地定義最優值；

(3)按自底向上或自頂向下記憶化的方式計算最優

(4)根據計算最優值得到的信息構造最優解
3、貪心算法
貪心選擇性質的定義
做出當前看來是最好的選擇，
根據貪心策略一步步選擇最終導致最優解，也就是選擇局部最優解，可得整體最優解
(1)原理：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。

(2)特性：貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。能夠用貪心算法求解的問題一般具有兩個重要特性：貪心選擇性質和最優子結構性質。

1)貪心選擇性質

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素。貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。證明的大致過程為：首先考察問題的一個整體最優解，并證明可修改這個最優解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規模更小的類似子問題。然后用數學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優解。其中，證明貪心選擇后的問題簡化為規模更小的類似子問題的關鍵在于利用該問題的最優子結構性質。

2)最優子結構性質

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。

(3)貪心算法與動態規劃算法的差異:

動態規劃和貪心算法都是一種遞推算法，均有最優子結構性質，通過局部最優解來推導全局最優解。兩者之間的區別在于：貪心算法中作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留，貪心算法每一步的最優解一定包含上一步的最優解。動態規劃算法中全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有最優解。

(4)基本思路：

1)建立數學模型來描述問題。
2)把求解的問題分成若干個子問題。
3)對每一子問題求解，得到子問題的局部最優解。
4)把子問題的解局部最優解合成原來解問題的一個解。

貪心算法在該問題的貪心策略不滿足貪心選擇性質條件時，構造出來的解是近似解

4、回溯法

(1)描述:回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法。

(2)原理: 回溯法在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。

回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數相當大的問題。有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。
(3)問題的解空間
問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。


(5)回溯法的基本思想

基本思想：

用回溯法解題的一個顯著特征是在搜索過程中動態產生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間。

解題步驟：

1)針對所給問題，定義問題的解空間；
2)確定易于搜索的解空間結構；
3)以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。

常用剪枝函數：用約束函數在擴展結點處剪去不滿足約束的子樹；用限界函數剪去得不到最優解的子樹

約束函數用于選取滿足條件的一個解，而限界函數用于剪除不可能存在的解
5、分支限界法

(1)描述：采用廣度優先產生狀態空間樹的結點，并使用剪枝函數的方法稱為分枝限界法。

所謂“分支”是采用廣度優先的策略，依次生成擴展結點的所有分支（即：兒子結點）。
所謂“限界”是在結點擴展過程中，計算結點的上界（或下界），邊搜索邊減掉搜索樹的某些分支，從而提高搜索效率。

(2)原理：按照廣度優先的原則，一個活結點一旦成為擴展結點（E-結點）R后，算法將依次生成它的全部孩子結點，將那些導致不可行解或導致非最優解的兒子舍棄，其余兒子加入活結點表中。然后，從活結點表中取出一個結點作為當前擴展結點。重復上述結點擴展過程，直至找到問題的解或判定無解為止。

(3)分支限界法與回溯法

1)求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。
2)搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。

(4)常見的分支限界法

1)FIFO分支限界法(隊列式分支限界法)

基本思想：按照隊列先進先出(FIFO)原則選取下一個活結點為擴展結點。

搜索策略：一開始，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點后，作為當前擴展結點。對當前擴展結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數的兒子加入活結點隊列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。

2)LC(least cost)分支限界法==(優先隊列式分支限界法)==

基本思想：為了加速搜索的進程，應采用有效地方式選擇活結點進行擴展。按照優先隊列中規定的優先級選取優先級最高的結點成為當前擴展結點。

搜索策略：對每一活結點計算一個優先級（某些信息的函數值），并根據這些優先級；從當前活結點表中優先選擇一個優先級最高（最有利）的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。再從活結點表中下一個優先級別最高的結點為當前擴展結點，……，直到找到一個解或活結點隊列為空為止。

補充：
1.在對問題的解空間進行搜索時，
分支限界法中的一個活結點最多有一次機會成為活結點
回溯法中的一個結點會有多次機會成為活結點

數值化隨機算法
利用了概率的性質計算近似值得到的隨機算法

舍伍德算法
得到的解不一定正確，但總會得到一個解

拉斯維加斯算法
有時能得到解，有時得不到解，但得到的解一定正確
運行時以一定的概率得到正確的解

線性時間選擇問題和快速排序利用了舍伍德算法

N后問題使用了拉斯維加斯算法

P問題是指能夠在多項式時間內解決的問題，這意味著計算機能夠在有限時間內完成計算。
NP問題是指我們能夠在多項式時間內驗證一個解的問題。

對于一個問題，如果我們能夠在多項式時間內解決，那么我們肯定也能在多項式時間內驗證某個猜測是否為這個問題的一個解，因此P問題也屬于NP問題，或者說P問題是NP問題的一個子集。

NP完全問題也簡稱為NPC問題，NPC問題是NP問題中最難的一類問題，
NPC問題是NP難問題的一個子集。

用于計算時間復雜度的方法：

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

總結

以上是生活随笔為你收集整理的算法设计与分析——算法思想总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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