分治算法

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的问题所需的计算时间，则有：

通常可以用展开递归式的方法来解这类递归方程，反复带入求解得