1      分治演算法

1.1      基本概念

把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并

1.2      典型問題

1.2.1        二分搜索

二分查找可以解決（預排序陣列的查找）問題：只要陣列中包含T（即要查找的值），那么通過不斷縮小包含T的范圍，最終就可以找到它，一開始，范圍覆寫整個陣列，將陣列的中間項與T進行比較，可以排除一半元素，范圍縮小一半，就這樣反復比較，反復縮小范圍，最終就會在陣列中找到T，或者確定原以為T所在的范圍實際為空，對于包含N個元素的表，整個查找程序大約要經過log(2)N次比較，

1.2.2        大整數乘法

1.2.3        Strassen矩陣乘法

1.2.4        棋盤覆寫

1.2.5        歸并排序

歸并排序（Merge Sort）完全遵循上述分治法三個步驟：

1. 分解：將要排序的n個元素的序列分解成兩個具有n/2個元素的子序列
2. 解決：使用歸并排序分別遞回地排序兩個子序列
3. 合并：合并兩個已排序的子序列，產生原問題的解

歸并排序的演算法思想，看看下面的圖解示例就明白了，

1.2.6        快速排序

該方法的基本思想是：

  （1）先從數列中取出一個數作為基準數，

  （2）磁區程序，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊，

  （3）再對左右區間重復第二步，直到各區間只有一個數，

1.2.7        線性時間選擇

1.2.8        最接近點對問題

1.2.9        回圈賽日程表

1.2.10    漢諾塔

漢諾塔問題是源于印度一個古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，

綜合分析可知把n個盤子從1座（相當第一柱子）移到3座（相當第三柱子）：

  （1）把1座上（n-1）個盤子借助3座移到2座，

  （2）把1座上第n個盤子移動3座，

  （3）把2座上（n-1）個盤子借助1座移動3座，

2      動態規劃演算法

2.1      基本概念

動態規劃是通過組合子問題的解而解決整個問題的，通過將問題分解為相互不獨立（各個子問題包含有公共的子問題，也叫重疊子問題）的子問題，對每個子問題求解一次，將其結果保存到一張輔助表中，避免每次遇到各個子問題時重新計算，

2.2      典型問題

2.2.1        鋼條切割

2.2.2        最長非降子序列的長度

• 問題描述

一個序列有N個數：A[1],A[2],…,A[N]，求出最長非降子序列的長度，

• 解決方法

d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]

想要求d(i)，就把i前面的各個子序列中， 最后一個數不大于A[i]的序列長度加1，然后取出最大的長度即為d(i)， 當然了，有可能i前面的各個子序列中最后一個數都大于A[i]，那么d(i)=1， 即它自身成為一個長度為1的子序列，

2.2.3        最長公共子序列

• 動態規劃解決程序

1）描述一個最長公共子序列

　　如果序列比較短，可以采用蠻力法列舉出X的所有子序列，然后檢查是否是Y的子序列，并記錄所發現的最長子序列，如果序列比較長，這種方法需要指數級時間，不切實際，

　　LCS的最優子結構定理：設X={x₁，x₂，……，x_m}和Y={y₁，y₂，……，y_n}為兩個序列，并設Z={z₁、z₂、……，z_k}為X和Y的任意一個LCS，則：

      （1）如果x_m=y_n，那么z_k=x_m=y_n，而且Z_k-1是X_m-1和Y_n-1的一個LCS，

　　（2）如果x_m≠y_n，那么z_k≠x_m蘊含Z是是X_m-1和Y_n的一個LCS，

　　（3）如果x_m≠y_n，那么z_k≠y_n蘊含Z是是X_m和Y_n-1的一個LCS，

　　定理說明兩個序列的一個LCS也包含兩個序列的前綴的一個LCS，即LCS問題具有最優子結構性質，

2）一個遞回解

　　根據LCS的子結構可知，要找序列X和Y的LCS，根據x_m與y_n是否相等進行判斷的，如果x_m=y_n則產生一個子問題，否則產生兩個子問題，設C[i,j]為序列X_i和Y_j的一個LCS的長度，如果i=0或者j=0，即一個序列的長度為0，則LCS的長度為0，LCS問題的最優子結構的遞回式如下所示：

2.2.4        最優二叉搜索樹

2.2.5        最長回文字串

2.2.6        0-1背包問題

• 0-1背包問題描述

　　有一個竊賊在偷竊一家商店時發現有n件物品，第i件物品價值為v_i元，重量為w_i，假設v_i和w_i都為整數，他希望帶走的東西越值錢越好，但他的背包中之多只能裝下W磅的東西，W為一整數，他應該帶走哪幾樣東西？

0-1背包問題中：每件物品或被帶走，或被留下，（需要做出0-1選擇），小偷不能只帶走某個物品的一部分或帶走兩次以上同一個物品，

部分背包問題：小偷可以只帶走某個物品的一部分，不必做出0-1選擇，

• 0-1背包問題解決方法

　　0-1背包問題是個典型舉辦子結構的問題，但是只能采用動態規劃來解決，而不能采用貪心演算法，因為在0-1背包問題中，在選擇是否要把一個物品加到背包中，必須把該物品加進去的子問題的解與不取該物品的子問題的解進行比較，這種方式形成的問題導致了許多重疊子問題，滿足動態規劃的特征，動態規劃解決0-1背包問題步驟如下：

0-1背包問題子結構：選擇一個給定物品i，則需要比較選擇i的形成的子問題的最優解與不選擇i的子問題的最優解，分成兩個子問題，進行選擇比較，選擇最優的，

0-1背包問題遞回程序：設有n個物品，背包的重量為w，C[i][w]為最優解，即：

2.2.7        裝配線調度問題

• 動態規劃解決步驟

1）描述通過工廠最快線路的結構

　　對于裝配線調度問題，一個問題的（找出通過裝配站S_i,j的 最快線路）最優解包含了子問題（找出通過S_1,j-1或S_2,j-1的最快線路）的一個最優解，這就是最優子結構，觀察一條通過裝配站S1,j的最快線路，會發現它必定是經過裝配線1或2上裝配站j-1，因此通過裝配站的最快線路只能以下二者之一：

a)通過裝配線S_1,j-1的最快線路，然后直接通過裝配站S_i,j；

b)通過裝配站S_2,j-1的最快線路，從裝配線2移動到裝配線1，然后通過裝配線S_1,j，

為了解決這個問題，即尋找通過一條裝配線上的裝配站j的最快線路，需要解決其子問題，即尋找通過兩條裝配線上的裝配站j-1的最快線路，

2）一個遞回的解

　　最終目標是確定底盤通過工廠的所有路線的最快時間，設為f*，令f_i[j]表示一個底盤從起點到裝配站S_i,j的最快時間，則f* = min(f₁[n]+x₁,f₂[n]+x₂)，逐步向下推導，直到j=1，

當j=1時: f₁[1] = e₁+a_1,1,f₂[1] = e₂+a_2,1，

當j>1時：f₁[j] = min(f₁[j-1]+a_1,j，f₂[j-1]+t_2,j-1+a_1,j)，f₂[j] = min(f₂[j-1]+a_2,j，f₁[j-1]+t_1,j-1+a_2,j)，

3      回溯法

3.1      基本概念

回溯演算法實際上一個類似列舉的搜索嘗試程序，主要是在搜索嘗試程序中尋找問題的解，當發現已不滿足求解條件時，就“回溯”回傳，嘗試別的路徑，

回溯法解題步驟：

1) 定義問題解空間；

2) 確定易于搜索的解空間結構；

3) 深度優先搜索樹解空間，并且運用剪枝函式避免無效搜索，

3.2      典型問題

3.2.1        八皇后問題

八皇后問題是在8*8的棋盤上放置8枚皇后，使得棋盤中每個縱向、橫向、左上至右下斜向、右上至左下斜向均只有一枚皇后，八皇后的一個可行解如圖所示：

思路：

對于八皇后的求解可采用回溯演算法，從上至下依次在每一行放置皇后，進行搜索，若在某一行的任意一列放置皇后均不能滿足要求，則不再向下搜索，而進行回溯，回溯至有其他列可放置皇后的一行，再向下搜索，直到搜索至最后一行，找到可行解(所有)，輸出，

4      貪心演算法

4.1      基本概念

在對問題求解時，總是做出在當前看來是最好的選擇，也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的區域最優解，

4.2      典型問題

5      分支界限法

5.1      基本概念

類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的演算法，但在一般情況下，分支限界法與回溯法的求解目標不同，回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使

某一目標函式值達到極大或極小的解，即在某種意義下的最優解，

5.2      典型問題

標籤：其他

上一篇：leetcode - 鏈表兩兩元素交換 + 判斷鏈表有無環

下一篇：查找二叉樹