1、主要內(nèi)容、分割戰(zhàn)略、動(dòng)態(tài)計(jì)劃、貪心算法、回溯方法、0-1背包問題的算法設(shè)計(jì)戰(zhàn)略比較與分析、分支限制法、分割法的基本思想是將N規(guī)模的問題分解為K個(gè)小子問題。這些子問題徐璐獨(dú)立，與原始問題相同。遞歸解決這些子問題，然后合并每個(gè)子問題的解決，以獲得原始問題的解決。1 .分治法、分治法可以解決的問題一般具有以下特點(diǎn)。如果在一定程度上縮小牙齒問題的規(guī)模，就很容易解決。牙齒問題可以分為幾個(gè)小的相同問題。換句話說，牙齒問題具有最優(yōu)子結(jié)構(gòu)特性。利用牙齒問題，可以將分解子問題的解法結(jié)合成牙齒問題的解法。分解為牙齒問題的各個(gè)子問題徐璐獨(dú)立。也就是說，子問題之間不包括公共子問題。問題的計(jì)算復(fù)雜性通常隨著問題規(guī)模的增

2、加而增加，所以大部分問題滿足了牙齒特征。牙齒特征是適用分治法的前提，大部分問題也可以滿足。牙齒特征反映了遞歸思想的應(yīng)用，能否利用分治法完全取決于問題是否具有牙齒特征。如果具有前兩個(gè)茄子特征，不具有第三個(gè)特征，可以考慮貪心算法或動(dòng)態(tài)計(jì)劃。牙齒特征包括分治法的效率。如果各子問題不是獨(dú)立的，分治法就要做很多不必要的事情，反復(fù)解決公共子問題。此時(shí)也可以使用分治法，但一般來說，最好使用動(dòng)態(tài)計(jì)劃。divide-and-conquer(p)if(| p |=n0)ad hoc(p)；/小型問題解決divide p into smaller sub instances P1，p2，PK；/分解問題for (I

3、=1，I=k，I)yi=divide-and-conquer(pi)；/每個(gè)子問題return merge(y1，yk)遞歸解決。/將每個(gè)子問題的解決合并為原始問題的解決，分割法的基本階段，分割法的時(shí)間效率滿足：T(n)=kT(n/m) f(n)，展開遞歸后分割法的時(shí)間效率大致是動(dòng)態(tài)計(jì)劃的基本思想。動(dòng)態(tài)計(jì)劃算法的基本要素：最佳子結(jié)構(gòu)重疊子問題，2 .動(dòng)態(tài)計(jì)劃，動(dòng)態(tài)計(jì)劃算法適合解決最優(yōu)化問題。將問題分成多個(gè)子問題，并將所有已解決子問題的答案記錄在一個(gè)表中。無論牙齒問題以后使用還是渡邊杏使用，一旦計(jì)算出來，就放入表中。動(dòng)態(tài)規(guī)劃基本階段，尋找最佳解決方案的特性，并雕刻結(jié)構(gòu)特征。遞歸定義最佳值。從底部

4、向上計(jì)算最佳值。根據(jù)計(jì)算最佳值時(shí)獲得的信息構(gòu)建最佳解決方案。貪心算法的基本思想通過目前看來最好的選擇(貪心的選擇)，縮小原來問題的規(guī)模，反復(fù)進(jìn)行，直到最終解決方法出來。(威廉莎士比亞、貪心、貪心、貪心、貪心、貪心、貪心、貪心)牙齒技術(shù)的特點(diǎn)是，不能保證求的最后解法是最好的。不能用于查找最大或最小解決方案問題。只能查找滿足特定約束的可執(zhí)行解決方案的范圍。3 .貪心算法，貪婪算法的基本要素：1，貪婪選擇的性質(zhì)，貪婪選擇的性質(zhì)意味著問題的整體最佳解決方案可以通過一系列部分最優(yōu)選擇來實(shí)現(xiàn)，即貪婪選擇。這是貪心算法能夠運(yùn)行的第一個(gè)基本要素，也是貪心算法和動(dòng)態(tài)編程算法之間的主要區(qū)別。牙齒性質(zhì)是使用貪婪法成

5、功的保證。否則就是近憂。動(dòng)態(tài)編程是子問題的解法，得到了當(dāng)前問題的解法，因此動(dòng)態(tài)編程算法通常自下而上解決每個(gè)子問題。貪心算法從當(dāng)前問題的部分最優(yōu)解決方案中導(dǎo)出子問題，因此貪心算法通常從上到下進(jìn)行，以迭代的方式進(jìn)行連續(xù)的貪心選擇，每次做出貪心選擇時(shí)，將想要的問題簡(jiǎn)化為較小的子問題。(David aser，Northern Exposure(美國(guó)電視電視劇，貪心)，2，最優(yōu)子結(jié)構(gòu)特性，問題的最優(yōu)解包含子問題的最優(yōu)解時(shí)，牙齒問題說具有最優(yōu)子結(jié)構(gòu)特性。問題的最優(yōu)子結(jié)構(gòu)特性是動(dòng)態(tài)編程算法或貪心算法可以解決的問題的核心特征?；厮莘椒ㄊ窍到y(tǒng)的、跳躍的搜索算法。在包含所有問題分析的解決方案空間樹中，根據(jù)深度優(yōu)先

6、級(jí)策略在根節(jié)點(diǎn)中搜索解決方案空間樹。4 .回溯方法，(1)定義給定問題的問題的解決空間(解釋編碼)(2)確定易于搜索的解決方案空間結(jié)構(gòu)(由樹或圖組成)。(3)以深度優(yōu)先級(jí)搜索解析空間，在搜索過程中使用茄子函數(shù)防止錯(cuò)誤搜索。回溯方法的基本步驟：(1)提高回溯方法效率的兩種茄子方法使用約束函數(shù)截?cái)嗖环霞s束條件的子樹。使用邊界函數(shù)截?cái)酂o法獲得最佳解決方案的子樹。(2)兩個(gè)茄子典型解析空間樹子集樹：0-1背包，葉節(jié)點(diǎn)數(shù)2n，摘要點(diǎn)數(shù)2n 1，遍歷時(shí)間(2N)；陣列樹：TSP問題，葉節(jié)點(diǎn)數(shù)n！巡回時(shí)間(n！)。如果給定問題在N個(gè)元素的集合S中找到滿足特定特性的子集，則相應(yīng)的解決方案空間樹稱為子集樹。例

7、如，0-1背包問題。這些子集樹通常包含2n個(gè)葉節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)為2n1-1。通過子集樹需要O(2n)計(jì)算時(shí)間。子集樹，void back track(int)if(TN)output(x)；else for(int I=0)；I=1；I)XT=I；If(約束(t)，如果給定問題確定n個(gè)元素滿足特定特性的排序，則相應(yīng)的解決方案空間樹稱為排序樹。比如旅行推銷員問題。這種陣列樹通常有N牙齒！葉節(jié)點(diǎn)。要通過陣列樹，請(qǐng)O(n！)計(jì)算時(shí)間。樹陣列，void back track(int)if(TN)output(x)；else for(int I=t；I=n；I) swap(xt，Xi) : If(約束(t

8、)，回溯方法：回溯方法稱為通用問題解決方法。這也顯示了回溯法運(yùn)用的廣泛性?；厮莘椒ㄅc動(dòng)態(tài)規(guī)劃和貪心算法相比具有獨(dú)特的優(yōu)點(diǎn)?；厮莘椒ㄊ菍ふ乙粋€(gè)問題的所有解法或任何解法。這在解決問題時(shí)更全面，這也是其他幾個(gè)茄子算法所沒有的優(yōu)點(diǎn)。分支限制法的搜索策略是在擴(kuò)展節(jié)點(diǎn)上，教師創(chuàng)建所有子節(jié)點(diǎn)(分支)，然后從當(dāng)前活動(dòng)節(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)。為了有效地選擇下一個(gè)展開節(jié)點(diǎn)，加快搜索過程，計(jì)算每個(gè)活動(dòng)節(jié)點(diǎn)上的函數(shù)值(邊界)，并根據(jù)函數(shù)值選擇當(dāng)前活動(dòng)節(jié)點(diǎn)表中最有利的節(jié)點(diǎn)之一作為展開節(jié)點(diǎn)。搜索轉(zhuǎn)到解決空間中具有最佳解決方案的分支，以便盡快找到最佳解決方案。牙齒方法稱為分支限制法。5 .分支限制法、分支限制法是解決方

9、案空間樹，它經(jīng)常以寬度優(yōu)先或最小消耗(最大效果)優(yōu)先級(jí)搜索問題。在分支限制法中，每個(gè)活動(dòng)節(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)。實(shí)時(shí)節(jié)點(diǎn)成為擴(kuò)展節(jié)點(diǎn)時(shí)，將同時(shí)創(chuàng)建所有子節(jié)點(diǎn)。在這些兒子節(jié)點(diǎn)中，導(dǎo)致無法執(zhí)行的分析或非最佳解決方案的兒子節(jié)點(diǎn)將被丟棄，其馀兒子節(jié)點(diǎn)將添加到活動(dòng)節(jié)點(diǎn)表中。然后將“活動(dòng)節(jié)點(diǎn)”(active nodes)表格中的下一個(gè)節(jié)點(diǎn)作為當(dāng)前展開節(jié)點(diǎn)移除，并重復(fù)上述節(jié)點(diǎn)展開過程。牙齒過程將繼續(xù)，直到找到所需的解決方法或活節(jié)點(diǎn)表為空。解決方案階段，解決方案空間定義(解碼)；確定解決方案空間的樹結(jié)構(gòu)?；贐FS等搜索： a。每個(gè)活動(dòng)節(jié)點(diǎn)只有一個(gè)機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)。b .從擴(kuò)展節(jié)點(diǎn)創(chuàng)建可以一次到達(dá)的新節(jié)

10、點(diǎn)。c .在新節(jié)點(diǎn)上，刪除無法導(dǎo)出最佳解決方案的節(jié)點(diǎn)。/茄子修剪策略d .將其馀新節(jié)點(diǎn)添加到活動(dòng)表(隊(duì)列)中。e .在活動(dòng)表中選擇和展開節(jié)點(diǎn)。/選擇策略f .直到活動(dòng)表為空；兩個(gè)茄子典型的活動(dòng)節(jié)點(diǎn)擴(kuò)展方法，先進(jìn)先出隊(duì)列(F I F O) :將活動(dòng)節(jié)點(diǎn)表組織到一個(gè)隊(duì)列中，并根據(jù)隊(duì)列中的先進(jìn)先出原則選擇下一個(gè)節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。優(yōu)先級(jí)隊(duì)列(用于消耗的小根堆、用于增加的大根堆):每個(gè)節(jié)點(diǎn)都有相應(yīng)的消耗或收益。0-1背包問題的說明：給定的N茄子項(xiàng)目和背包。物品I的重量是wi，其價(jià)值是VI，背包的容量是C。問如何挑選背包里的東西，能最大限度地提高背包里的東西的總價(jià)值嗎？選擇裝入背包的項(xiàng)目時(shí)，每個(gè)項(xiàng)目I只有

11、兩種茄子選擇：裝入背包或記帳背包。不能將項(xiàng)目I多次放在背包里，也不能只放一部分。6 .0-1背包問題的算法設(shè)計(jì)戰(zhàn)略比較與分析，正式說明：最佳解決方案序列為x1、x2、.假設(shè)為xn，則可以最大限度地實(shí)現(xiàn)背包容量C的總價(jià)值。如果x1=1，則x2，xn表示如果，x1=0，X2，XN是C容量的背包的總值，仍然是最大的序列。這就是我們所說的最佳子結(jié)構(gòu)的性質(zhì)。(1)動(dòng)態(tài)規(guī)劃算法具有0-1背包問題的最優(yōu)子結(jié)構(gòu)特性。這可以為動(dòng)態(tài)編程問題提供遞歸關(guān)系。設(shè)置背包問題的子問題的最佳解決方案是m(i，j)。也就是說，m(i，J)是背包剩馀容量J，可選項(xiàng)目是I，I 1，N時(shí)0-1背包問題的最佳值。計(jì)算m(i，j)作為0

12、-1背包問題的最佳子結(jié)構(gòu)性質(zhì)的遞歸式如下：(1)動(dòng)態(tài)編程算法求解、臨界條件、算法復(fù)雜性分析：如m(i，J)的遞歸所示，算法需要O (NA)。背包容量C大時(shí)，算法需要更多的計(jì)算時(shí)間。例如，在c2n中，算法需要(n2n)計(jì)算時(shí)間。當(dāng)一個(gè)問題具有最佳子結(jié)構(gòu)特性時(shí)，可以使用動(dòng)態(tài)計(jì)劃解決。但有時(shí)有更簡(jiǎn)單有效的算法。貪心算法不是在整體最優(yōu)中考慮的，在某種意義上只是部分最優(yōu)選擇。(約翰f肯尼迪，努力)貪心算法無法得到整個(gè)最優(yōu)解，但最終結(jié)果是最優(yōu)解的好近似值。(2)求解貪心算法，我們首先計(jì)算當(dāng)前區(qū)域的最優(yōu)解m(i，j)，然后通過循環(huán)繼續(xù)查找最大值(M (I 1，Z)。這也可能表明貪心算法比動(dòng)態(tài)計(jì)劃算法解決0-

13、1背包問題的便利性。用貪心算法解決問題的前提是問題具有最優(yōu)的子結(jié)構(gòu)性質(zhì)。所有選擇都是當(dāng)前狀態(tài)下最好的部分選擇。解決背包問題也顯示出貪心算法解決特定問題時(shí)的效率。貪心算法不一定求最優(yōu)解，但也是解決問題的重要方法。(1)分析空間定義：x=(0，0，0)，(0，0，1)，(0，1，0)，(1，1，0)，(1，1，0)解決方案空間可以顯示為子集樹。搜索解決方案空間樹時(shí)，只要左側(cè)兒子節(jié)點(diǎn)是可執(zhí)行節(jié)點(diǎn)，搜索就會(huì)進(jìn)入左側(cè)子樹。僅當(dāng)右側(cè)子樹可以包含最佳解決方案時(shí)，才開始搜索右側(cè)子樹。否則，請(qǐng)剪切右側(cè)的子樹?？尚行约s束函數(shù)：wixiC上限函數(shù)：Bound()，使用回溯方法解決問題，但是背包問題比較麻煩?；厮莘椒?/p>

14、在解決多個(gè)茄子最優(yōu)解問題時(shí)有很大的優(yōu)點(diǎn)。因?yàn)橛?jì)算父函數(shù)需要O(n)時(shí)間，最壞情況下需要O(2n)個(gè)右兒童節(jié)點(diǎn)需要父函數(shù)，所以計(jì)算0/1背包問題的回溯算法所需的計(jì)算時(shí)間復(fù)雜性為O(n2n)。(3)分支邊界求解，0/1背包問題的分支邊界算法可以使用最大收益算法邊界函數(shù)計(jì)算活動(dòng)節(jié)點(diǎn)的最大收益上限upprofit?；顒?dòng)節(jié)點(diǎn)為根的子樹中所有節(jié)點(diǎn)的收入值不能超過upprofit?；顒?dòng)節(jié)點(diǎn)的最大堆使用upprofit作為關(guān)鍵值字段。在子集樹中執(zhí)行最大利潤(rùn)分支搜索的函數(shù)首先初始化活動(dòng)節(jié)點(diǎn)的最大堆，然后使用數(shù)組bestx記錄最佳解決方案。函數(shù)的循環(huán)首先驗(yàn)證E節(jié)點(diǎn)左邊孩子的可行性。如果可能，請(qǐng)將其添加到子集樹和活

15、動(dòng)節(jié)點(diǎn)隊(duì)列(即最大堆)中。僅當(dāng)節(jié)點(diǎn)右側(cè)孩子的邊界值指示可以找到最佳解決方案時(shí)，才將右側(cè)孩子添加到子集樹和隊(duì)列中。回溯方法比分支限制具有內(nèi)存占用的優(yōu)點(diǎn)。回溯方法使用解析空間的最大路徑長(zhǎng)度(o)記憶體，而分支邊界使用解析空間大小(o)記憶體。對(duì)于子集空間，回溯方法需要O(n)的內(nèi)存空間，分支限制需要O(2n)的空間。最大收益或最小消耗分支限制比回溯方法更直觀，在很多情況下，可以檢查比回溯方法少的節(jié)點(diǎn)數(shù)，但在實(shí)際應(yīng)用中，回溯方法超出允許的時(shí)間限制之前，可能會(huì)超過內(nèi)存限制。在解決0-1背包問題的過程中，可以清楚地看到四種茄子算法的優(yōu)點(diǎn)和策略。解決背包問題的四種茄子算法的效率也各不相同。貪心的算法是最有效的，但不一定是最優(yōu)的解決方案?；厮莘椒ㄒ埠芎?，但解決過程很麻煩，是求所有最優(yōu)解。動(dòng)態(tài)計(jì)劃是最差的，因?yàn)檫f歸是使用系統(tǒng)資源最多的方法