1.1基礎算法分析類型

1.1.1 分治法

核心思想：分而治之

原理：先將一個復雜的問題拆解為兩個或多個相同的子問題，然后將子問題依然進行分治法處理，直到子問題已經可以直接求解，最終按照問題的拆解順序，從子問題開始逐步將問題合并為一個大問題，層層向上，最后得到改實際問題的解。在算法領域通常是越是規(guī)模小的問題越容易求解，分治法也是充分利用此優(yōu)勢發(fā)揮其價值。

可解決問題的類型：

（1）待求解的問題是可以拆分為若干相同或相似的子問題，子問題之間相互獨立。

（2）該問題可以在小規(guī)模情況下成立，并得到解。

（3）問題被拆分后的子問題的解之間可以進行合并。

解決問題的步驟：

一、分解問題；

二、解決子問題；

三、合并解，得到原始問題的解。

分治法常采用遞歸的方式進行求解，原因是遞歸可以有效地將問題拆解為相似且更小的子問題，并且子問題之間相互獨立，互不干擾。例如：二分查找、歸并排序等。

缺點：利用分治法時，子問題之間存在重復子問題，則可能影響分治法的計算效率，這是因為相同的問題在不同的子問題中均被求解。此時，可考慮利用動態(tài)規(guī)劃的方式對問題進行求解。

1.1.2 動態(tài)規(guī)劃法

動態(tài)規(guī)劃是一種將原問題拆解為若干相對簡單子問題的求解方法，常常用于重疊子問題和最優(yōu)子結構性能的問題。通過動態(tài)規(guī)劃的方法，計算量則遠遠小于一般的解法。原因在于對于重疊子問題，一般情況下會被重復計算，而動態(tài)規(guī)劃則是將重復計算簡化問計算一次據(jù)放入到結果表中，在下一次計算時則從結果表中查詢，從而直接獲得結果，因此使性能得到提升。

動態(tài)規(guī)劃的方法是一個從初始狀態(tài)開始計算結果，后續(xù)的計算都依賴于前一個計算結果的狀態(tài)，最終獲得解的過程。

主要步驟：

（1）劃分問題；

（2）確定狀態(tài)和狀態(tài)變量；

（3）確定狀態(tài)轉移過程；

（4）尋找終止條件。

1.1.3 回溯法

回溯法是一種不斷嘗試獲得問題解的方法，嘗試的過程是一種不斷枚舉的過程。

回溯法在所有的解空間中，按照深度優(yōu)先嘗試的原則，從初始狀態(tài)不斷深入到各個解空間中，解決過程如下：

（1）對需要解決的問題，確定問題的解空間，確保在解空間的范圍內存在最優(yōu)解。

（2）確定回溯法的嘗試規(guī)則及尋找的方式，以減少不必要的計算。

1.1.4 分支限界法

分支限界法是通過廣度優(yōu)先或者最小代價優(yōu)先的方式嘗試性解決問題。其搜索策略是先通過在路徑選擇處，生成其所有的下一步分支，計算每一個分支的某個條件限定值，這些條件限定值即為分支的界限，然后從這些分支中選擇某個的分支作為下一個節(jié)點，使問題的搜索路徑向著最優(yōu)解的分支進行，此處選擇分支的方式主要有兩種：

（1）FIFO（First In First Out）：先進先出；

（2）最小代價。

分支界限法的核心思想：需要確定某個分支的上下界，一遍搜索一邊移除某些不滿足條件的分支，以提升問題解決得效率。

1.1.5 貪心法

”貪心“是指當前求解的過程在當前的條件下是最好的選擇，并未從整體上觸發(fā)考慮，屬于局部最優(yōu)解。改方法沒有一定固定的解題框架，重點在于貪心法的貪心策略。

貪心算法并不是一定會使所有問題得到全局最優(yōu)的解，因此貪心算法適用于通過局部最優(yōu)解可以獲得全局最優(yōu)解的問題。

基本思路：

（1）通過數(shù)學模型描述問題；

（2）將原始問題拆解為若干子問題，并對每個問題求解，獲得每個子問題的局部最優(yōu)解；

（3）將每個子問題的局部最優(yōu)解進行合并，獲得對整個問題的全局最優(yōu)解。

對若干個子問題的局部最優(yōu)合并后的解是否是全局最優(yōu)解的問題，需要通過實際問題進行分析，如果子問題之間相互獨立，不相互影響，則通過合并基本上都屬于全局最優(yōu)解。