《数据结构与算法分析》课件第10章

第10章“难”问题求解算法10.1概率算法10.2近似算法

10.1概率算法

概率算法的一个基本特征是对所求解问题的同一个实例用同一个概率算法求解两次，可能得到完全不同的结果。

(1)数值概率算法。

(2)舍伍德算法。

(3)拉斯维加斯算法。

(4)蒙特卡罗算法。10.1.1数值概率算法

数值概率算法实际上是在统计意义下求解问题的近似解。

1．用随机投点法计算π值

设有一个半径为r的圆及其外切正方形，如图10-1(a)所示。向该正方形随机地投入n个点，设落入圆内的点数为k。由于随机投入正方形的点服从均匀分布，因此所投入的点落入圆内的概率为πr2/4r2。当n足够大时，k/n→π/4，因此π=4k/n,由此可得到计算π值的概率算法。图10-1计算π值的示意图

2．用随机投点法计算定积分

设f(x)是[0，1]上的连续函数，且0≤f(x)≤1，计算

I=

f(x)dx的值。积分I的值等于图10-2中所示的面积G。在图10-2所示的单位正方形中均匀地做投点试验，则随机点落在曲线y=f(x)下方的概率为

假设向单位正方形内随机投入n个点(xi,yi)，i= 1,2,…,n，如果有m个点落入G内，则m/n近似地等于随机点落入G内的概率，即I=m/n。10.1.2舍伍德算法

在平均情况下分析算法的计算复杂度时，通常假设算法的输入数据服从某一个特定的概率分布。例如，快速排序算法中，假设输入数据服从均匀分布，其平均时间复杂度为O(nlbn)，那么在输入数据都完成排序后，这个时间就不再成立了。此时可采用舍伍德算法消除该算法所需计算时间与输入实例之间的这种联系。设A是一个确定性算法，当其输入实例为x时所需的计算时间为tA(x)。假设算法A的全体输入规模为n的实例的集合是XA，算法A所需的平均时间为

(10-1)

这显然不能排除存在x∈XA使得tA(x)远大于(n)的可能性。我们期望得到一个概率算法B，使得对问题的输入规模为n的每一个实例x∈XA均有tB(x)=

(n)+s(n)。对于某一个具体实例x∈XA，算法B偶尔需要的计算时间比(n)+s(n)多，这是由算法所作的概率选择引起的，与具体实例x无关。

定义算法B关于规模为n的随机实例的平均计算时间为

(10-2)

可知tB(n)=

(n)+s(n)，这就是舍伍德算法设计的基本思想。当s(n)与(n)相比可以忽略时，舍伍德算法可以获得很好的计算性能。10.1.3拉斯维加斯算法

舍伍德算法的优点是其计算时间复杂度对所有的实例而言是相对均匀的，但与其相对应的确定性算法相比，其平均时间复杂度没有改进。而拉斯维加斯算法能显著地改善算法的有效性，甚至对迄今为止找不到有效算法的某些问题也能得到满意的结果。下面考虑整数因子分解的拉斯维加斯算法。

设n是一个大于1的整数，关于整数n的因子分解问题是，找出n的如下形式的唯一分解式：

其中，p1＜p2＜…＜pk是k个素数；m1，m2，…，mk是k个整数。如果n是合数，则n必有一个非平凡因子x，1＜x＜n，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为因子分割问题。下面算法可实现整数的因子分割：下面讨论求整数n的因子分割的拉斯维加斯算法——Pollard算法，该算法用与Split算法相同的计算量就可以获得在1～x4范围内的因子分割。

Pollard算法开始时随机选取0～n-1范围内的一个整数x1，然后由式

(10-3)

递归产生无穷序列x1，x2，…，xk，…。对于i=2k，k=0,1,2,…，以及2k≤j≤2k+1，Pollard算法计算xj-xi与n的最大公因子为

d=gcd(xj-xi,n)

(10-4)

如果d是n的非平凡因子，则在实现对n的一次因子分割时，该算法输出n的因子d。10.1.4蒙特卡罗算法

在实际应用中常会遇到一些特殊的问题，即无论是采用确定性算法，还是概率算法都无法保证每次都能得到正确解。蒙特卡罗算法在一般情况下可以保证对问题的所有实例都可以高概率地给出正确解，但通常无法判断一个具体解是否正确。设p是一个实数，且＜p＜1。如果蒙特卡罗算法对于问题的任何一个实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p- 为该算法的优势。

如果对于同一个实例，蒙特卡罗算法不会给出两个不同的正确答案，则称蒙特卡罗算法是一致的。

对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只需执行算法若干次，并选择出现频次最高的解即可。下面讨论素数测试问题。费尔马小定理为素数判定提供了一个有力的工具。

费尔马小定理：如果p是素数，且0＜a＜p，则ap-1

1

(modp)。

利用费尔马小定理可以设计一个素数判定算法。对于一个给定的整数n，通过计算d=2n-1modn来判定整数n的素性：当d≠1时，n肯定不是素数；当d=1时，n可能是素数，也可能不是素数。为了提高素数测试的准确性，可以随机地选取整数a(1＜a＜n-1)，然后利用条件an-1

1(modn)来判定整数n的素性。但是，费尔马小定理是素数判定的必要条件，即满足费尔马小定理的整数n未必是素数。为此利用二次探测定理可对上述算法做进一步地改进。

二次探测定理：如果p是一个素数，0＜x＜p，则方程x2

1(modp)的解是x=1,p-1。

利用二次探测定理，在利用费尔马小定理计算an-1modn的过程中，增加对于整数n的二次探测，一旦发现其违背二次探测条件，即可得出n不是素数的结论。

10.2近似算法

许多“难”问题实质上是最优化问题，即要求使某个目标函数达到最大值或最小值的解。不失一般性，对于确定的问题，假设其每一个可行解所对应的目标函数值不小于一个确定的正数。

若一个最优化问题的最优解为s*，用近似算法求解该

问题得到的解为s，则该近似算法的性能比定义为

η = max。通常情况下，该性能比是问题输入规模n的函数ρ(n)，即η≥ρ(n)。根据定义可知：η≥1，当近似解等于最优解时，η=1；η越大，近似最优解就越差。

有时使用相对误差衡量近似算法的精确程度。近似算法的相对误差定义为

(10-5)若问题的输入规模为n，存在一个函数ε(n)使得λ≤ε(n)，则称ε(n)为该近似算法的相对误差界。函数

ε(n)与ρ(n)的关系为

ε(n)≤ρ(n)-110.2.1顶点覆盖问题的近似算法

设无向图G=(V,E)的顶点覆盖是V的一个子集，V'

V,满足：若(v,u)是G的一条边，则v

V'或u

V'。顶点覆盖的大小是它所包含的顶点个数|V'|。图10-3顶点覆盖问题的近似算法10.2.2旅行售货员问题的近似算法

旅行售货员问题可描述为给定一个完全无向网络G=(V,E)，其中每一条边(v,u)E有一个非负整数费用c(v,u)，要求找出G的最小费用哈密顿回路。

从实际应用中抽象出的旅行售货员问题常常具有一些特殊性质，如费用函数c往往具有三角不等式性质。当图G中的顶点是平面上的点时，任意两个顶点间的费用就是这两个顶点间的欧氏距离，故费用函数c具有三角不等式性质。下面介绍具有三角不等式性质的旅行售货员问题的近似算法。图10-4旅行售货员问题的近似算法由于图G是一个完全图，因此可知ApproxTSPTour算法的计算时间为O(|E|) = O(|V|2)。

若用H*表示图G的最小费用旅行售货员回路，H表示ApproxTSPTour算法的近似最优旅行售货员回路，则c(H)≤2c(H*)。

证明：设T是ApproxTSPTour算法计算得出的图G的最小生成树。从H*中任意删除一条边后，可得到图G的一棵生成树。由于T是最小生成树，故有

c(T)≤c(H*)

(10-6)对树T所做的一个完全遍历是在访问T的一个顶点时列出该顶点，而在结束对T的一棵子树的访问并沿途返回时也列出返回时经过的顶点。设W是T的前序完全遍历，即图10-4(b)的前序完全遍历为abcbdbaefgfhfea。由于对树T的前序完全遍历W经过T的每条边恰好两次，因此有

c(W)=2c(T)≤2c(H*)(10-7)然而W不是一个旅行售货员回路，它访问了G中某些顶点多次。由于费用函数满足三角不等式，因此在W中删除已经访问过的顶点不会增加旅行的费用。若在W中删除顶点u和顶点w间的一个顶点v，那么就用边(u,w)代替原来从u到w的一条路。反复使用该方法删除W中多次被访问的顶点后，可得到G的一条旅行售货员回路。在图10-4中，从W中删除重复访问顶点后得到的回路为H = abcdefgha，这就是ApproxTSPTour算法计算得出的近似最优哈密顿回路。由费用函数的三角不等式性质知

c(H)≤c(W)≤2c(H*)(10-8)

也就是说，算法ApproxTSPTour的性能比为2。10.2.3集合覆盖问题的近似算法

下面给出集合覆盖问题的一个实例。设<X,F>由一个有限集X和X的一个子集族F组成，子集族F覆盖了有限集X。也就是说，X中的任何一个元素至少属于F中的一个子集，即

S。对于F中的一个子集C

F，若C覆盖了