发信人: Lerry (戒网·学习), 信区: Algorithm
标 题: 分治策略
发信站: 哈工大紫丁香 (2001年11月20日21:17:22 星期二), 站内信件
分治策略
相关知识： 一维数组 | 多维数组 | 栈 | 队列 | 串 | 回溯
一、算法思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小
，解题所需的计算时间往往也越少，从而也越容易计算。想解决一个较大的问题，有时
是相当困难的。分治法的思想就是，将一个难以直接解决的大问题，分割成一些规模较
小的相同问题，以便各个击破，分而治之。
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题
互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。
1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的
：
解决子问题所需的工作总量（由 子问题的个数、解决每个子问题的工作量 决定）
合并所有子问题所需的工作量
2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法
3、分治的具体过程：
begin ｛开始｝
if ①问题不可分 then ②返回问题解
else begin
③从原问题中划出含一半运算对象的子问题1；
④递归调用分治法过程，求出解1；
⑤从原问题中划出含另一半运算对象的子问题2；
⑥递归调用分治法过程，求出解2；
⑦将解1、解2组合成整修问题的解；
end;
end; {结束}
二、例题分析
1、[金块问题]老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的
雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最
轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
分析:问题可以简化为：在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小
元。
明显的方法是逐个的进行比较查找。
（一次冒泡排序）
m:=a[1];
for i:=2 to n do
if m < a[i] then m:=a[i];
(或者一次选择排序)
p:=1;
for i:=2 to n do
if a[p]<a[i] then p:=i;
m:=a[p];
需要n-1次比较得到max，而再经过n-2次比较得到min，共进行2*n-3次比较可以找出极大
元和极小元。
用分治法可以较少比较次数地解决上述问题：
如果集合中只有1个元素，则它既是最大值也是最小值；
如果有2个元素，则一次maxnum(i,j) 一次minnum(i,j)就可以得到最大值和最小值
；
如果把集合分成两个子集合，递归的应用这个算法分别求出两个子集合的最大值和
最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子
集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。
可得解题思想：
｛maxmin｝
①if 问题不可分：n=2
②问题的解求得（两个元素时）：对两元素进行比较;return;
③for i:=1 to n div 2 do b[i]:=a[i]
④maxmin(n div 2,b,max1,min1)，其中max1和min1为解1
⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2]
⑥maxmin(n div 2,b,max2,min2)，其中max2和min2为解2
⑦max:=maxnum(max1,max2);
min:=minnum(min1,min2);
{maxmin}
其中对函数maxnum的求精：
function maxnum(a,b:integer):integer;
begin
if a>b then maxnum:=a else maxnum:=b;
end;
分析比较次数：
比较运算均在函数maxnum和minnum中进行，
当n=2时，比较次数T(n)=1
当n>2时，比较次数T(n)=2T(n/2)+2
∵n是2的k次幂
∴设n=2^k
2、快速排序
快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序：
（1）分解(Divide) 以元素a[p]为基准元素将a[p：q-1]划分为三段a[p：q-1]，a[q]和
a[q+1：r]，使得a[p：q-1]中任何一个元素都小于a[q]，a[q+1：r]中任何一个元素大于
等于a[q]，下标q在划分中确定。
（2）递归求解(Conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行
排序。
（3）合并(Merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的，所以不必进
行任何合并操作就已经排好序了。
在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参
见排序算法----快速排序
3、归并排序
归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组
合并为一个。(源程序)
２－路归并排序示例：
初始值 E Y U K S L B
一趟归并排序 E Y K U L S B
两趟归并排序 E K U Y B L S
三趟归并排序 B E K L S U Y
习题:对数字49 38 40 97 76 13 27进行归并排序
procedure mergesort(var r,r1:listtype;s,t:integer);
{r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进
行归并排序、并存放到链表r1中，其中s是下界t是上界}
{过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r
1中}
if 问题不可分 then
求解
if s=t then
r1[s]:=r[s]
else else
（1）分出问题的一个子问题1，并求解子问题1 mergesort(r,r2,s,(s+t)div 2);
（2）分出问题的一个子问题2，求解子问题2 mergesort(r,r2,(s+t)div 2,t);
（3）合并子问题1和子问题2 merge(r2,s,(s+t)div 2,t,r1);
4、[循环赛问题]（1999年广东省青少年信息学奥林匹克竞赛 第三题：棒球联赛）
问题描述：广州市体委将举行一次由N支队伍（队伍编号为1..N）参加的少年棒球联赛。
联赛总共不能多于N轮（同一时间内若干支队进行一次比赛为一轮），并且每两支队之间
必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。
循环赛问题可以用分治法解决。下面是先假定n=2^k
procedure table(k:integer;a:array[1..u1,1..u2] of integer);
var n,i,j,m,s,t:integer;
begin
n:=1;
for i:=1 to k do n:=n*2;
for i:=1 to n do a[1,i]:=i;
m:=1;
for s:=1 to k do
begin
n:=n / 2;
for t:=1 to n do
for i:=m+1 to 2*m do
for j:=m+1 to 2*m do
begin
a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];
a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];
end;
m:=m*2;
end;{for s}
end;
三、练习题
[二分检索]假定在A[1..9]中顺序存放这九个数：-7,-2,0,5,16,43,57,102,291 要求检
索291,16,101是否在数组中。
给定已排好序的n个元素A1,A2,A3,…，An, 找出元素x是否在A中，如果x在A中，指
出它在A中的位置。
--
不在乎天长地久，就怕你从来没有！
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]