分治演算法

1. 郵局選址的分治演算法，C++語言

郵局選址問題

􀂐問題描述：
在一個按照東西和南北方向劃分成規整街區的城市裡，n個居民點散亂地分布在不同的街區中。用x坐標表示東西向，用y坐標表示南北向。各居民點的位置可以由坐標(x,y)表示。街區中任意2點(x1,y1)和(x2,y2)之間的距離可以用數值|x1-x2|+|y1-y2|度量。
居民們希望在城市中選擇建立郵局的最佳位置，使n個居民點到郵局的距離總和最小。

􀂐編程任務：
給定n個居民點的位置,編程計算n個居民點到郵局的距離總和的最小值。

􀂐數據輸入：
由文件input.txt提供輸入數據。文件的第1行是居民點數n，1≤n≤10000。接下來n行是居民點的位置，每行2個整數x和y，-10000≤x，y≤10000。

􀂐結果輸出:
程序運行結束時，將計算結果輸出到文件output.txt中。文件的第1行中的數是n個居民點到郵局的距離總和的最小值。

輸入文件示例
5
1 2
2 2
1 3
3 -2
3 3

輸出文件示例
10

解法：
http://blog.csdn.net/lyflower/archive/2008/03/07/2156943.aspx
//- By CQ.Xiao @ SCAU
//- Nov.9th 2007

#include "iostream"
using namespace std;

struct info{
unsigned dis; //最小值
unsigned r; //標號r之前（包括r）的村莊為一個轄區
};

//-- Definition for Global-Variable
unsigned village = 0, postoffice = 0; //number of village & postoffice
unsigned *xCoordinate = NULL; //x coordinate of each village
unsigned **center = NULL, **dis = NULL; //point for Center(l,r) & Dis(l,r)
info **totalDis = NULL; //point for TotalDis(t,k)

//-- Function Declare
void input();
void calculateCenter();
void calculateDis();
void calculateTotalDis();
void output(unsigned t, unsigned k);
void setFree();

int main(){
input();
calculateCenter();
calculateDis();
calculateTotalDis();
output(0, postoffice);
setFree();
return 0;
}

void input(){
//--- Input
cin >> village >> postoffice;
xCoordinate = new unsigned [village];
for (unsigned i = 0; i < village; i++)
cin >> xCoordinate[i];
//--- Sort
int t = 0;
for (i = 0; i < village - 1; i++)
for (int j = 0; j < village - 1 - i; j++)
if (xCoordinate[j] > xCoordinate[j+1]){
t = xCoordinate[j];
xCoordinate[j] = xCoordinate[j+1];
xCoordinate[j+1] = t;
}
}

void calculateCenter(){
//--- 內存分配
center = new unsigned *[village]; //動態分配二維數組的第一維
for (unsigned i=0; i<village; i++) //動態分配二維數組的第二維
center[i] = new unsigned[village];

//--- 初始化Center(l,r)
for (unsigned l = 0; l < village; l++)
for (unsigned r = l; r < village; r++)
center[l][r] = xCoordinate[(r-l)/2 + l];
}

void calculateDis(){
//--- 內存分配
dis = new unsigned *[village]; //動態分配二維數組的第一維
for (unsigned i = 0; i < village; i++) //動態分配二維數組的第二維
dis[i] = new unsigned[village];

//--- 初始化Dis(l,r)
for (unsigned l = 0; l < village; l++)
for (unsigned r = l; r < village; r++){
dis[l][r] = 0;
for (unsigned k = l; k <= r; k++)
if (center[l][r] > xCoordinate[k])
dis[l][r] += center[l][r] - xCoordinate[k]; //計算unsigned時不要得出負數
else
dis[l][r] += xCoordinate[k]- center[l][r];
}
}

void calculateTotalDis(){
//--- 內存分配
totalDis = new info *[village]; //動態分配二維數組的第一維
for (unsigned i = 0; i < village; i++) //動態分配二維數組的第二維
totalDis[i] = new info[postoffice+1];

//--- 計算TotalDis(v,p+1)
//---- 當k=1時，根據公式(1.2)，直接計算
for (unsigned t = 0; t < village; t++)
totalDis[t][1].dis = dis[t][village-1];
//---- 當k=2,3,...,p時的情況
for (unsigned k = 2; k <= postoffice; k++)
for (unsigned t = 0; t < village; t++){
totalDis[t][k].dis = (unsigned)(-1);
totalDis[t][k].r = 0;
for (unsigned r = t; r <= village-k; r++){
unsigned temp = dis[t][r] + totalDis[r+1][k-1].dis;
//---- 計算最小值
if (temp < totalDis[t][k].dis){
totalDis[t][k].dis = temp;
totalDis[t][k].r = r;
}
}
}
}

void output(unsigned t, unsigned k){
if (1 == k)
cout << center[t][village-1];
else{
cout << center[t][totalDis[t][k].r] << ' ';
output(totalDis[t][k].r+1, k-1);
}
}

void setFree(){
//--釋放動態分配的內存
for (unsigned i = 0; i < village; i++){
delete []center[i];
delete []dis[i];
delete []totalDis[i];
}
delete []center;
delete []dis;
delete []totalDis;
}

2. 分治演算法的基本思想

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

3. 什麼是分治演算法貪婪演算法

貪婪演算法

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

分治演算法

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

4. c++分治演算法

你這題很巧，你用二分法遞歸排序，最後會只剩下兩個相鄰的元素，而不會重疊指向一個元素，所以high - low == 0這一句始終不成立，造成死循環。加以個條件就好了

#include<iostream>
using namespace std;
//要先寫 第一個元素的值為0的排除子函數，沒寫。
int arrange(int a[],int low,int high)
{
int flag=0;
int mid =(low+high)/2;

if((high-low)==0 || (high - low) == 1) //二分法排序的最後兩種可能
{
if(a[mid]==mid)
return a[mid];
else
return 0;
}

int left;
int right;
left=arrange(a,low,mid); //向左
right=arrange(a,mid,high); //向右
if(left||right) //整合，有一個非0就是找到值了
return left+right;
else
return 0;
}
int main()
{
int a[]={-8,-5,-2,-1,2,5,8,10,18,21};
int result;
result=arrange(a,1,10);
cout<<result << endl;
return 0;
}

5. 分治演算法的應用實例

下面通過實例加以說明： 給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的，並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一台可用來比較兩組硬幣重量的儀器，利用這台儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個硬幣輕一些，則尋找偽幣的任務完成。假如兩硬幣重量相等，則繼續比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在並找出這一偽幣。
另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。這樣，就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣。可以利用儀器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，並且可以判斷它位於較輕的那一組硬幣中。最後，在第三步中，用第二步的結果得出原先1 6個硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這1 6個硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。
假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣，那麼不能判斷出它是否就是偽幣。在一個小問題中，通過將一個硬幣分別與其他兩個硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則演算法終止。否則，繼續劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組，因此再把它分成兩組，每組有4個硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由於這個組只有兩個硬幣，因此不必再細分。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。 在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中，用直接比較法求出。演算法如下：
void maxmin1(int A[],int n,int *max,int *min)
{ int i;
*min=*max=A[0];
for(i=0;i <= n;i++)
{ if(A[i]> *max) *max= A[i];
if(A[i] < *min) *min= A[i];
}
}
上面這個演算法需比較2(n-1)次。能否找到更好的演算法呢？我們用分治策略來討論。
把n個元素分成兩組：
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
分別求這兩組的最大值和最小值，然後分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多於兩個，則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。
例如有下面一組元素：-13，13，9，-5，7，23，0，15。用分治策略比較的演算法如下：
void maxmin2(int A[],int i,int j,int *max,int *min)
/*A存放輸入的數據，i，j存放數據的范圍，初值為0，n-1，*max,*min 存放最大和最小值*/
{ int mid,max1,max2,min1,min2;
if (j==i) {最大和最小值為同一個數;return;}
if (j-1==i) {將兩個數直接比較，求得最大會最小值；return；}
mid=(i+j)/2;
求i~mid之間的最大最小值分別為max1，min1;
求mid+1~j之間的最大最小值分別為max2，min2;
比較max1和max2，大的就是最大值;
比較min1和min2，小的就是最小值;
} 題目：在一個(2^k)*(2^k)個方格組成的棋盤上，有一個特殊方格與其他方格不同，稱為特殊方格，稱這樣的棋盤為一個特殊棋盤。我們要求對棋盤的其餘部分用L型方塊填滿（註：L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角，方向隨意），且任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下：
題目的解法使用分治法，即子問題和整體問題具有相同的形式。我們對棋盤做一個分割，切割一次後的棋盤如圖1所示，我們可以看到棋盤被切成4個一樣大小的子棋盤，特殊方塊必定位於四個子棋盤中的一個。假設如圖1所示，特殊方格位於右上角，我們把一個L型方塊（灰色填充）放到圖中位置。這樣對於每個子棋盤又各有一個「特殊方塊」，我們對每個子棋盤繼續這樣分割，直到子棋盤的大小為1為止。
用到的L型方塊需要（4^k-1)/3 個，演算法的時間是O（4^k)，是漸進最優解法。
本題目的C語言的完整代碼如下（TC2.0下調試），運行時，先輸入k的大小，(1<=k<=6)，然後分別輸入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。 #include<stdio.h>//#include<conio.h>//#include<math.h>inttitle=1;intboard[64][64];voidchessBoard(inttr,inttc,intdr,intdc,intsize){ints,t;if(size==1)return;t=title++;s=size/2;if(dr<tr+s&&dc<tc+s)chessBoard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidmain(){intdr=0,dc=0,s=1,i=0,j=0;printf(printinthesizeofchess: );scanf(%d,&s);printf(printinspecalpointx,y: );scanf(%d%d,&dr,&dc);if(dr<s&&dc<s){chessBoard(0,0,dr,dc,s);for(i=0;i<s;i++){for(j=0;j<s;j++){printf(%4d,board[i][j]);}printf( );}}elseprintf(thewrongspecalpoint!! );getch();}

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

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

7. 分治演算法的解題步驟

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

8. 分治演算法和動態規劃有什麼不同和聯系

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

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

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

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

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

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

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

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

9. 分治演算法常用什麼技術實現

分治法
分治法採用了遞歸的結構，將原問題分成幾個規模較小但是類似於原問題的子問題， 通過遞歸的方式再來求解這些小問題，然後將子問題的解合並來建立原問題的解，分治法在每成遞歸時都有三個步驟：
分解: 將原問題分解成若干個小問題，這些子問題是原問題的規模較小的實例
解決: 解決這些子問題，通過遞歸的方式求解子問題，直到自問題的規模足夠小，可以直接求解
合並: 將這些子問題的解合並成原問題的解
最大子序列和問題是典型的可以用分治演算法求解的模型

10. 分治演算法時間復雜度

一：分治演算法和遞歸
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的問題所需的計算時間，則有：

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