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 ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。