分支演算法

Ⅰ 分治演算法時間復雜度

一：分治演算法和遞歸
1.簡述遞歸

我們要講到分治演算法，我覺得有必要說一下遞歸，他們就像一對孿生兄弟，經常同時應用在演算法設計中，並由此產生許多高效的演算法。
直接或間接的調用自身的演算法稱為遞歸演算法。用函數自身給出定義的函數稱為遞歸函數。

int fibonacci(int n){
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
先簡單看一下經典的遞歸例子，博主會找個時間系統詳細的總結一下關於遞歸的內容。

2.簡述分治

分治法的設計思想是：

分–將問題分解為規模更小的子問題；
治–將這些規模更小的子問題逐個擊破；
合–將已解決的子問題合並，最終得出「母」問題的解；
一個先自頂向下，再自底向上的過程。

凡治眾如治寡，分數是也。—孫子兵法

3.分治法與遞歸的聯系

由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

二：分治法的適用條件
分治法所能解決的問題一般具有以下幾個特徵：

1) 該問題的規模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
3) 利用該問題分解出的子問題的解可以合並為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

第一條特徵是絕大多數問題都可以滿足的，因為問題的復雜性一般是隨著問題規模的增加而增加；

第二條特徵是應用分治法的前提它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；、

第三條是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。

第四條特徵涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好

三：分治法的基本步驟
分解問題：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；（自頂向下）
這里涉及到一個平衡子問題的思想：人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。

解決問題：如果問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題，以得到小問題的解。
合並結果：將各個子問題的解合並為原問題的解：（自底向上）。
它的一般演算法設計模式如下：
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //（2）解決問題：遞歸到小問題，則解決小規模的問題（自頂向下）
divide P into smaller subinstances P1,P2,...,Pk；//（1）分解問題
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //利用遞歸的解各子問題
return merge(y1,...,yk); //將各子問題的解合並為原問題的解（自底向上）
}
四：分治法的復雜性分析
從分治法的一般設計模式可以看出，用他設計出的程序一般是遞歸演算法。因此分治法的計算效率通常可以用遞歸方程來進行分析。
一個分治法將規模為n的問題分成k個規模為n/m的子問題去解。設分解閥值（表示當問題P規模不超過n0時，問題已容易解出，不必再繼續分解）n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合並為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

通常可以用展開遞歸式的方法來解這類遞歸方程，反復帶入求解得

Ⅱ 分治演算法和動態規劃的區別和聯系

一、分治法與動態規劃主要共同點：

1）二者都要求原問題具有最優子結構性質，都是將原問題分而治之，分解成若干個規模較小(小到很容易解決的程序)的子問題。然後將子問題的解合並，形成原問題的解。

二、分治法與動態規劃實現方法：

① 分治法通常利用遞歸求解。

② 動態規劃通常利用迭代法自底向上求解，但也能用具有記憶功能的遞歸法自頂向下求解。

三、分治法與動態規劃主要區別：

① 分治法將分解後的子問題看成相互獨立的。

② 動態規劃將分解後的子問題理解為相互間有聯系，有重疊部分。

Ⅲ 分治演算法的基本思想

當我們求解某些問題時，由於這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對於這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。

Ⅳ 什麼是分治演算法

分治法就是將一個復雜的問題分成多個相對簡單的獨立問題進行求解，並且綜合所有簡單問題的解可以組成這個復雜問題的解。
例如快速排序演算法就是一個分治法的例子。即將一個大的無序序列排序成有序序列，等於將兩個無序的子序列排序成有序，且兩個子序列之間滿足一個序列的元素普遍大於另一個序列中的元素。

Ⅳ 如何理解分治演算法及相關例題

演算法步驟：
1 ：從左上角起，給棋盤編號（1，1），（1，2）（8，8），計為集合qp。tracks記錄走過的每個點. （可以想像為坐標（x,y））

2：設起點為（1，1），記為 當前位置 cp，

3：搜索所有可走的下一步，根據「馬行日」的走步規則，可行的點的坐標是x坐標加減1，y坐標加減2，

或是x加減2，y加減1； （例如起點（1，1），可計算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8個點）， 如果沒有搜到可行點，程序結束。

4：判斷計算出的點是否在棋盤內，即是否在集合qp中；判斷點是否已經走過，即是否在集合tracts中，不在才是合法的點。（在上面的舉例起點（1，1），則合法的下一步是（2，3）和 （3，2））

5：將前一步的位置記錄到集合tracts中，即tracts.add（cp）；選擇一個可行點，cp=所選擇點的坐標。

6：如果tracts里的點個數等於63，退出程序，否則回到步驟3繼續執行。

Ⅵ 分治演算法

演算法步驟：
1 ：從左上角起，給棋盤編號（1，1），（1，2），。。。。。。（8，8），計為集合qp。tracks記錄走過的每個點. （可以想像為坐標（x,y））

2：設起點為（1，1），記為 當前位置 cp，

3：搜索所有可走的下一步，根據「馬行日」的走步規則，可行的點的坐標是x坐標加減1，y坐標加減2，

或是x加減2，y加減1； （例如起點（1，1），可計算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8個點）， 如果沒有搜到可行點，程序結束。

4：判斷計算出的點是否在棋盤內，即是否在集合qp中；判斷點是否已經走過，即是否在集合tracts中，不在才是合法的點。（在上面的舉例起點（1，1），則合法的下一步是（2，3）和 （3，2））

5：將前一步的位置記錄到集合tracts中，即tracts.add（cp）；選擇一個可行點，cp=所選擇點的坐標。

6：如果tracts里的點個數等於63，退出程序，否則回到步驟3繼續執行。

Ⅶ 簡述分治法的基本思想

http://hi..com/foying/blog/item/b8ad2401bd77ad097bec2cf0.html

Ⅷ 什麼是分治演算法貪婪演算法

貪婪演算法

雖然設計一個好的求解演算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用於解決許多問題的演算法設計方法，你可以使用這些方法來設計演算法，並觀察這些演算法是如何工作的。一般情況下，為了獲得較好的性能，必須對演算法進行細致的調整。但是在某些情況下，演算法經過調整之後性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。

分治演算法

就是把大問題分解成一些小問題，然後重小問題構造出大問題的解。

Ⅸ 分治演算法的解題步驟

分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

Ⅹ 簡述貪心，遞歸，動態規劃，及分治演算法之間的區別和聯系

遞歸，簡單的重復，計算量大。
分治，解決問題獨立，分開計算，如其名。
動態規劃演算法通常以自底向上的方式解各子問題，
貪心演算法則通常以自頂向下的方式進行；
動態規劃能求出問題的最優解，貪心不能保證求出問題的最優解