貪心算法-分治算法-動态規劃-回溯-分支限界的簡單介紹

1.1 貪心算法

在求解過程中，總是做出在目前看來最好的選擇，有可能陷入局部最優。

1.2 分治算法

将一個難以解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

1.3動态規劃

将待求解的問題分解為若幹子問題（階段），按順序求解子階段，前一個子問題的解，為後一個子問題的求解提供了必要的資訊。

與分治算法的主要差別是：經分解後得到的子問題往往不是互相獨立的。

1.4 回溯

在包含問題的所有解的解空間樹中，按照深度優秀搜尋的政策，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。

1.5 分支限界

采用廣度優先的政策，在問題的解空間樹T上搜尋問題的解。與回溯差別：回溯法的求解目标是找出T中滿足限制條件的所有解，而分支限界法的求解目标則是找出滿足限制條件的一個解，或是在滿足限制條件的解中找出使某一個目标函數值達到極大或極小的解，即在某種意義下的最優解。