分治法
????基本思想
????將一個問題，分解為多個子問題，遞歸的去解決子問題，最終合并為問題的解
????適用情況
? ? 1. 問題分解為小問題后容易解決
? ? 2. 問題可以分解為小問題，即最優(yōu)子結構
? ? 3. 分解后的小問題解可以合并為原問題的解
? ? 4. 小問題之間互相獨立
????實例：? ? 二分查找，快速排序，合并排序，大整數(shù)乘法，循環(huán)賽日程表
動態(tài)劃分算法
????基本思想
????????將問題分解為多個子問題（階段），按順序求解，前一個問題的解為后一個問題提供信息
????適用情況
? ? ? ? 1. 最優(yōu)化原理：問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，即最優(yōu)子結構
? ? ? ? 2. 無后效性：某個狀態(tài)一旦確定，就不受以后決策的影響
? ? ? ? 3. 有重疊子問題
????????說明:? 遞推關系是從次小的問題開始到較大問題的轉化，往往可以用遞歸來實現(xiàn)，可以利用? ? ? ?之前產(chǎn)生的子問題的解來減少重復的計算
回溯法
????基本思想
????????選優(yōu)搜索法，走不通就退回重選，按照深度優(yōu)先搜索的策略，從根節(jié)點出發(fā)，深度搜索解空間
????步驟
? ? ? ? 1. 確定解空間
? ? ? ? 2. 確定節(jié)點的擴展搜索規(guī)則
? ? ? ? 3. 深度優(yōu)先方式搜索解空間，用剪枝法避免無效搜索
分支界限法
????基本思想
? ? ? ?與回溯法類似，也是在解空間里搜索解得算法，不同點是，回溯法尋找所有解，分支界限法搜索一個解或者最優(yōu)解
????????分支：廣度優(yōu)先策略或者最小耗費（最大效益）優(yōu)先
????????分支搜索方式：FIFO、LIFO、優(yōu)先隊列式、分支界限搜索算法
貪心算法
????基本思想
????????不從總體最優(yōu)考慮，僅考慮局部最優(yōu)解，問題必須具備后無效性
????步驟
? ? ? ? 1. 將問題分解為多個子問題
? ? ? ? 2. 得到問題的局部最優(yōu)解
? ? ? ? 3. 合并子問題的局部最優(yōu)解
? ? ? ?適用情況
????????局部最優(yōu)策略能導致全局最優(yōu)解
????????子問題后無效性
