文档介绍：第二章分治法(Divide and Conquer) ——“分”而治之
一般方法
对大规模问题的求解
利用分治法求解大规模问题

当问题的规模较大而无法直接求解时,将整个问题分成若干个小问题,然后分而治之。
可用递归过程描述。
一般情况下,子问题与原始问题“同质”
分治策略的抽象化控制
procedure DANDC(p,q)
global (1:n);
integer m,p,q; //1≤p≤q≤n//
if SMALL(p,q)
then return(G(p,q))
else
m←DIVIDE(p,q) //p≤m<q//
BINE(DANDC(p,m),
DANDC(m+1,q)))
endif
end DANDC
注:
k=2: 二分是最常用的分解策略;
SMALL(p,q):布尔函数,判断输入规模q-p+1是否足够小而无需再进一步分就可求解;
G(p,q): 当SMALL(p,q)为真时,对输入规模为q-p+1的子问题求解;
DIVIDE():当规模q-p+1还较大时,对规模为q-p+1的子问题进一步分解,返回值为[p,q]区间进一步的分割点;
COMBINE(x,y):子结果的合并函数,将区间[p,m]和[m+1,q]上的子问题的解合并成区间[p,q]上的“较完整”的解。当p=1,q=n时,就得到整个问题的解。
2. 分治策略的抽象化控制过程
DANDC的计算时间
若所分成的两个子问题的规模大致相等,则DANDC总的计算时间可用递归关系式表示如下:
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则

注:
T(n):表示输入规模为n的DANDC计算时间
g(n):表示对足够小的输入规模直接求解的计算时间
f(n):BINE对两个子区间的子结果进行合并
的时间
(该公式针对具体问题有各种不同的变形)
二分检索(折半查找)
1. 问题的描述
已知一个按非降次序排列的元素表a1, a2, …,an,判定某给定的元素x是否在该表中出现。
若是,则找出x在表中的位置并返回其所在位置
的下标
若非,则返回0值。
问题的形式描述:
I=(n, a1, a2, …,an,x)
问题分解:选取下标k,由此将I分解为3个子问题:
I1=(k-1, a1, a2, …,ak-1,x)
I2=(1, ak,x)
I3=(n-k, ak+1, a2, …,an,x)
对于I2,若ak=x,则有解k,对I1、I3不用再求解;否则,
若x<ak,则只在I1中求解,对I3不用求解;
若x>ak,则只在I3中求解,对I1不用求解;
对I1 、I3的求解可再次采用分治方法求解——递归求解
过程
2. 二分检索二分检索:每次选取中间元素的下标
二分检索
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low←1; high←n;
while low≤high do
mid ←
case
:x<A(mid):high←mid-1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
注:
给定一个按非降次序排列的元素数组A(1:n),n≥1,判断x是否出现。
若是,置j,使得x=A(j)
若非,j=0
:设A(1:9)=(-15,-6,0,7,9,23,54,82,101)
在A中检索x=101,-14,82。执行轨迹见下表1
表1 运行轨迹示例
x=101
x=-14
x=82
low
high
mid
low
high
mid
low
high
mid
1
9
5
1
9
5
1
9
5
6
9
7
1
4
2
6
9
7
8
9
8
1
1
1
8
9
8
9
9
9
2
1
找不到
找到
找到
成功的检索
不成功的检索
成功的检索
过程BINSRCH(A,n,x,j)能正确运行
证明:
1)在具体指定A中的数据元素及x的数据类型后,算法中的所有运算都
能按要求正确运行——即首先满足确定性和能行性
2)终止性
算法初始部分置low←1, high←n
①若n=0,不进入循环,j置0,算法终止
②否则,进入循环,计算mid,
或 x=A(mid),j置为mid,算法终止;
或x<A(mid),置high←mid-1,搜索范围实