属于分治算法

⑴ 分治法的步骤

分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
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;
}

⑵ 每天一个知识点：分治算法：选择问题

选择问题的要求是找出含有 N 个元素的表 S 中的第 k 个最小的元素。

基本的算法是简单的递归策略。设 N 大于截止点(cutoff point)，在截止点后元素将进行简单的排序，v 是选出的一个元素，叫做枢纽元(pivot)。其余的元素被放在两个集合 和 中。 含有那些不大于 v 的元素，而 则包含那些不小于 v 的元素。

为了得到一个线性算法，必须保证子问题只是原问题的一部分，而不仅仅只是比原问题少几个元素。这里要解决问题就是如何花费更少的时间来寻找枢纽元。

为得到一个好的最坏情形，关键想法是再用一个间接层。不是从随机元素的样本中找出中项，而是从中项的样本中找出中项。

基本的枢纽元选择算法如下：

上面给出的枢纽元选择法，有一个专业的术语，叫做“五分化中项的中项”。“五分化中项的中项”保证每个递归子问题的大小最多是原问题的大约 70%。对于整个选择算法，枢纽元可以足够快的算出，以确保 的运行时间。

定理：使用“五分化中项的中项”的快速选择算法的运行时间为 。

分治算法还可以用来降低算法预计所需要的比较次数。

设有 N 个数的集合 S 并且要寻找其中第 k 个最小的数 X。我们选择 S 的子集 S‘，令 δ 是某个数，使得计算过程所用的平均比较次数最小化。

找出 S’ 中第 ( ) 个和第 个最小的元素，几乎可以肯定 S 中的第 k 个元素将落在 和 之间，此时，问题变成了 2δ 个元素的选择问题。

经过分析，会发现，若 和 ，则期望的比较次数为 ，除低次项外它是最优的。（如果 k>N/2，那么我们可以考虑查找第(N-k)个最大元素的对称问题。）

最后一项代表进行两次选择以确定 和 的代价。假设采用合理聪明的策略，则划分的平均代价等于 N 加上 在 S 中的期望阶(expected rank)，即 。如果第 k 个元素在 S‘ 中出现，那么代价就是 O(N)。然而，s 和 δ 已经被选取以保证这种情况以非常低的概率 o(1/N) 发生，因此该可能性的期望代价是 o(1)，当它的 N 越来越大时趋向于 0。

这个分析指出，找出中项平均大约需要 1.5N 次比较。当然，该算法为计算 s 需要浮点运算，这在一些机器上可能使该算法减慢速度。不过即使是这样，若能正确实现，则该算法完全能够比得上快速选择实现方法。

⑶ 如何理解分治算法及相关例题

算法步骤：
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继续执行。

⑷ 分治算法求数组中最大元素位置的算法：

实质就是递归，思想是分治
max1=Max(a, low, mid);
max2=Max(a, mid+1, high);
以上把代码就是把数组分成两部分，然后这两部分中再往下分，直至if(low==high)
时返回下标，然后在每一层进行比较max=a[max1]>a[max2]?max1: max2; 把最大值的下标赋给max。
最后返回。

⑸ 分治法是什么

分治法可以通俗的解释为:把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治法的精髓：

分--将问题分解为规模更小的子问题。

治--将这些规模更小的子问题逐个击破。

合--将已解决的子问题合并，最终得出"母"问题的解。

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。

n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。

而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

⑹ 分治算法

算法步骤：
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、该问题的规模缩小到一定的程度就可以容易的解决。

2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3、利用该问题分解出的子问题的解可以合并为该问题的解。

4、该问题所分解出的自问题是相互独立的，即子问题之间不包含子子问题。

(7)属于分治算法扩展阅读

思想及策略

分治算法的设计思想是：将一个难以直接解决的大问题，分割成一些规模小的相同的问题，一边各个击破，分而治之。

分治算法的策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如规模n比较小）则直接解决，否则将其分解成k个规模较小的自问题，这些子问题相互独立且与元问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

⑻ 选择排序，插入排序和归并排序算数法中，什么算法是分治算法

归并排序 用到了 分治 的思想

⑼ 分治算法是什么呢

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

解题步骤

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

⑽ 什么是分治算法贪婪算法

贪婪算法

虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。

分治算法

就是把大问题分解成一些小问题，然后重小问题构造出大问题的解。