4分治演算法

『壹』 分治的設計步驟

1. 劃分步：把輸入的問題劃分為k個子問題，並盡量使這k個子問題的規模大致相同。
2. 治理步：當問題的規模大於某個預定的閾值n0時，治理步由k個遞歸調用組成。
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繼續執行。

『叄』 如何理解分治演算法及相關例題

演算法步驟：
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繼續執行。

『肆』 分治法的步驟

分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合並：將各個子問題的解合並為原問題的解。
它的一般的演算法設計模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 將P分解為較小的子問題 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
6. T ← MERGE(y1,y2,...,yk) △ 合並子問題
7. return(T)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子演算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時直接用演算法ADHOC(P)求解。演算法MERGE(y1,y2,...,yk)是該分治法中的合並子演算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合並為P的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？
各個子問題的規模應該怎樣才為適當？
答: 但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
出處：網路
實踐題目：
給定一個順序表，編寫一個求出其最大值和最小值的分治演算法。
分析：
由於順序表的結構沒有給出，作為演示分治法這里從簡順序表取一整形數組數組大小由用戶定義，數據隨機生成。我們知道如果數組大小為 1 則可以直接給出結果，如果大小為 2則一次比較即可得出結果，於是我們找到求解該問題的子問題即: 數組大小 <= 2。到此我們就可以進行分治運算了，只要求解的問題數組長度比 2 大就繼續分治，否則求解子問題的解並更新全局解
以下是代碼。
*/
/*** 編譯環境TC ***/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define M 40
/* 分治法獲取最優解 */
void PartionGet(int s,int e,int *meter,int *max,int *min){
/* 參數:
* s 當前分治段的開始下標
* e 當前分治段的結束下標
* meter 表的地址
* max 存儲當前搜索到的最大值
* min 存儲當前搜索到的最小值
*/
int i;
if(e-s <= 1){ /* 獲取局部解，並更新全局解 */
if(meter[s] > meter[e]){
if(meter[s] > *max)
*max = meter[s];
if(meter[e] < *min)
*min = meter[e];
}
else{
if(meter[e] > *max)
*max = meter[e];
if(meter[s] < *min)
*min = meter[s];
}
return ;
}
i = s + (e-s)/2; /* 不是子問題繼續分治,這里使用了二分，也可以是其它 */
PartionGet(s,i,meter,max,min);
PartionGet(i+1,e,meter,max,min);
}
int main(){
int i,meter[M];
int max = INT_MIN; /* 用最小值初始化 */
int min = INT_MAX; /* 用最大值初始化 */
printf(The array's element as followed: );
rand(); /* 初始化隨機數發生器 */
for(i = 0; i < M; i ++){ /* 隨機數據填充數組 */
meter[i] = rand()%10000;
if(!((i+1)%10)) /* 輸出表的隨機數據 */
printf(%-6d ,meter[i]);
else
printf(%-6d,meter[i]);
}
PartionGet(0,M - 1,meter,&max,&min); /* 分治法獲取最值 */
printf( Max : %d Min : %d ,max,min);
system(pause);
return 0;
}

『伍』 分治法指的是什麼呢

分治法指的是將原問題遞歸地分成若干個子問題，直到子問題滿足邊界條件，停止遞歸，將子問題逐個解決（一般是同種方法），將已經解決的子問題合並，最後，演算法會層層合並得到原問題的答案。

分治演算法步驟：

分：遞歸地將問題分解為各個的子問題（性質相同的，相互獨立的子問題）。

治：將這些規模更小的子問題逐個擊破。

合：將已解決的問題逐層合並，最終得出原問題的解。

分治法適用條件

1、問題的規模縮小到一定的規模就可以較容易地解決。

2、問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。

3、合並問題分解出的子問題的解可以得到問題的解。

4、問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

『陸』 分治演算法的小問題

A是排好序的嗎？？
應該是吧，不然還要分治演算法干什麼……
時間復雜度O（logn）
如n=16,樸素演算法16次，分治演算法4次

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

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

『捌』 分治策略的分治策略的定義

這種演算法設計策略叫做分治法。 如果原問題可分割成k個子問題，1<k≤n ，且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。 分治法所能解決的問題一般具有以下幾個特徵：
該問題的規模縮小到一定的程度就可以容易地解決；
該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
利用該問題分解出的子問題的解可以合並為該問題的解；
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特徵是應用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。