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