【文章內(nèi)容簡介】 程序的理解； 健壯性：算法應(yīng)具有容錯處理，當(dāng)輸入為非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。 效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí) 行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關(guān)。 經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法 6. 迭代法 : 也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。 ，需要做好以下三個方面的工作： 1)、確定迭代 模型 。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。 2)、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代 關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。 3)、對迭代過程進行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析出用來結(jié)束迭代過程的條件。 是： 將一個規(guī)模為 n 的問題分解為 k 個規(guī)模較小的子問題，這些子問 題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。 ： （ 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （ 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （ 3）利用該問題分解出的子問題的解可以合并為該問題的解； （ 4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 分治法的基本步驟 分治法 在每一層遞歸上都有三個步驟： （ 1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題； （ 2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題； （ 3）合并：將各個子問題的解合并為原問題的解。 11. 動態(tài)規(guī)劃的基本思想 前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為 標(biāo)準動態(tài)規(guī)劃 ，這種標(biāo)準動態(tài)規(guī)劃是在研 究多階段決策問題時推導(dǎo)出來的，具有嚴格的數(shù)學(xué)形式，適合用于理論上的分析。在實際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。 動態(tài)規(guī)劃的實質(zhì)是 分治思想 和 解決冗余 ，因此， 動態(tài)規(guī)劃 是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。 由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。 貪心法 的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇； 而分治法中的各個子問題是獨立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。 不足之處：如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。 解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個 解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。 因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。 1動態(tài)規(guī)劃算法的基本步驟 設(shè)計一個標(biāo)準的動態(tài)規(guī)劃算法，通?？砂匆韵聨讉€步驟進行： （ 1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)劃求解。 （ 2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 （ 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所 以把這兩步放在一起，是因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。 （ 4）寫出規(guī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達式。 一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值 ，但是一般將其改為遞推計算。實際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計動態(tài)規(guī)劃，而是按以下幾個步驟進行： （ 1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 （ 2）遞歸地定義最優(yōu)值。 （ 3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。 （ 4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。 步驟（ 1）～（ 3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（ 4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（ 4）。此時，在步驟（ 3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟 （ 4）中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解。 總結(jié)： 動態(tài)規(guī)劃實際上就是最優(yōu)化的問題，是指將原問題的大實例等價于同一最優(yōu)化問題的較小實例，自底向上的求解最小實例，并將所求解存放起來，存放的結(jié)果就是為了準備數(shù)據(jù)。與遞歸相比，遞歸是不斷的調(diào)用子程序求解，是自 頂向下的調(diào)用和求解。 13. 分治 法與動態(tài)規(guī)劃法的 相同點是： 將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。 兩者的不同點是 ：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問 題，經(jīng)分解得到的子問題往往是互相獨立的。 14. 回溯法 回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時，就選擇下一個候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程稱為回溯。擴大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。 15. 分支限界法： 這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。 算法思想： 分枝限界（ branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對 E節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成 E節(jié)點。當(dāng)一個節(jié)點變?yōu)?E節(jié)點時，則生成從該節(jié)點移動一步即可到達的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個 E節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結(jié) 束。 有兩種常用的方法可用來選擇下一個 E節(jié)點 （雖然也可能存在其他的方法）： 1) 先進先出（ F I F O） 即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活 節(jié)點表的性質(zhì)與 隊列相同。 2) （優(yōu)先隊列）最小耗費或最大收益法在這種模式中，每個節(jié)點都有一個對應(yīng)的耗費或收益。如果查找 一個具有最小耗費的解，則活節(jié)點表可用最小堆來建立，下一個 E節(jié)點就是具有最小耗費 的活節(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點表，下一個 E節(jié)點是具有最大收益的活節(jié)點 16. 分支限界法與回溯法的 相 同 點是： 都是一種在問題的解空間樹 T 中搜索問題解的算法。 不同點： （ 1）求解目標(biāo)不同； （ 2）搜索方式不同； （ 3）對擴展結(jié)點的擴展方式不同； （ 4）存儲空間的要求不同。 17. 分治法所能解決的問題一般具有的幾個特征是 ： （ 1）該問題的規(guī)模縮小到一定的程度就可以容易地解決； （ 2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 。 （ 3） 利用該問題分解出的子問題的解可以合并為該問題的解； （ 4） 原問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 18. 用 分支限界法 設(shè)計算法的步驟 是： (1)針對所給問題，定義問題的解空間（對解進行編碼）； (2)確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解） ； (3)以廣度優(yōu)先或以最小耗費（ 最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 19. 常見的兩種分支限界法 的算法框架 ： （ 1）隊列式 (FIFO)分支限界法： 按照隊列先進先出（ FIFO）原則選取下一個節(jié)點為擴展節(jié)點。 （ 2）優(yōu)先隊列式分