策略是面向問(wèn)題的，算法是面向?qū)崿F(xiàn)的。
一、不同算法策略特點(diǎn)小結(jié)
1、貪心策略
??? 貪心策略一方面是求解過(guò)程比較簡(jiǎn)單的算法，另一方面它又是對(duì)能適用問(wèn)題的條件要求最嚴(yán)格（即適用范圍很?。┑乃惴ā?/p>
??? 貪心策略解決問(wèn)題是按一定順序，在只考慮當(dāng)前局部信息的情況下，就做出一定的決策，最終得出問(wèn)題的解。
即：通過(guò)局部最優(yōu)決策能得到全局最優(yōu)決策
2、遞推策略
?? 遞推也是由當(dāng)前問(wèn)題的逐步解決從而得到整個(gè)問(wèn)題的解，依賴于信息間本身的遞推關(guān)系，每一步不需要決策參與到算法中，更多用于計(jì)算
3、遞歸策略
?? 遞歸常常用于分治算法、動(dòng)態(tài)規(guī)劃算法中。
?? 遞歸是利用大問(wèn)題與其子問(wèn)題間的遞推關(guān)系來(lái)解決問(wèn)題的。
?? 能采用遞歸策略的算法一般有以下特征：
?? （1）為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解方便地構(gòu)造出大問(wèn)題的解
?? （2）并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成更小的問(wèn)題，并從這些更小的問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解
?? （3）特別的，當(dāng)規(guī)模N = 1時(shí)，能直接得解
4、枚舉策略
??? 對(duì)問(wèn)題所有的解逐一嘗試，從而找出問(wèn)題的真正解。一般用于決策類問(wèn)題，很難找到大、小規(guī)模之間的關(guān)系，也不易對(duì)問(wèn)題進(jìn)行分解。
5、遞歸回溯策略
??? 類似于枚舉，通過(guò)嘗試遍歷問(wèn)題各個(gè)可能解的通路，當(dāng)發(fā)現(xiàn)此路不通時(shí)，回溯到上一步繼續(xù)嘗試別的通路。
6、分治策略
?? 分治一般用于較復(fù)雜的問(wèn)題，必須可以逐步被分解為容易解決的獨(dú)立的子問(wèn)題，這些子問(wèn)題解決后，進(jìn)而將它們的解“合成”，就得到較大問(wèn)題的解，最終合成為總問(wèn)題的解。
7、動(dòng)態(tài)規(guī)劃策略
??? 與貪心類似，也是通過(guò)多階段決策過(guò)程來(lái)解決問(wèn)題。每個(gè)階段決策的結(jié)果是一個(gè)決策結(jié)果序列，這個(gè)結(jié)果序列中，最終哪一個(gè)是最優(yōu)的結(jié)果，取決于以后每個(gè)階段的決策，當(dāng)然每次決策結(jié)果序列都必須進(jìn)行存儲(chǔ)。因此是“高效率，高消費(fèi)的算法”。
???? 同時(shí)，它又與遞歸法類似，當(dāng)問(wèn)題不能分解為獨(dú)立的階段，卻又符合最優(yōu)化原理時(shí)，就可以使用動(dòng)態(tài)規(guī)劃法，通過(guò)遞歸決策過(guò)程，逐步找出子問(wèn)題的最優(yōu)解，從而決策出問(wèn)題的解。
二、算法策略間的關(guān)系
1、對(duì)問(wèn)題進(jìn)行分解的算法策略——分治法與動(dòng)態(tài)規(guī)劃法
?? 共同點(diǎn)：（1）分治法與動(dòng)態(tài)規(guī)劃法實(shí)際上都是遞歸思想的運(yùn)用
???????????? （2）二者的根本策略都是對(duì)問(wèn)題進(jìn)行分解，找到大規(guī)模與小規(guī)模的關(guān)系，然后通過(guò)解小規(guī)模的解，得出大規(guī)模的解
?? 不同點(diǎn)： 適用于分治法的問(wèn)題分解成子問(wèn)題后，各子問(wèn)題間無(wú)公共子子問(wèn)題，而動(dòng)態(tài)規(guī)劃法相反。
????????????? 動(dòng)態(tài)規(guī)劃法 = 分治算法思想 + 解決子問(wèn)題間的冗余情況
2、多階段逐步解決問(wèn)題的策略——貪心算法、遞推法、遞歸法和動(dòng)態(tài)規(guī)劃法
???? 貪心算法：每一步都根據(jù)策略得到一個(gè)結(jié)果，并傳遞到下一步，自頂向下，一步一步地做出貪心決策。
???? 動(dòng)態(tài)規(guī)劃算法：每一步?jīng)Q策得到的不是一個(gè)唯一結(jié)果，而是一組中間結(jié)果（且這些結(jié)果在以后各步可能得到多次引用），只是每一步都使問(wèn)題的規(guī)模逐步縮小，最終得到問(wèn)題的一個(gè)結(jié)果。
???? 遞推、遞歸法：注重每一步之間的關(guān)系，決策的因素較少。遞推法是根據(jù)關(guān)系從前向后推導(dǎo)，從小規(guī)模問(wèn)題的結(jié)論推解出大問(wèn)題的解。而遞歸法是根據(jù)關(guān)系從后向前使大問(wèn)題轉(zhuǎn)化為小問(wèn)題，最后同樣由小規(guī)模問(wèn)題的解推解出大問(wèn)題的解。
3、全面逐一嘗試、比較——蠻力法、枚舉法、遞歸回溯法
???? 蠻力策略（即枚舉和遞歸回溯）：
???? 當(dāng)問(wèn)題找不到信息間的相互關(guān)系、也不能將問(wèn)題分解為獨(dú)立的子問(wèn)題，就只有把全部解都列出來(lái)之后，才能判定和推斷出問(wèn)題的解。
???? 蠻力策略適用于規(guī)模不大的問(wèn)題。
???? （1）枚舉法：實(shí)現(xiàn)依賴于循環(huán)。所以一個(gè)枚舉法只針對(duì)一個(gè)特定問(wèn)題規(guī)模的情況，例如：八重循環(huán)嵌套解八皇后問(wèn)題的算法。
???? （2）遞歸回溯法：適用于任意指定規(guī)模的情況，例如：遞歸回溯法解N皇后問(wèn)題。
4、算法策略的中心思想
?? 用算法策略將解決問(wèn)題的過(guò)程歸結(jié)為：用算法的基本工具“循環(huán)機(jī)制和遞歸機(jī)制”實(shí)現(xiàn)。
三、算法策略側(cè)重的問(wèn)題類型
??? 一般常遇到的問(wèn)題分為四類：
??? （1）判定性問(wèn)題：可用遞推法、遞歸法
??? （2）計(jì)算問(wèn)題：可用遞推法、遞歸法
??? （3）最優(yōu)化問(wèn)題：貪心算法、分治法、動(dòng)態(tài)規(guī)劃法、枚舉法
??? （4）構(gòu)造性問(wèn)題：貪心算法、分治法、廣度優(yōu)先搜索、深度優(yōu)先搜索
