數據結構 課件 -第15章 算法設計基礎

數據結構計算機領域本科教育教學改革試點工作計劃（“101計劃”）研究成果101算法設計基礎第15章15.1分書問題與枚舉法15.2回溯與分支限界15.3分治法15.4動態(tài)規(guī)劃15.5貪心法15.6背包問題15.7應用場景15.1分書問題與枚舉法15.1分書問題與枚舉法

15.1分書問題與枚舉法15.1分書問題與枚舉法

15.1分書問題與枚舉法15.1分書問題與枚舉法

15.1分書問題與枚舉法15.1分書問題與枚舉法

15.1分書問題與枚舉法15.1分書問題與枚舉法優(yōu)化方向：減少枚舉總量。這里又分兩個子方向：一是盡早發(fā)現不滿足約束條件的狀態(tài)子集，避免對后續(xù)狀態(tài)進行無效賦值；二是避免重復驗證相同的狀態(tài)子集。降低驗證耗時。這里也分兩個子方向：一是采用更高效的算法進行驗證；二是將問題拆解為若干個小規(guī)模的子問題，以期能降低問題的復雜程度，得到更高的整體效率。15.2回溯與分支限界15.2回溯與分支限界“聰明的”枚舉：使不可能的情況被盡早篩除，從而減小搜索的空間。分書問題（3人分4本書）的決策樹將求解的過程理解為樹的某種遍歷，即所謂的“狀態(tài)搜索”。如果在搜索過程中加入約束條件的判斷，就有可能提前發(fā)現不可能成為解的狀態(tài)，從而及時止損，轉而搜索其它更有可能的狀態(tài)，達到節(jié)省時間的目的。15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界當某個結點向下一層的所有邊都不能滿足約束時，這個結點即被刪除，同時以這個結點為根結點的整個子樹也被刪除，不必進行無用的遍歷，所以回溯法通常比枚舉法的效率高。這個刪除子樹的過程被形象地稱為“剪枝”。

3人分4本書15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

注意到該問題的解不一定是全部任務的排列，而可能只包含一個任務的子集。15.2回溯與分支限界15.2回溯與分支限界

15.2回溯與分支限界15.2回溯與分支限界

15.3分治法15.3分治法分治法的實施包含“分”、“治”、“合”三個步驟：(1)“分”：將一個難以直接解決的大問題，分割成若干個規(guī)模較小而結構相同的子問題。(2)“治”：將劃分出的子問題分別解決。(3)“合”：將各個子問題的解合并處理，得到原問題的解。很多問題都可以用分治法解決，只是在不同問題中，上述三個步驟所占的比重可能不太一樣。歸并排序：“分”是很簡單的事，關鍵在于“治”和“合”快速排序：“分”和“治”是比較復雜的，“合”是水到渠成之事二分查找：“分”很簡單，核心在于“治”，根本不需要“合”。15.3分治法15.3分治法

——————————————————————偽代碼：分治法的偽代碼描述DivideAndConquer(n)——————————————————————ifn<kMinSize

then//若問題規(guī)模小于給定閾值|solution=Conquer(n)//直接處理end|Divide(n,

);//將規(guī)模為n

的原問題分割為

個子問題|fori

0to

-1do||sub_solution[i]

DivideAndConquer(第i個子問題的規(guī)模

)|end|solution

Merge(sub_solution);//將

個子問題的解合并得到最終解endreturnsolution——————————————————————15.3分治法15.3分治法

15.3分治法15.3分治法

15.3分治法15.3分治法

15.3分治法15.3分治法

15.3分治法15.3分治法

15.3分治法15.3分治法遞歸樹法：用遞歸樹將遞歸過程展開，看到遞歸每一層的工作量，然后對整體工作量進行評估。遞歸樹工作量

……………………………………………………………………

…………………………………………………………………………………………………………

……

用遞歸樹法大致估算工作量，用代入法嚴格證明結論。15.3分治法15.3分治法

15.3分治法15.3分治法

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

呈指數級增長15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

讓計算機長點記性是多么有用15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃動態(tài)規(guī)劃：如果大量的遞歸調用是重復性的從最小規(guī)模的問題開始求解，并且將小規(guī)模的最優(yōu)解存儲下來——這就是所謂“帶記憶”的求解。當問題的規(guī)模逐漸增大、需要根據小規(guī)模問題的解得到當前問題解的時候，我們不是遞歸地去求解小規(guī)模問題，而是直接查表，把之前存儲的小規(guī)模問題的最優(yōu)解拿過來用，這樣就極大地節(jié)省了時間。15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃

for

length

1ton-1

do//length=j-i,|for

i

1ton-length

do||j

i+length

||m[i][j]

Infinity//將m[i][j]初始化||for

k

itoj-1do|||this_m

m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1]|||ifthis_m<m[i][j]then//若當前值更優(yōu)||||m[i][j]

this_m//則更新最優(yōu)解||||p[i][j]

k//且記錄劃分位置|||end||end|endend———————————————————15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃動態(tài)規(guī)劃的設計思想一般可用動態(tài)規(guī)劃求解的優(yōu)化問題，具有以下兩個特征：具有最優(yōu)子結構。動態(tài)規(guī)劃中單個子問題的最優(yōu)解并不一定是整體最優(yōu)解的一部分，每一步的最優(yōu)決策是在綜合了所有子問題的最優(yōu)解之后做出的。整體最優(yōu)解對子問題最優(yōu)解的依賴性使得我們可以從最小問題出發(fā)構造出整個問題的解。子問題大量重復。即用分治法遞歸自頂向下求解時，分解出來的子問題并不總是新問題。動態(tài)規(guī)劃算法正是利用問題的這一性質，反其道而行，自底向上求解，將每次解決的新問題存在表中，避免重復計算，從而提高解題效率。需要注意的是，特征（1）是應用動態(tài)規(guī)劃的正確性的必要前提，特征（2）是動態(tài)規(guī)劃提升效率的前提。如果問題本身不具備最優(yōu)子結構，例如前面一步的最優(yōu)選擇會導致錯失后面的最優(yōu)解，則這個問題根本不能用動態(tài)規(guī)劃解決。另一方面，如果遞歸調用的子問題都沒有重復，那直接遞歸解決就好了，用動態(tài)規(guī)劃反而多用了存儲空間。15.4動態(tài)規(guī)劃15.4動態(tài)規(guī)劃動態(tài)規(guī)劃的設計思想應用動態(tài)規(guī)劃解決問題時，一般有4個步驟：確認問題具有最優(yōu)子結構；推導出子問題最優(yōu)解之間的遞推關系式；按照正確的順序，從小規(guī)模開始計算并存儲子問題的最優(yōu)解，同時記錄最優(yōu)劃分——注意每一步計算時都要保證用到的子問題是已經解決過的；根據最優(yōu)劃分構造出最優(yōu)的解決方案。15.5貪心法15.5貪心法貪心法的設計思想將解決問題的過程分步驟進行，每一步都采取當前最優(yōu)策略（也稱為“局部最優(yōu)策略”），并且不允許反悔。于是貪心法的關鍵點有兩個：劃分步驟?？梢赃f歸地理解為，將原問題劃分為執(zhí)行當前的一步指令，再遞歸地解決剩下的、結構相同的子問題?！柏潯薄炊x當前的“最優(yōu)”策略。當然，首先這個策略必須能形成一個可行解，即滿足問題的約束，因為執(zhí)行了當前策略后，在解決剩余子問題時不允許反悔；其次，這個策略必須是當前約束條件下能達到的最佳狀態(tài)。局部最優(yōu)=全局最優(yōu)

貪心可以得到最優(yōu)解15.5貪心法15.5貪心法

15.5貪心法15.5貪心法

15.5貪心法15.5貪心法方法1：在保證無沖突的前提下，每次批準一項最早開始的活動，即“先到先得”。方法2：在保證無沖突的前提下，每次批準一項時長最短的活動。15.5貪心法15.5貪心法方法3：在保證無沖突的前提下，每次批準一項沖突最少的活動。方法4：在保證無沖突的前提下，每次批準一項最早結束的活動。15.5貪心法15.5貪心法

15.5貪心法15.5貪心法貪心法的正確性分析一般分為2個步驟：證明可貪性：至少存在一組最優(yōu)解是可以由貪心法得到的。即對任一組最優(yōu)解，如果用貪心法決策的結果替換最優(yōu)解的一部分，仍然可以得到一組最優(yōu)解。這是貪心法與動態(tài)規(guī)劃最關鍵的區(qū)別——動態(tài)規(guī)劃在做決策時要枚舉子問題的最優(yōu)解，于是需要記錄子問題的最優(yōu)解以避免重復計算。而貪心法并不關心子問題的解是什么，只管根據眼前的局部問題特征取一個最優(yōu)的選擇?？韶澬员砻鬟@個問題的最優(yōu)解雖然不一定用貪心法得到，但貪心法也是可以得到一組最優(yōu)解的。證明單一最優(yōu)子結構性質。即在進行了一步貪心選擇后，就只剩下一個子問題；并且能證明當前貪心的結果加上這個子問題的最優(yōu)解，可以構成全局最優(yōu)解。單一最優(yōu)子結構性質表明貪心法選取的局部最優(yōu)就是全局最優(yōu)。15.6背包問題15.6背包問題

15.6背包問題15.6背包問題連續(xù)背包問題——貪心法劃分步驟：每一步選擇一件物品放入背包，直到背包的剩余承重量為0。貪：方法1：選擇當前剩余物品中價值最大的。反例？方法2：選擇當前剩余物品中重量最輕的。反例？方法3：選擇當前剩余物品中單位重量下價值最大的，即vi/wi的值最大的那件物品。

證明：最優(yōu)解的第1個分量用貪心選擇替換后仍然是最優(yōu)解，并且，在選擇了第1件物品后，剩下解是剩余子問題的最優(yōu)解。這就證明了按照單價貪心獲得的局部最優(yōu)解的確是全局最優(yōu)解。15.6背包問題15.6背包問題

NP-Hard問題15.6背包問題15.6背包問題

關鍵技術：代碼指紋獲取相似度計算一段代碼通過加字符、減字符、改字符這三種操作變換為另一段代碼所用的最少操作次數——動態(tài)規(guī)劃最大公共子串的貪心匹配(GreedyStringTiling)——貪心+動態(tài)規(guī)劃15.7應用場景：代碼查重15.7應用場景15.8小結15.8小結本章主要介紹了四大類算法設計技術：枚舉及其改進：枚舉是解決一類可枚舉問題的最直接的方法。在枚舉的過程中