算法設(shè)計(jì)技巧論述

算法設(shè)計(jì)技巧論述摘要：本文對(duì)幾種經(jīng)典算法設(shè)計(jì)技巧進(jìn)行了分析和論述。包括貪婪算法、分治算法、動(dòng)態(tài)規(guī)劃、隨機(jī)化算法以及回溯算法，系統(tǒng)的介紹了他們的原理、特點(diǎn)和算法設(shè)計(jì)的步驟，并對(duì)每一種算法進(jìn)行了舉例分析，對(duì)算法設(shè)計(jì)的發(fā)展趨勢(shì)進(jìn)行了展望。關(guān)鍵詞：貪婪算法；分治算法；動(dòng)態(tài)規(guī)劃；隨機(jī)化算法；回溯算法1刖曰隨著科學(xué)技術(shù)的不斷發(fā)展，算法設(shè)計(jì)變得越來越復(fù)雜，算法設(shè)計(jì)的研究受到人們?cè)絹碓蕉嗟闹匾暋Ｌ貏e是計(jì)算機(jī)技術(shù)的廣泛應(yīng)用，更促進(jìn)了算法設(shè)計(jì)相關(guān)理論的研究與發(fā)展。2貪婪算法2.1基本概念概念：貪婪算法（又稱貪心算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。2.2算法思想及算法實(shí)現(xiàn)步?2.2.1算法思想從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。2.2.2實(shí)現(xiàn)該算法的步驟：1、從問題的某一初始解出發(fā)；2、while能朝給定總目標(biāo)前進(jìn)一步do3、求出可行解的一個(gè)解元素；4、由所有解元素組合成問題的一個(gè)可行解;2.3貪婪算法的基本要素對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。2.3.1貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解決子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2.3.2最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2.4貪婪算法的不足及優(yōu)勢(shì)2.4.1貪婪算法的不足：1、不能保證求得的最后解是最佳的；2、不能用來求最大或最小解問題；3、只能求滿足某些約束條件的可行解的范圍。2.4.2貪婪算法的優(yōu)勢(shì)貪婪算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪婪算法與其他算法相比具有一定的速度優(yōu)勢(shì)。如果一個(gè)問題可以同時(shí)用幾種方法解決，貪婪算法應(yīng)該是最好的選擇之一。2.5例題分析2.5.1背包問題題目要求：有一個(gè)背包，背包容量是M=150.有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘?。物品ABCDEFG重量35306050401025價(jià)值10403050354030算法分析：目標(biāo)函數(shù)：￡pi最大約束條件是裝入的物品總重量不超過背包容量，既，訥＜=M(M=150)1、根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？2、每次選取挑選所占重量最小的物品裝入是否能得到最優(yōu)解？3、每次選取單位重量價(jià)值最大的物品，成為解決本題的策略。貪心算法是很常見的算法之一，這是由于它簡單易行，構(gòu)造貪心策略簡單。但是，它需要證明后才能真正運(yùn)用到題目的算法中。一般來說，貪心算法的證明圍繞著整個(gè)問題的最優(yōu)解一定是由在貪心策略中存在的子問題的最優(yōu)解得來的。對(duì)于本例題中的3種貪心策略，都無法成立，即無法被證明，解釋如下：1、貪心策略：選取價(jià)值最大者。反例：W=30物品ABC重量281212價(jià)值302020根據(jù)策略，首先選取物品A，接下來就無法選取了，可是，選取B、C則更好。2、貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。3、貪心策略：選取單位重量價(jià)值最大的物品。反例：W=30物品：ABC重量：282010價(jià)值：282010根據(jù)策略，三種物品單位重量價(jià)值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷，如果選擇A，則答案錯(cuò)誤。值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。比如，求最小生成樹的Prim算法和Krushal算法都是漂亮的貪心算法。2.5.2均分紙牌問題題目要求：有N對(duì)紙牌，編號(hào)分別為1,2,...，n。每堆上有若干張，但紙牌總數(shù)必為n的倍數(shù)，可以在任一堆上取若干張紙牌，然后移動(dòng)。紙牌的規(guī)則為：在編號(hào)為1上取紙牌，只能移動(dòng)到編號(hào)為2的堆上；在編號(hào)為n的堆上取得紙牌，只能移動(dòng)到編號(hào)為n-1的堆上；其他堆上取得紙牌，可以移動(dòng)到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如：n=4,4堆紙牌分別為：①9②8③17④6移動(dòng)三次可以達(dá)到目的：從③取4張牌放到④，再從③取三張放到②，取一張放到①。算法分析：設(shè)a[i]為第I堆紙牌的張數(shù)（0<=I<=n），v為均分后每堆紙牌的張數(shù)，s為最小移動(dòng)次數(shù)。我們用貪心算法，按照從左到右的順序移動(dòng)紙牌。如第I堆的紙牌數(shù)不等于平均值，則移動(dòng)一次（即s加1），分兩種情況移動(dòng)：1、若a[i]>v，則將a[i]-v張從第I堆移動(dòng)到第I+1堆；2、若a[i]<v，則將v-a[i]張從第I+1堆移動(dòng)到第I堆。為了設(shè)計(jì)的方便，我們把這兩種情況統(tǒng)一看作是將a[i]-v從第I堆移動(dòng)到第I+1堆，移動(dòng)后有a[i]=v;a[I+1]=a[I+1]+a[i]-v在從第I+1堆取出紙牌補(bǔ)充第I堆的過程中可能回出現(xiàn)第I+1堆的紙牌小于零的情況。

貪婪算法均分紙牌流程圖貪婪算法均分紙牌流程圖如n=3,三堆指派數(shù)為1227，這時(shí)v=10,為了使第一堆為10,要從第二堆移9張到第一堆，而第二堆只有2張可以移，這是不是意味著剛才使用貪心法是錯(cuò)誤的呢?我們繼續(xù)按規(guī)則分析移牌過程，從第二堆移出9張到第一堆后，第一堆有10張，第二堆剩下-7張，在從第三堆移動(dòng)17張到第二堆，剛好三堆紙牌都是10，最后結(jié)果是對(duì)的，我們?cè)谝苿?dòng)過程中，只是改變了移動(dòng)的順序，而移動(dòng)次數(shù)不便，因此此題使用貪心法可行的。3分治算法3.1基本概念概念：分治算法是指把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題即子問題的合并。題，再把子問題分成更小的子問題直到最后子問題可以簡單的直3.2算法思想及算法實(shí)現(xiàn)步驟3.2.1分治算法的基本思想分治算法的基本思想是將一個(gè)規(guī)模為N的問題分解為K個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題性質(zhì)相同。求出子問題的解，就可得到原問題的解。3.2.2分治法解題的一般步驟分治法解題的一般步驟：1、分解，將要解決的問題劃分成若干規(guī)模較小的同類問題；2、求解，當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決；3、合并，按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。3.2.3算法設(shè)計(jì)模式它的一般的算法設(shè)計(jì)模式如下：Divide-and-conquer(P)1、if|P*02、thenreturn(ADHOc(P))3、將P分解為較小的子問題P1,P2,...,Pk4、fori—1tok5、doyiDivide-and-conquer(Pi)△遞歸解決Pi6、T-MERGE(y1,y2,...,yk)△合并子問題7、return(T)其中|P|表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當(dāng)P的規(guī)模不超過n0時(shí)，直接用算法ADHOc(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1,P2,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。3.3分治算法的分治策略及復(fù)雜性分析3.3.1分治算法的分治策略當(dāng)我們求解某些問題時(shí)，由于這些問題要處理的數(shù)據(jù)相當(dāng)多，或求解過程相當(dāng)復(fù)雜，使得直接求解法在時(shí)間上相當(dāng)長，或者根本無法直接求出。對(duì)于這類問題，我們往往先把它分解成幾個(gè)子問題，找到求出這幾個(gè)子問題的解法后，再找到合適的方法，把它們組合成求整個(gè)問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個(gè)更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個(gè)子問題才較適宜？各個(gè)子問題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問題很難予以肯定的回答。但人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。換句話說，將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復(fù)雜，或者是有多種合并方案，或者是合并方案不明顯，究竟應(yīng)該怎樣合并，沒有統(tǒng)一的模式，需要具體問題具體分析。3.3.2分治算法的復(fù)雜性分析從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是一個(gè)遞歸過程。因此，分治法的計(jì)算效率通?？梢杂眠f歸方程來進(jìn)行分析。為方便起見，設(shè)分解閾值n0=1，且算法ADHOC解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。又設(shè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n/m的子問題去解，而且，將原問題分解為k個(gè)子問題以及用算法MERGE將k個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。如果用T(n)表示該分治法Divide-and-conquer(P)解規(guī)模為|P|=n的問題P所需的計(jì)算時(shí)間，則有：1、T(1)=1T(n)=kT(n/m)+f(n)用算法的復(fù)雜性中遞歸方程解的漸進(jìn)階的解法介紹的解遞歸方程的迭代法，可以求得(1)的解：logm(n-1)2、T(n)=n"(logmK)+E(k"j)*f(n/(m"j))j=0注意，遞歸方程⑴及其解⑵只給出n等于m的方幕時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由等于m的方幕時(shí)T(n)的值可以估計(jì)T(n)的增長速度。通常，我們可以假定T(n)是單調(diào)上升的，從而當(dāng)mi^nn0由于我們關(guān)心的一般是最壞情況下的計(jì)算時(shí)間復(fù)雜度的上界，所以用等于號(hào)（=）還是小于或等于號(hào)（忍）是沒有本質(zhì)區(qū)別的分治法的幾種變形。3.4例題分析3.4.1找出偽幣題目要求：給你一個(gè)裝有16個(gè)硬幣的袋子。16個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。解決方案一：比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務(wù)。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣的任務(wù)完成。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。解決方案二：利用分而治之方法。假如把16硬幣的例子看成一個(gè)大的問題。第一步，把這一問題分成兩個(gè)小問題。隨機(jī)選擇8個(gè)硬幣作為第一組稱為A組，剩下的8個(gè)硬幣作為第二組稱為B組。這樣，就把16個(gè)硬幣的問題分成兩個(gè)8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣?？梢岳脙x器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。最后，在第三步中，用第二步的結(jié)果得出原先16個(gè)硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這16個(gè)硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。把兩個(gè)或三個(gè)硬幣的情況作為不可再分的小問題。注意如果只有一個(gè)硬幣，那么不能判斷出它是否就是偽幣。在一個(gè)小問題中，通過將一個(gè)硬幣分別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。這樣，16硬幣的問題就被分為兩個(gè)8硬幣皿組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。假設(shè)B是輕的那一組，因此再把它分成兩組，每組有4個(gè)硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個(gè)硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個(gè)較輕的組。由于這個(gè)組只有兩個(gè)硬幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即知道哪一個(gè)硬幣輕一些。較輕的硬幣就是所要找的偽幣。分治算法解決偽幣流程圖3.4.2金塊問題題目要求：有一個(gè)老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊。解決方案一：假設(shè)袋中有n個(gè)金塊。可以用函數(shù)Max思想通過n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個(gè)金塊中用類似的方法通過n-2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n-3。解決方案二：分而治之法。當(dāng)n很小時(shí)，比如說，n^2,識(shí)別出最重和最輕的金塊，一次比較就足夠了。當(dāng)n較大時(shí)（n>2），第一步，把這袋金塊平分成兩個(gè)小袋A和&第二步，分別找出在A和B中最重和最輕的金塊。設(shè)A中最重和最輕的金塊分別為HA與LA，以此類推，B中最重和最輕的金塊分別為HB和LB。第三步，通過比較HA和HB，可以找到所有金塊中最重的；通過比較LA和LB，可以找到所有金塊中最輕的。在第二步中，若n>2，則遞歸地應(yīng)用分而治之方法。（開始:平均分堆—H<5=0>是丫否1FHi]分別分堆輸出最小金塊序號(hào)找到重量與其他堆1不同的金塊堆H[i]（_結(jié)束）T—n取半值分治算法查找金塊假設(shè)n=8。這個(gè)袋子被平分為各有4個(gè)金塊的兩個(gè)袋子A和B。為了在A中找出最重和最輕的金塊，A中的4個(gè)金塊被分成兩組A1和A2。每一組有兩個(gè)金塊，可以用一次比較在A中找出較重的金塊HA1和較輕的金塊LA1。經(jīng)過另外一次比較，又能找出HA2和LA2?，F(xiàn)在通過比較HA1和HA2，能找出HA；通過LA1和LA2的比較找出LA。這樣，通過4次比較可以找到HA和LA。同樣需要另外4次比較來確定HB和LB。通過比較HA和HB（LA和LB），就能找出所有金塊中最重和最輕的。因此，當(dāng)n=8時(shí)，這種分而治之的方法需要10次比較。設(shè)c(n)為使用分而治之方法所需要的比較次數(shù)。為了簡便，假設(shè)n是2的幕。當(dāng)n=2時(shí)，c(n)=1。對(duì)于較大的n，c(n)=2c(n/2)+2。當(dāng)n是2的幕時(shí)，使用迭代方法可知c(n)=3n/2-2。在本例中，使用分而治之方法比逐個(gè)比較的方法少用了25%的比較次數(shù)。4動(dòng)態(tài)規(guī)劃4.1基本概念概念：動(dòng)態(tài)規(guī)劃是指，每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策問題的過程就稱為動(dòng)態(tài)規(guī)劃。4.2動(dòng)態(tài)規(guī)劃的基本思想及算法實(shí)現(xiàn)步驟4.2.1動(dòng)態(tài)規(guī)劃的基本思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。4.2.2動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)基本步驟動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動(dòng)路線（通常是求最優(yōu)的活動(dòng)路線）。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài)f|決策1|f|決策2|f|決策n|f結(jié)束狀態(tài)圖1動(dòng)態(tài)規(guī)劃決策過程示意圖1、劃分階段：按照問題的時(shí)間或空間特征，把問題分為若十個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。2、確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。3、確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。4、尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。實(shí)際應(yīng)用中可以按以下幾個(gè)簡化的步驟進(jìn)行設(shè)計(jì)：1、分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。2、遞歸的定義最優(yōu)解。3、以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解4.3算法的適用情況及算法實(shí)現(xiàn)的說明4.3.1適用情況能采用動(dòng)態(tài)規(guī)劃求解的問題的一般要具有3個(gè)性質(zhì):1、最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。2、無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。3、有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。(該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì))。4.3.2算法實(shí)現(xiàn)的說明動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡單。使用動(dòng)態(tài)規(guī)劃求解問題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：1、問題的階段2、每個(gè)階段的狀態(tài)3、從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過程就可以用一個(gè)最優(yōu)決策表來描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對(duì)應(yīng)此問題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值(如最短路徑，最長公共子序列，最大價(jià)值等)，填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解。f(n,m)=max(f(n-1,m),f(n-1,m-w[n])+P(n,m)}4.4動(dòng)態(tài)規(guī)劃的優(yōu)越性與缺點(diǎn)4.4.1動(dòng)態(tài)規(guī)劃的優(yōu)越性k能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求出全局最優(yōu)解。而動(dòng)態(tài)規(guī)劃方法把全過程化為一系列結(jié)構(gòu)相似的子問題，每個(gè)子間題的變量個(gè)數(shù)大大減少，約束集合也簡單得多，易于得到全局最優(yōu)解。特別是對(duì)于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問題，可以對(duì)每個(gè)子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對(duì)于這類問題，動(dòng)態(tài)規(guī)劃通常是求全局最優(yōu)解的唯一方法。2、可以得到一族最優(yōu)解。與非線性規(guī)劃只能得到全過程的一個(gè)最優(yōu)解不同，動(dòng)態(tài)規(guī)劃得到的是全過程及所有后部子過程的各個(gè)狀態(tài)的一族最優(yōu)解。有些實(shí)際問題需要這樣的解族，即使不需要，它們?cè)诜治鲎顑?yōu)策略和最優(yōu)值對(duì)于狀態(tài)的穩(wěn)定性時(shí)也是很有用的。當(dāng)最優(yōu)策略由于某些原因不能實(shí)現(xiàn)時(shí)，這樣的解族可以用來尋找次優(yōu)策略。3、能夠利用經(jīng)驗(yàn)提高求解效率。如果實(shí)際問題本身就是動(dòng)態(tài)的，由于動(dòng)態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動(dòng)態(tài)特征，在計(jì)算中可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解率。比如在策略迭代法中，實(shí)際經(jīng)驗(yàn)?zāi)軌驇椭x擇較好的初始策略，提高收斂速度。4.4.2動(dòng)態(tài)規(guī)劃的主要缺點(diǎn)1、沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個(gè)問題能否構(gòu)造動(dòng)態(tài)規(guī)劃模型的具體準(zhǔn)則(大部分情況只能夠憑經(jīng)驗(yàn)判斷是否適用動(dòng)態(tài)規(guī)劃)。這樣就只能對(duì)每類問題進(jìn)行具體分析，構(gòu)造具體的模型。對(duì)于較復(fù)雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應(yīng)用上的局限性。2、用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)(curseofdimensionality)o若一維狀態(tài)變量有m個(gè)取值，那么對(duì)于n維問題，狀態(tài)xk就有mn個(gè)值，對(duì)于每個(gè)狀態(tài)值都要計(jì)算、存儲(chǔ)函數(shù)fk(xk)，對(duì)于n稍大(即使n=3)的實(shí)際問題的計(jì)算往往是不現(xiàn)實(shí)的。目前還沒有克服維數(shù)災(zāi)的有效的一般方法。4.5例題分析[經(jīng)典例題]背包問題題目要求：從n個(gè)物品中選取裝入背包的物品，每件物品i的重量為wi,價(jià)值為pi。求使物品價(jià)值最高的選取方法。題目分析：初看這類問題，第一個(gè)想到的會(huì)是貪心，但是貪心法卻無法保證一定能得到最優(yōu)解，看以下實(shí)例：貪心準(zhǔn)則1：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品。利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2,w=[100,10,10],p=[20,15,15],c=105°（c為背包容量，n為物品數(shù)量）當(dāng)利用價(jià)值貪婪準(zhǔn)則時(shí)，獲得的解為x=[1，0，0]，這種方案的總價(jià)值為20。而最優(yōu)解為[0，1，1]，其總價(jià)值為30。貪心準(zhǔn)則2：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n=2,w=[10,20],p=[5,100],c=25。當(dāng)利用重量貪婪策略時(shí)，獲得的解為x=[1,0],比最優(yōu)解[0,1]要差。貪心準(zhǔn)則3：價(jià)值密度pi/wi貪婪算法，這種選擇準(zhǔn)則為：從剩余物品中選擇可裝入包的pi/wi值最大的物品，但是這種策略也不能保證得到最優(yōu)解。利用此策略n=3,w=[20,15,15],p=[40,25,25],c=30時(shí)的得到的就不是最優(yōu)解。由以上的三種貪心策略可知，本題如果采用貪心方法求解，則完全取決于輸入的數(shù)據(jù)，不管采用哪種方法都不能保證完全正確。要使物品價(jià)值最高，即p1*x1+p2*x1+...+pi*xi（其1<=i<=n，x取0或1，取1表示選取物品i）取得最大值。在該問題中需要決定x1...xn的值。假設(shè)按i=1，2，...n的次序來確定xi的值。如果置x1=0，則問題轉(zhuǎn)變?yōu)橄鄬?duì)于其余物品（即物品2,3,.，n），背包容量仍為c的背包問題。若置x1=1，問題就變?yōu)殛P(guān)于最大背包容量為C-W1的問題?，F(xiàn)設(shè)r={c,C-W1}為剩余的背包容量。在第一次決策之后，剩下的問題便是考慮背包容量為r時(shí)的決策。不管x1是0或是[x2,.,xn]必須是第一次決策之后的一個(gè)最優(yōu)方案。也就是說在此問題中，最優(yōu)決策序列由最優(yōu)決策子序列組成。這樣就滿足了動(dòng)態(tài)規(guī)劃的程序設(shè)計(jì)條件。動(dòng)態(tài)規(guī)劃思路：階段i：在前i件物品中，選取若干件物品放入背包中；狀態(tài)：在前i件物品中，選取若干件物品放入所?？臻g為c的背包中的所能獲得的最大價(jià)值；決策：第i件物品放或者不放；由此可以寫出動(dòng)態(tài)轉(zhuǎn)移方程：用f[i,j]表示在前i件物品中選擇若干件放在所剩空間為j的背包里所能獲得的最大價(jià)值f[i,j]=max{f[i-1,j-wi]+pi(j>=wi),f[i-1,j]}這樣，就可以自底向上地得出在前n件物品中取出若干件放進(jìn)背包能獲得的最大價(jià)值，也就是f[n,c]。5隨機(jī)化算法5.1隨機(jī)化算法的基本概述隨機(jī)化算法是這樣一種算法，在算法中使用了隨機(jī)函數(shù)，且隨機(jī)函數(shù)的返回值直接或者間接的影響了算法的執(zhí)行流程或執(zhí)行結(jié)果。隨機(jī)化算法基于隨機(jī)方法，依賴于概率大小。這種算法看上去是憑著運(yùn)氣做事，其實(shí)，隨機(jī)化算法是有一定的理論基礎(chǔ)的，我們可以想象，在[1,10000]這個(gè)閉區(qū)間里，隨機(jī)1000次，隨機(jī)到2這個(gè)數(shù)的幾率是多大(約為0.001)，何況1000次的隨機(jī)在計(jì)算機(jī)程序中僅僅是一眨眼的功夫?？梢钥闯?，隨機(jī)化算法有著廣闊的前景。只是由于隨機(jī)化算法比較難于掌控，所以并不是很多人都接觸過他，但肯定有很多人都聽說過。5.2隨機(jī)化算法的基本原理及類別隨機(jī)化算法的基本原理是:當(dāng)某個(gè)決策中有多個(gè)選擇，但又無法確定哪個(gè)是好的選擇，或確定好的選擇需要付出較大的代價(jià)時(shí)，如果大多數(shù)選擇是好的，那么隨機(jī)地選一個(gè)往往是一種有效的策略。通常當(dāng)一個(gè)算法需要作出多個(gè)決策，或需要多次執(zhí)行一個(gè)算法時(shí)，這一點(diǎn)表現(xiàn)得尤為明顯。這個(gè)原理使得隨機(jī)化算法有一個(gè)共同的性質(zhì):沒有一個(gè)特別的輸人會(huì)使算法執(zhí)行出現(xiàn)最壞情況。實(shí)際算法設(shè)計(jì)時(shí)，隨機(jī)化算法可大致分為如下四方面：1、在判定性問題中，如果待檢查的狀態(tài)非常之多，那么.可以考慮進(jìn)行隨機(jī)抽樣，或者是考慮一個(gè)“不怎么對(duì)”的算法〔假設(shè)其正確率為p<100%）。那么如果將這個(gè)算法執(zhí)行很多遍（設(shè)為k），那么其整體誤判率為（1p）&，當(dāng)k遞增時(shí)，整體誤判率就會(huì)趨近于零。這類算法被稱作Monte-Carl算法。例如:一個(gè)判斷算法，它有50%的幾率將正確結(jié)果判成錯(cuò)誤，但是錯(cuò)誤一定能判斷出來，那么當(dāng)此算法運(yùn)行10次，整體的誤判率大約為0.1%。這樣做的好處在于如果能找到一個(gè)時(shí)間復(fù)雜度的階小于原算法的非完全正確算法，就可以將時(shí)間復(fù)雜度的階降下來。比如上面的算法，如果運(yùn)行20次，那么誤判率將達(dá)到百萬分之一的地步，但是時(shí)間復(fù)雜度只不過乘上一個(gè)20的常數(shù)。當(dāng)問題規(guī)模很大的時(shí)候，用一點(diǎn)點(diǎn)的正確率去換大量的時(shí)間在實(shí)際應(yīng)用上是非常值得的。事實(shí)上，以這種方式換取代碼的簡便甚至是降低思維難度都是不錯(cuò)的應(yīng)用。但是值得注意的是，這個(gè)算法畢竟不是100%正確的。2、當(dāng)一類算法對(duì)于數(shù)據(jù)的處理順序敏感，并在極端情況下會(huì)令算法達(dá)到一個(gè)難以讓人接受的時(shí)間復(fù)雜度下界，那么可以通過隨機(jī)打亂數(shù)據(jù)的排列來使得算法盡量避免極端情況，從而使算法得到期望下的運(yùn)行時(shí)間。這類算法被稱Shersood算法。一個(gè)最好的例子便是快速排序。當(dāng)給定待排序數(shù)組是有序的時(shí)候，最原始的快速排序會(huì)因?yàn)閯澐植痪嘶?（n2），那么這就失去了快速排序的意義了。常用的方法就是隨機(jī)打亂數(shù)組的排列，或者更簡單的，在取分割點(diǎn)的時(shí)候隨機(jī)一個(gè)數(shù)組下標(biāo)。當(dāng)然這會(huì)牽扯出一個(gè)問題，就是隨機(jī)的時(shí)候如果出現(xiàn)”運(yùn)氣不好”的情況怎么辦?可以直觀的想:是把一個(gè)普通的情況隨機(jī)成極端情況幾率大?還是把極端情況隨機(jī)到普通情況大?這個(gè)是一目了然的。而且經(jīng)驗(yàn)主義的看法認(rèn)為:在統(tǒng)計(jì)情況下產(chǎn)生極端情況（如快速排序中的待排序列為有序序列）的概率是非常小的，這種情況通常都是利用算法特點(diǎn)被人為地特殊構(gòu)造出來的。3、當(dāng)一類問題的解很豐富，并且只要求一個(gè)任意解的時(shí)候（或者可以理解為不考慮解的優(yōu)劣性），那么可在中間步驟作決策的時(shí)候干脆“猜”上一個(gè)來碰碰運(yùn)氣。盡管事前并不知道這個(gè)猜測(cè)會(huì)帶來什么樣的結(jié)果，但是這樣至少省去了檢查全部可能性的麻煩，況且可能狀態(tài)的總數(shù)也許是一個(gè)天文數(shù)字，這對(duì)只要找一組解的任務(wù)來說無疑是代價(jià)太大了。這類算法被稱作LasVegas算法。一個(gè)經(jīng)典例子是隨機(jī)n皇后問題。當(dāng)n很大時(shí)，搜索無法勝任，那么可以考慮每一行亂放一個(gè)位置，這樣有一定概率得到解，至少比搜索得不到解要來的好。要注意的是，這類算法很有可能找不到任何結(jié)果。所以可以考慮作如下改進(jìn):在算法里進(jìn)行控制使得在允許期望時(shí)間內(nèi)程序猜許多次，或者加人一些估價(jià)方法，讓程序盡量去“猜”那些“看上去”能找到解的決策（注意，不一定是最優(yōu)值，否則就退化成貪心了）。4、在部分?jǐn)?shù)值計(jì)算問題中，由于精確解難以直接求得，通常采用一些概率方法來逼近要求的答案，利用計(jì)算機(jī)計(jì)算量大的特點(diǎn)來獲得一定精度下的答案。這類算法被稱為數(shù)值概率算法。例如用投點(diǎn)法計(jì)算圓周率:作一個(gè)2*2的正方形并作出其內(nèi)接圓，然后在這個(gè)正方形內(nèi)各處等概率投點(diǎn)。那么由于落下點(diǎn)概率與面積成正比，所以在圓內(nèi)的點(diǎn)數(shù)除以總點(diǎn)數(shù)再乘以正方形的面積4就能得到圓周率的一個(gè)近似值。這種算法的最大特點(diǎn)是運(yùn)行時(shí)間越長，理論上就能得到越精確的值。換句話說，如果能隨機(jī)投無窮多個(gè)點(diǎn)，理論上就能得到精確的Pi值。但是話說回來，這畢竟是一種逼近算法，只是用于計(jì)算一些比較扭曲且精度要求不高的式子，對(duì)于要求精確的一些數(shù)值和公式還是得通過數(shù)學(xué)分析的方式來進(jìn)行計(jì)算。但是在計(jì)算某些不規(guī)則的數(shù)值的時(shí)候還是能起到奇效的。5.3例題分析及應(yīng)用5.3.1字符串問題題目要求：一個(gè)長度在4..10的字符串中，需要判定是否可以在字符串中刪去若干字符，使得改變后字符串符合以下條件之一：（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA

“D”兩個(gè)字母，例如：長度為6字符串"POPKDK”，若刪除其中的“O”，則原串變?yōu)椋骸癙PKK”，符合條件(2)“D”兩個(gè)字母，題目分析：這道題很容易想到一種算法：運(yùn)用排列組合：枚舉每4個(gè)字母，然后逐一判斷。算法是可行的，但是如果需要題目中加上一句話：需要判斷n個(gè)字符串，且n<=100000，那么這樣的耗時(shí)是不能讓人忍受①的，因?yàn)樵诿杜e的過程中，是非常浪費(fèi)時(shí)間的。(①：這里是指信息學(xué)中要求算法的普遍運(yùn)算時(shí)間為：1000ms)所以這道題有可能可以借助于隨機(jī)化算法，下面我們來算一下在10個(gè)字符中取4個(gè)字符一共有多少種取法：C(4,10)=210。那么很容易得知，隨機(jī)化算法如果隨機(jī)300次，能得到的結(jié)果基本上就正確了(概率為1-(209/210)^300，約為0.76)，而隨機(jī)時(shí)的時(shí)間消耗是O(1)，只需要判斷沒有隨機(jī)重復(fù)即可，判重的時(shí)間復(fù)雜度也為O(1)，并且最多隨機(jī)300次，這樣就可以有效地得到答案，最大運(yùn)算次數(shù)為：O(300n)，這是在計(jì)算機(jī)的承受范圍內(nèi)(1000ms)的。隨機(jī)算法流程圖隨機(jī)算法流程圖從這里就能看出，隨機(jī)化算法是一個(gè)很好的概率算法，但是它并不能保證正確，而且它單獨(dú)使用的情況很少，大部分是與其他的算法：例如貪心、搜索等配合起來運(yùn)用。5.3.2排序問題快速排序是排序方法中較為便捷的方法之一，但是由于它極不穩(wěn)定，最好的時(shí)候時(shí)間復(fù)雜度為O(nlogn)，這里的log是指以2為底的對(duì)數(shù)運(yùn)算。最壞的時(shí)候能達(dá)到與普通排序方法一樣的O(n”2)。而制約快速排序的有兩個(gè)：一是數(shù)據(jù)，越無序的數(shù)據(jù)，快排的速度越快；二是中間點(diǎn)的枚舉。因?yàn)閮蓚€(gè)制約條件都與隨機(jī)有著不可分開的關(guān)系。所以，在快速排序中加入隨機(jī)化算法無疑是十分重要的。運(yùn)用在：1、數(shù)據(jù)讀入時(shí)，隨機(jī)排放數(shù)據(jù)位置。2、中間點(diǎn)的枚舉進(jìn)行多次隨機(jī)化后決定。這樣就基本上將快速排序的時(shí)間復(fù)雜度維持在最好狀態(tài)。6回溯算法6.1回溯算法的基本概念概念：回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法。6.2回溯算法的算法思想及算法步驟6.2.1回溯算法的基本思想同溯算法是算法設(shè)計(jì)的基木方法之一，其主要思想是:不斷地用修改過的規(guī)范函數(shù)V;}x;,x}}...，x;)}稱限界函數(shù))去測(cè)試止在構(gòu)造中的n元組的部分量(}x;,x}}..}x;)，看其是否可能導(dǎo)致最優(yōu)解，如果判定(x,,x},}',x;)不可能導(dǎo)致最優(yōu)解，那么就將可能要測(cè)試的x;.;,x;十2,…,x.,個(gè)向量一概略去，因此，同溯算法作的測(cè)試次數(shù)要少的多。6.2.2回溯算法的算法步驟用回溯算法解決問題的一般步驟為：1、定義一個(gè)解空間，它包含問題的解。2、利用適于搜索的方法組織解空間。3、利用深度優(yōu)先法搜索解空間。4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。問題的解空間通常是在搜索問題的解的過程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。6.3回溯算法的一般問題描述及解決方法6.3.1回溯算法的一般問題描述可用回溯法求解的問題P，通常要能表達(dá)為:對(duì)于已知的由n元組（x1，x2,…，xn）組成的一個(gè)狀態(tài)空間E=（（x1，x2，…，xn）|x^Si，i=1，2，…，n｝，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。中Si是分量xi的定義域，且|Si|有限，i=1，2，?，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。解問題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地檢測(cè)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。我們發(fā)現(xiàn)，對(duì)于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<i）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0忍j忍n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2,…，xi的一個(gè)約束，nNi>j。因此，對(duì)于約束集D具有完備性的問題P，一旦檢測(cè)斷定某個(gè)j元組（xl,x2,…，xj）違反D中僅涉及（xl,x2,…，xj的一個(gè)約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（xl，x2,…，xj，xj+1，…，xn）都不會(huì)是問題P的解，因而就不必去搜索它們、檢測(cè)它們。回溯法正是針對(duì)這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。6.3.2回溯算法的解題思路回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：設(shè)Si中的元素可排成xi（1），xi（2），…，xi（mi-l），|Si|二mi，i=1，2，…，n。從根開始，讓T的第I層的每一個(gè)結(jié)點(diǎn)都有mi個(gè)兒子。這mi個(gè)兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1（1），xi+1（2），…，xi+1（mi），i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個(gè)n元組（x1，x2，…，xn）對(duì)應(yīng)于T中的一個(gè)葉子結(jié)點(diǎn)，T的根到這個(gè)葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對(duì)于任意的0織住n-1，E中n元組（x1，x2，…，xn）的一個(gè)前綴I元組（x1，x2，…，xi）對(duì)應(yīng)于T中的一個(gè)非葉子結(jié)點(diǎn)，T的根到這個(gè)非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x1，x2,…，乂^反之亦然。特別，E中的任意一個(gè)n元組的空前綴（），對(duì)應(yīng)于T的根。因而，在E中尋找問題P的一個(gè)解等價(jià)于在T中搜索一個(gè)葉子結(jié)點(diǎn)，要求從T的根葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個(gè)權(quán)x1,x2,…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1,x2）、…，前綴I元組（x1,x2,…，xi）,…，直到i=n為止。在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個(gè)結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)解狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)回答狀態(tài)結(jié)點(diǎn)，它對(duì)應(yīng)于問題P的一個(gè)解。對(duì)于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T,利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點(diǎn)的所有狀態(tài)結(jié)點(diǎn)，而跳過對(duì)肯定不含回答結(jié)點(diǎn)的所有子樹的搜索，以提高搜索效率。具體地說，當(dāng)搜索按深度優(yōu)先策略到達(dá)一個(gè)滿足D中所有有關(guān)約束的狀態(tài)結(jié)點(diǎn)時(shí)，即“激活”該狀態(tài)結(jié)點(diǎn)，以便繼續(xù)往深層搜索；否則跳過對(duì)以該狀態(tài)結(jié)點(diǎn)為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點(diǎn)的祖先結(jié)點(diǎn)回溯，一邊“殺死”其兒子結(jié)點(diǎn)已被搜索遍的祖先結(jié)點(diǎn)，直到遇到其兒子結(jié)點(diǎn)未被搜索遍的祖先結(jié)點(diǎn)，即轉(zhuǎn)向其未被搜索的一個(gè)兒子結(jié)點(diǎn)繼續(xù)搜索。在搜索過程中，只要所激活的狀態(tài)結(jié)點(diǎn)又滿足終結(jié)條件，那么它就是回答結(jié)點(diǎn)，應(yīng)該把它輸出或保存。由于在回溯法求解問題時(shí)，一般要求出問題的所有解，因此在得到回答結(jié)點(diǎn)后，同時(shí)也要進(jìn)行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點(diǎn)均已被搜索過為止。6.4例題分析6.4.1組合問題問題描述：找出從自然數(shù)1，2,…，n中任取r個(gè)數(shù)的所有組合。問題分析：采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質(zhì)：1、a[i+1]>a[i]，后一個(gè)數(shù)字比前一個(gè)大；2、a[i]-i<=n-r+1o按回溯法的思想，找解過程可以敘述如下：首先放棄組合數(shù)個(gè)數(shù)為r的條件，候選組合從只有一個(gè)數(shù)字1開始。因該候選解滿足除問題規(guī)模之外的全部條件，擴(kuò)大其規(guī)模，并使其滿足上述條件1，候選組合改為1，2。繼續(xù)這一過程，得到候選組合1，2,3。該候選解滿足包括問題規(guī)模在內(nèi)的全部條件，因而是一個(gè)解。在該解的基礎(chǔ)上，選下一個(gè)候選解，因a[2]上的3調(diào)整4，以及以后調(diào)整為5都滿足問題的全部要求，得到解1，2,4和1，2,5。由于對(duì)5不能再作調(diào)整，就要從a[2]回溯到a[1]，這時(shí)，a[1]=2,可以調(diào)整為3,并向前試探，得到解1,3,4。重復(fù)上述向前試探和向后回溯，直至要從a[0]再回溯時(shí)，說明已經(jīng)找完問題的全部解。回溯法解決組合問題6.4.2填字游戲問題描述：在3X3個(gè)方格的方陣中要填入數(shù)字1到N(NN10)內(nèi)的某9個(gè)數(shù)字，每個(gè)方格填一個(gè)整數(shù)，似的所有相鄰兩個(gè)方格內(nèi)的兩個(gè)整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個(gè)要求的各種數(shù)字填法。問題分析：可用試探發(fā)找到問題的解，即從第一個(gè)方格開始，為當(dāng)前方格尋找一個(gè)合理的整數(shù)填入，并在當(dāng)前位置正確填入后，為下一方格尋找可填入的合理整數(shù)。如不能為當(dāng)前方格找到一個(gè)合理的可填證書，就要回退到前一方格，調(diào)整前一方格的填入數(shù)。當(dāng)?shù)诰艂€(gè)方格也填入合理的整數(shù)后，就找到了一個(gè)解，將該解輸出，并調(diào)整第九個(gè)的填入的整數(shù)，尋找下一個(gè)解。為找到一個(gè)滿足要求的9個(gè)數(shù)的填法，從還未填一個(gè)數(shù)開始，按