數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)領(lǐng)域本科教育教學(xué)改革試點(diǎn)工作計(jì)劃（“101計(jì)劃”）研究成果101算法設(shè)計(jì)基礎(chǔ)第15章15.1分書(shū)問(wèn)題與枚舉法15.2回溯與分支限界15.3分治法15.4動(dòng)態(tài)規(guī)劃15.5貪心法15.6背包問(wèn)題15.7應(yīng)用場(chǎng)景15.1分書(shū)問(wèn)題與枚舉法15.1分書(shū)問(wèn)題與枚舉法

15.1分書(shū)問(wèn)題與枚舉法15.1分書(shū)問(wèn)題與枚舉法

15.1分書(shū)問(wèn)題與枚舉法15.1分書(shū)問(wèn)題與枚舉法

15.1分書(shū)問(wèn)題與枚舉法15.1分書(shū)問(wèn)題與枚舉法

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

15.2回溯與分支限界15.2回溯與分支限界當(dāng)某個(gè)結(jié)點(diǎn)向下一層的所有邊都不能滿(mǎn)足約束時(shí)，這個(gè)結(jié)點(diǎn)即被刪除，同時(shí)以這個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的整個(gè)子樹(shù)也被刪除，不必進(jìn)行無(wú)用的遍歷，所以回溯法通常比枚舉法的效率高。這個(gè)刪除子樹(shù)的過(guò)程被形象地稱(chēng)為“剪枝”。

3人分4本書(shū)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回溯與分支限界

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

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

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

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

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

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

的原問(wèn)題分割為

個(gè)子問(wèn)題|fori

0to

-1do||sub_solution[i]

DivideAndConquer(第i個(gè)子問(wèn)題的規(guī)模

)|end|solution

Merge(sub_solution);//將

個(gè)子問(wèn)題的解合并得到最終解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分治法遞歸樹(shù)法：用遞歸樹(shù)將遞歸過(guò)程展開(kāi)，看到遞歸每一層的工作量，然后對(duì)整體工作量進(jìn)行評(píng)估。遞歸樹(shù)工作量

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

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

……

用遞歸樹(shù)法大致估算工作量，用代入法嚴(yán)格證明結(jié)論。15.3分治法15.3分治法

15.3分治法15.3分治法

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

呈指數(shù)級(jí)增長(zhǎng)15.4動(dòng)態(tài)規(guī)劃15.4動(dòng)態(tài)規(guī)劃

讓計(jì)算機(jī)長(zhǎng)點(diǎn)記性是多么有用15.4動(dòng)態(tài)規(guī)劃15.4動(dòng)態(tài)規(guī)劃

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

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

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

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

15.4動(dòng)態(tài)規(guī)劃15.4動(dòng)態(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//若當(dāng)前值更優(yōu)||||m[i][j]

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

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

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

15.5貪心法15.5貪心法

15.5貪心法15.5貪心法方法1：在保證無(wú)沖突的前提下，每次批準(zhǔn)一項(xiàng)最早開(kāi)始的活動(dòng)，即“先到先得”。方法2：在保證無(wú)沖突的前提下，每次批準(zhǔn)一項(xiàng)時(shí)長(zhǎng)最短的活動(dòng)。15.5貪心法15.5貪心法方法3：在保證無(wú)沖突的前提下，每次批準(zhǔn)一項(xiàng)沖突最少的活動(dòng)。方法4：在保證無(wú)沖突的前提下，每次批準(zhǔn)一項(xiàng)最早結(jié)束的活動(dòng)。15.5貪心法15.5貪心法

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

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

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

NP-Hard問(wèn)題15.6背包問(wèn)題15.6背包問(wèn)題

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