【正文】 0。){print(a[p])。p:=c[p]。}} 上節(jié) 下節(jié) 算法策略和算法是有區(qū)別的 ,它們是算法設(shè)計中的兩個方面， 算法策略 是面向問題的 ,算法 是面向?qū)崿F(xiàn)的；但二者又是不可分的 ,首先是通過算法策略才找出解決問題的算法，其次對于用不同算法求解的問題算法策略是自然不同的。 本章共介紹了五種算法策略 ,它們互相有著一定的差別，適應(yīng)的問題也有所差異。 上節(jié) 下節(jié) 算法策略間的比較 “ 貪婪算法 ” “ 遞推法 ” “ 遞歸法 ” “ 枚舉法 ” “ 遞歸回朔法 ” “ 分治法 ” “ 動態(tài)規(guī)劃法 ” 上節(jié) 下節(jié) 不同算法策略特點小結(jié)“貪婪算法 ” 這些策略求解的是最簡單的一類問題，或者說是對問題要求最嚴(yán)格的算法策略。 “ 貪婪算法 ” 解決這類問題是按一定順序（從前向后或從后向前等）一定的策略，只需考慮當(dāng)前局部信息就能做出決策，即所謂局部最優(yōu)就是全局最優(yōu)。 上節(jié) 下節(jié)“遞推法 ” “ 遞推法 ” 和貪婪算法一樣也是由當(dāng)前問題的逐步解決從而得到整個問題的解，只是依賴的是信息間本身的遞推關(guān)系，每一步不需要策略參與到算法中，它們更多地用于計算。 上節(jié) 下節(jié)“遞歸法 ” 和遞推法類似，遞歸法是利用大問題與其子問題間的遞歸關(guān)系來解決問題的。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為 N的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。特別地，當(dāng)規(guī)模 N=1時，能直接得解。 上節(jié) 下節(jié)“枚舉法 ” 枚舉法既是一個策略，也是一個算法，也是一個分析問題的手段。枚舉法的求解思路很簡單 ,就是對所有可能的解逐一嘗試，從而找出問題的真正解。當(dāng)然這就要求所解的問題可能的解是 有限的、固定的 ，不會產(chǎn)生組合爆炸、容易枚舉的。多用于決策類問題。這類問題都不易進行問題的分解，只能 整體來求解 。 上節(jié) 下節(jié)“遞歸回朔法 ” 類似于枚舉法的思想 ,遞歸回朔法通過遞歸嘗試遍問題各個可能解的通路，發(fā)現(xiàn)此路不通時回朔到上一步繼續(xù)嘗試別的通路。在下一章中對其應(yīng)用做詳細(xì)介紹。 上節(jié) 下節(jié)“分治法 ” 求解的則是較復(fù)雜的問題，這類問題是可以被分解成 獨立的子問題 來解決的，將兩個或兩個以上的獨立子問題的解“ 合成 ” ，就得到較大的子問題的解，最后合成為總問題的解。 上節(jié) 下節(jié)“動態(tài)規(guī)劃法 ” 動態(tài)規(guī)劃法與貪心法類似 ，是通過多階段決策過程來解決問題的。但每個階段決策的結(jié)果是一個決策結(jié)果序列，這個結(jié)果序列中最后采用哪一個結(jié)果取決于以后每個階段決策，因此稱為 “ 動態(tài) ” 規(guī)劃法。當(dāng)然每一次的決策結(jié)果序列都必須進行存儲。因此，可以說 “ 動態(tài)規(guī)劃是高效率、高消費的算法 ” 。 另一方面， 動態(tài)規(guī)劃法與分治法類似 ，當(dāng)問題不能分解為獨立的子問題 ,但又符合最優(yōu)化原理 (最優(yōu)子結(jié)構(gòu)性質(zhì) )時 ,用動態(tài)規(guī)劃，通過多階段決策過程從逐步找出子問題的最優(yōu)解，從而決策出問題的結(jié)果。 上節(jié) 下節(jié) 1. 對問題進行分解的算法策略 分治法 與 動態(tài)規(guī)劃法 2. 多階段過程 貪婪算法 、 遞推法 、 遞歸法 和 動態(tài)規(guī)劃法 3. 全面逐一嘗試、比較 蠻力法 、 枚舉法 、 遞歸回溯法 4．算法策略的中心思想 上節(jié) 下節(jié) 算法策略間的關(guān)聯(lián) “ 分治法 ” 與 “ 動態(tài)規(guī)劃法 ” “ 分治法 ” 與 “ 動態(tài)規(guī)劃法 ” 都是 遞歸思想 的應(yīng)用之一，是找出大問題與小的子問題之間的關(guān)系 ,直到小的子問題很容易解決，再由小的子問題的解導(dǎo)出大問題的解。區(qū)別在于： 上節(jié) 下節(jié)分治法 所能解決的問題一般具有以下幾個特征： 1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 2) 該問題可以分解為若干個規(guī)模較小的相同問題，即該問 題具有。 3) 利用該問題分解出的子問題的解可以合并為該問題的解 。 4) 該問題所分解出的各個子問題是相互獨立的，即子問題 之間不包含公共的子問題。 上節(jié) 下節(jié)第一條特征是絕大多數(shù)問題都可以滿足的 。 第二條特征是應(yīng)用分治法的前提 ,它也是大多數(shù)問題可以滿足的 。 第三條特征是關(guān)鍵。 第四條特征涉及到分治法的效率。 動態(tài)規(guī)劃的 實質(zhì) 是分治思想和解決冗余。 上節(jié) 下節(jié)2．多階段過程 “ 貪婪算法 ” 、 “ 遞推法 ” 、 “ 遞歸法 ” 和 “ 動態(tài)規(guī)劃法 ” 多階段過程就是按一定順序 (從前向后或從后向前等 )一定的策略 , 逐步解決問題的方法。 “ 貪婪算法 ” 每一步根據(jù)策略得到一個結(jié)果傳遞到下一步，自頂向下，一步一步地作出貪心選擇。 上節(jié) 下節(jié)“ 動態(tài)規(guī)劃法 ” 則根據(jù)一定的決策 , 每一步?jīng)Q策出的不是一個結(jié)果，而只是使問題的規(guī)模不斷的縮小，如果決策比較簡單 ,是一般的算法運算 ,則可找到不同規(guī)模問題間的關(guān)系，使算法演變成 “ 遞推法 ” 、 “ 遞歸法 ” 算法 ,所以說動態(tài)規(guī)劃更側(cè)重算法設(shè)計策略，而不是算法。 “ 遞推法 ” 、 “ 遞歸法 ” 更注重每一步之間的關(guān)系 ,決策的因素較少。 “ 遞推法 ” 根據(jù)關(guān)系從前向后推 ,由小規(guī)模的結(jié)論 ,推解出問題的解。 “ 遞歸法 ” 根據(jù)關(guān)系先從后向前使大問題，轉(zhuǎn)化為小問題，最后同樣由小規(guī)模結(jié)論，推解出問題的解。 上節(jié) 下節(jié)3．全面逐一嘗試、比較 “ 蠻力法 ” 、 “ 枚舉法 ” 、 “ 遞歸回溯法 ” 考慮到有這樣一類問題，問題中不易找到信息間的相互關(guān)系，也不能分解為獨立的子問題 ,似乎只有把各種可能情況都考慮到 ,并把全部解都列出來之后 ,才能判定和得到最優(yōu)解。對于規(guī)模不大的問題，這些策略簡單方便 。而當(dāng)問題的計算復(fù)雜度高且計算量很大時 ,還是考慮采用 “ 動態(tài)規(guī)劃法 ” 這個更有效的算法策略 。 上節(jié) 下節(jié)枚舉法算法的實現(xiàn) 依賴于循環(huán) ,通過循環(huán)嵌套枚舉問題中各種可能的情況 ,如八皇后問題能用八重循環(huán)嵌套枚舉。而對于規(guī)模 不固定 的問題就無法用固定重數(shù)的循環(huán)嵌套來枚舉了 ,有的問題可能通過變換枚舉對象也能用循環(huán)嵌套枚舉實現(xiàn) ,但更多的任意指定規(guī)模的問題是靠遞歸回朔法來 “ 枚舉 ” 或 “遍歷 ” 各種可能的情況。比如 n皇后問題只能用 “ 遞歸回朔法” 通過遞歸實現(xiàn)（當(dāng)然可以通過棧 ,而不用遞歸）。 上節(jié) 下節(jié)4．算法策略的中心思想 所有算法策略的中心思想就是用算法的基本工具循環(huán)機制和遞歸機制實現(xiàn)算法。遞推法自然不用多說，貪婪算法就是逐步?jīng)Q策解決問題，動態(tài)規(guī)劃也是。 上節(jié) 下節(jié) 算法策略側(cè)重的問題類型 一般我們在實際應(yīng)用中遇到的問題主要分為四類 :判定性問題、計算問題、最優(yōu)化問題和構(gòu)造性問題。 遞推法 、 遞歸法 算法較適合解決判定性問題、計算問題。 “ 貪婪算法 ” 、 “ 分治法 ” 、 “ 動態(tài)規(guī)劃法 ” 與 “ 枚舉法 ” 較適合解最優(yōu)化問題。 構(gòu)造性問題更多地依賴于人的經(jīng)驗和抽象能力，算法一般是人類智能充分對問題解決步驟細(xì)化后才能得到算法，少有通用的算法策略。當(dāng)然也有一些問題在構(gòu)造過程中使用通用的算法策略。 上節(jié) 下節(jié)下面就最優(yōu)化問題討論如下： 在現(xiàn)實生活中，有這樣的問題：他有 n個輸入 , 而他的解就由 n個輸入的某個子集組成，只是這個子集必須滿足某些事先給定的條件。把那些必須滿足的條件稱為 約束條件 。而把滿足約定條件的子集稱為該問題的 可行解 。顯然 ,滿足約束條件的子集可能不止一個 ,因此，可行解一般來說是不唯一的。為了衡量可行解的優(yōu)劣，事先也給出了一定的標(biāo)準(zhǔn) ,這些標(biāo)準(zhǔn)一般以函數(shù)形式給出 , 這些函數(shù)稱為 目標(biāo)函數(shù) 。 那些使目標(biāo)函數(shù)取極值的可行解， 稱為 最優(yōu)解 , 這一類需求取最優(yōu)解的問題 , 又可根據(jù)描述約束條件和目標(biāo)函數(shù)的 數(shù)學(xué)模型的特性或求借問題方法的不同進行而細(xì)分為 線形規(guī)則 、 整數(shù)規(guī)則 、 非線形規(guī)則 、 動態(tài)規(guī)劃 等問題。 上節(jié) 下節(jié)盡管各類規(guī)劃問題都有一些相應(yīng)的求解方法，但其中的某些問題，還可用一種更直接的方法來求解，這種方法就叫 貪心方法 。 動態(tài)規(guī)劃法 是將問題實例歸納為更小的、 相似的子問題 , 并通過求解子問題產(chǎn)生一個全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇 , 但不依賴于有待于做出的選擇和子問題。 而 分治法 中的各個子問題是獨立的 (即不包含公共的子子問題 ),因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是 , 如果當(dāng)前選擇可能要依賴子問題的解時 , 則難以通過局部的貪心策略達到全局最優(yōu)解 。如果各子問題是不獨立的 ,則分治法要做許多不必要的工作 ,重復(fù)地解公共的子問題。 上節(jié) 下節(jié)動態(tài)規(guī)劃在解決不獨立子問題時，是分為若干個階段進行的 ,而且在任一階段后的行為都僅依賴 i階段的過程狀態(tài) , 而與 i階段之前的過程如何達到這種狀態(tài)的方法無關(guān) ,這樣的過程就構(gòu)成一個 多階段決策過程 。 動態(tài)規(guī)劃不僅求出了當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)值 ,而且同時求出了到中間狀態(tài)的最優(yōu)值。 顯然 ,用枚舉的方法從所有可能的決策序列中選取最優(yōu)決策序列是一種最笨的方法。 上節(jié) 下節(jié)最優(yōu)性原理 指出 , 過程的 最優(yōu)序列 有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。 如果求解問題的最優(yōu)性原理成立 , 則說明用動態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲得各階段間的遞推關(guān)系式。因此 , 從某種意義上說 動態(tài)規(guī)劃是一種找出子問題間遞推或遞歸關(guān)系的方法 。 動態(tài)規(guī)劃相比一般窮舉也存在一定 缺點 :空間占據(jù)過多 ,但對于空間需求量不大的題目來說 ,動態(tài)規(guī)劃無疑是最佳方法！ 上節(jié) 下節(jié)