[推荐]常用算法集

风花雪月

可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。

假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。

假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。

上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。

例2-5 考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，.。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。当这两个排好序的序列被归并后，即可得所需要的排序序列。

图2 - 6给出了分而治之排序算法的伪代码。算法中子集合的数目为2，A中含有n/k个元素。

template

void sort( T E, int n)

{ / /对E中的n 个元素进行排序， k为全局变量

if (n >= k) {

i = n/k;

j = n-i;

令A 包含E中的前i 个元素

令B 包含E中余下的j 个元素

s o r t ( A , i ) ;

s o r t ( B , j ) ;

m e rge(A,B,E,i,j,); //把A 和B 合并到E

}

else 使用插入排序算法对E 进行排序

}

图14-6 分而治之排序算法的伪代码



从对归并过程的简略描述中，可以明显地看出归并n个元素所需要的时间为O (n)。设t (n)为分而治之排序算法（如图1 4 - 6所示）在最坏情况下所需花费的时间，则有以下递推公式：

其中c 和d 为常数。当n / k≈n-n / k 时，t (n) 的值最小。因此当k= 2时，也就是说，当两个子集合所包含的元素个数近似相等时， t (n) 最小，即当所划分的子集合大小接近时，分而治之算法通常具有最佳性能。

可以用迭代方法来计算这一递推方式，结果为t(n)= (nl o gn)。虽然这个结果是在n为2的幂时得到的，但对于所有的n，这一结果也是有效的，因为t(n) 是n 的非递减函数。t(n) =(nl o gn) 给出了归并排序的最好和最坏情况下的复杂性。由于最好和最坏情况下的复杂性是一样的，因此归并排序的平均复杂性为t (n)= (nl o gn)。

图2 - 6中k= 2的排序方法被称为归并排序（ m e rge sort ），或更精确地说是二路归并排序（two-way merge sort）。下面根据图1 4 - 6中k= 2的情况（归并排序）来编写对n 个元素进行排序的C + +函数。一种最简单的方法就是将元素存储在链表中（即作为类c h a i n的成员（程序3 -8））。在这种情况下，通过移到第n/ 2个节点并打断此链，可将E分成两个大致相等的链表。

归并过程应能将两个已排序的链表归并在一起。如果希望把所得到C + +程序与堆排序和插入排序进行性能比较，那么就不能使用链表来实现归并排序，因为后两种排序方法中都没有使用链表。为了能与前面讨论过的排序函数作比较，归并排序函数必须用一个数组a来存储元素集合E，并在a 中返回排序后的元素序列。为此按照下述过程来对图1 4 - 6的伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对a 中的初始序列进行排序，并将所得到的排序序列归并到一个新数组b中，最后将它们复制到a 中。图1 4 - 6的改进版见图1 4 - 7。



template

M e rgeSort( T a[], int left, int right)

{ / /对a [ l e f t : r i g h t ]中的元素进行排序

if (left < right) {//至少两个元素

int i = (left + right)/2; //中心位置

M e rgeSort(a, left, i);

M e rgeSort(a, i+1, right);

M e rge(a, b, left, i, right); //从a 合并到b

Copy(b, a, left, right); //结果放回a

}

}

图14-7 分而治之排序算法的改进



可以从很多方面来改进图1 4 - 7的性能，例如，可以容易地消除递归。如果仔细地检查图1 4 - 7中的程序，就会发现其中的递归只是简单地重复分割元素序列，直到序列的长度变成1为止。当序列的长度变为1时即可进行归并操作，这个过程可以用n 为2的幂来很好地描述。长度为1的序列被归并为长度为2的有序序列；长度为2的序列接着被归并为长度为4的有序序列；这个过程不断地重复直到归并为长度为n 的序列。图1 4 - 8给出n= 8时的归并（和复制）过程，方括号表示一个已排序序列的首和尾。



初始序列[8] [4] [5] [6] [2] [1] [7] [3]

归并到b [4 8] [5 6] [1 2] [3 7]

复制到a [4 8] [5 6] [1 2] [3 7]

归并到b [4 5 6 8] [1 2 3 7]

复制到a [4 5 6 8] [1 2 3 7]

归并到b [1 2 3 4 5 6 7 8]

复制到a [1 2 3 4 5 6 7 8]

图14-8 归并排序的例子



另一种二路归并排序算法是这样的：首先将每两个相邻的大小为1的子序列归并，然后对上一次归并所得到的大小为2的子序列进行相邻归并，如此反复，直至最后归并到一个序列，归并过程完成。通过轮流地将元素从a 归并到b 并从b 归并到a，可以虚拟地消除复制过程。二路归并排序算法见程序1 4 - 3。

程序14-3 二路归并排序

template

void MergeSort(T a[], int n)

{// 使用归并排序算法对a[0:n-1] 进行排序

T *b = new T [n];

int s = 1; // 段的大小

while (s < n) {

MergePass(a, b, s, n); // 从a归并到b

s += s;

MergePass(b, a, s, n); // 从b 归并到a

s += s;

}

}

为了完成排序代码，首先需要完成函数M e rg e P a s s。函数M e rg e P a s s（见程序1 4 - 4）仅用来确定欲归并子序列的左端和右端，实际的归并工作由函数M e rg e (见程序1 4 - 5 )来完成。函数M e rg e要求针对类型T定义一个操作符< =。如果需要排序的数据类型是用户自定义类型，则必须重载操作符< =。这种设计方法允许我们按元素的任一个域进行排序。重载操作符< =的目的是用来比较需要排序的域。

程序14-4 MergePass函数

template

void MergePass(T x[], T y[], int s, int n)

{// 归并大小为s的相邻段

int i = 0;

while (i <= n - 2 * s) {

// 归并两个大小为s的相邻段

Merge(x, y, i, i+s-1, i+2*s-1);

i = i + 2 * s;

}

// 剩下不足2个元素

if (i + s < n) Merge(x, y, i, i+s-1, n-1);

else for (int j = i; j <= n-1; j++)

// 把最后一段复制到y

y[j] = x[j];

}

程序14-5 Merge函数

template

void Merge(T c[], T d[], int l, int m, int r)

{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .

int i = l, // 第一段的游标

j = m+1, // 第二段的游标

k = l; // 结果的游标

/ /只要在段中存在i和j，则不断进行归并

while ((i <= m) && (j <= r))

if (c <= c[j]) d[k++] = c[i++];

else d[k++] = c[j++];

// 考虑余下的部分

if (i > m) for (int q = j; q <= r; q++)

d[k++] = c[q];

else for (int q = i; q <= m; q++)

d[k++] = c[q];

}

自然归并排序（natural merge sort）是基本归并排序（见程序1 4 - 3）的一种变化。它首先对输入序列中已经存在的有序子序列进行归并。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，这些子序列是按从左至右的顺序对元素表进行扫描而产生的，若位置i 的元素比位置i+ 1的元素大，则从位置i 进行分割。对于上面这个元素序列，可找到四个子序列，子序列1和子序列2归并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4归并可得[ 1 , 2 , 5 , 6 ]，最后，归并这两个子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，对于上述元素序列，仅仅使用了两趟归并，而程序1 4 - 3从大小为1的子序列开始，需使用三趟归并。作为一个极端的例子，假设输入的元素序列已经排好序并有n个元素，自然归并排序法将准确地识别该序列不必进行归并排序，但程序1 4 - 3仍需要进行[ l o g2 n] 趟归并。因此自然归并排序将在(n) 的时间内完成排序。而程序1 4 - 3将花费(n l o gn) 的时间。

[ 本帖最后由 风花雪月 于 2006-10-10 01:02 编辑 ]

风花雪月

分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。


/ /使用快速排序方法对a[ 0 :n- 1 ]排序

从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点

把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点

递归地使用快速排序方法对left 进行排序

递归地使用快速排序方法对right 进行排序

所得结果为l e f t + m i d d l e + r i g h t

图14-9 快速排序的伪代码


考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。

把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。

程序14-6 快速排序

template

void QuickSort(T*a, int n)

{// 对a[0:n-1] 进行快速排序

{// 要求a[n] 必需有最大关键值

quickSort(a, 0, n-1);

template

void quickSort(T a[], int l, int r)

{// 排序a [ l : r ]， a[r+1] 有大值

if (l >= r) return;

int i = l, // 从左至右的游标

j = r + 1; // 从右到左的游标

T pivot = a[l];

// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换

while (true) {

do {// 在左侧寻找>= pivot 的元素

i = i + 1;

} while (a < pivot);

do {// 在右侧寻找<= pivot 的元素

j = j - 1;

} while (a[j] > pivot);

if (i >= j) break; // 未发现交换对象

Swap(a, a[j]);

}

// 设置p i v o t

a[l] = a[j];

a[j] = pivot;

quickSort(a, l, j-1); // 对左段排序

quickSort(a, j+1, r); // 对右段排序

}

若把程序1 4 - 6中d o - w h i l e条件内的<号和>号分别修改为< =和> =，程序1 4 - 6仍然正确。实验结果表明使用程序1 4 - 6的快速排序代码可以得到比较好的平均性能。为了消除程序中的递归，必须引入堆栈。不过，消除最后一个递归调用不须使用堆栈。消除递归调用的工作留作练习（练习1 3）。程序1 4 - 6所需要的递归栈空间为O (n)。若使用堆栈来模拟递归，则可以把这个空间减少为O ( l o gn)。在模拟过程中，首先对left 和right 中较小者进行排序，把较大者的边界放入堆栈中。在最坏情况下l e f t总是为空，快速排序所需的计算时间为(n2 )。在最好情况下， l e f t和r i g h t中的元素数目大致相同，快速排序的复杂性为(nl o gn)。令人吃惊的是，快速排序的平均复杂性也是(nl o gn)。

定理2-1 快速排序的平均复杂性为(nl o gn)。

证明用t (n) 代表对含有n 个元素的数组进行排序的平均时间。当n≤1时，t (n)≤d，d为某一常数。当n <1时，用s 表示左段所含元素的个数。由于在中段中有一个支点元素，因此右段中元素的个数为n-s- 1。所以左段和右段的平均排序时间分别为t (s), t (n-s- 1 )。分割数组中元素所需要的时间用cn 表示，其中c 是一个常数。因为s 有同等机会取0 ~n- 1中的任何一个值.

如对（2 - 8）式中的n 使用归纳法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8为自然对数的基底。在归纳开始时首先验证n= 2时公式的正确性。根据公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在归纳假设部分，假定t(n)≤kn l o ge n（当2≤n＜m 时，m 是任意一个比2大的整数＝.

图1 4 - 1 0对本书中所讨论的算法在平均条件下和最坏条件下的复杂性进行了比较。


方法最坏复杂性平均复杂性

冒泡排序n2 n2

计数排序n2 n2

插入排序n2 n2

选择排序n2 n2

堆排序nl o gn nl o gn

归并排序nl o gn nl o gn

快速排序n2 nl o gn

图14-10 各种排序算法的比较


中值快速排序（ median-of-three quick sort）是程序1 4 - 6的一种变化，这种算法有更好的平均性能。注意到在程序1 4 - 6中总是选择a [ 1 ]做为支点，而在这种快速排序算法中，可以不必使用a [ 1 ]做为支点，而是取{a[1],a[(1+r)/2],a[r]} 中大小居中的那个元素作为支点。例如，假如有三个元素，大小分别为5，9，7，那么取7为支点。为了实现中值快速排序算法，一种最简单的方式就是首先选出中值元素并与a[1] 进行交换，然后利用程序1 4 - 6完成排序。如果a [ r ]是被选出的中值元素，那么将a[1] 与a[r] 进行交换，然后将a [ 1 ]（即原来的a [ r ]）赋值给程序1 4 - 6中的变量p i v o t，之后继续执行程序1 4 - 6中的其余代码。

图2 - 11中分别给出了根据实验所得到的归并排序、堆排序、插入排序、快速排序的平均时间。对于每一个不同的n, 都随机产生了至少1 0 0组整数。随机整数的产生是通过反复调用s t d l i b . h库中的r a n d o m函数来实现的。如果对一组整数进行排序的时间少于1 0个时钟滴答，则继续对其他组整数进行排序，直到所用的时间不低于1 0个时钟滴答。在图2 - 11中的数据包含产生随机整数的时间。对于每一个n，在各种排序法中用于产生随机整数及其他开销的时间是相同的。因此，图2 - 11中的数据对于比较各种排序算法是很有用的。

对于足够大的n，快速排序算法要比其他算法效率更高。从图中可以看到快速排序曲线与插入排序曲线的交点横坐标比2 0略小，可通过实验来确定这个交点横坐标的精确值。可以分别用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9进行实验，以寻找精确的交点。令精确的交点横坐标为nBr e a k。当n≤nBreak 时，插入排序的平均性能最佳。当n＞nBreak 时，快速排序性能最佳。当n＞nBreak 时，把插入排序与快速排序组合为一个排序函数，可以提高快速排序的性能，实现方法是把程序1 4 - 6中的以下语句：

if(l >= r)r e t u r n ;

替换为

if (r-1
这里I n s e r t i o n S o r t ( a , l , r )用来对a [ 1 : r ]进行插入排序。测量修改后的快速排序算法的性能留作练习（练习2 0）。用更小的值替换n B r e a k有可能使性能进一步提高（见练习2 0）。

大多数实验表明，当n＞c时（c为某一常数），在最坏情况下归并排序的性能也是最佳的。而当n≤c时，在最坏情况下插入排序的性能最佳。通过将插入排序与归并排序混合使用，可以提高归并排序的性能

[ 本帖最后由 风花雪月 于 2006-10-10 01:02 编辑 ]

风花雪月

对于给定的n 个元素的数组a [ 0 : n - 1 ]，要求从中找出第k小的元素。当a [ 0 : n - 1 ]被排序时，该元素就是a [ k - 1 ]。假设n = 8，每个元素有两个域k e y和I D，其中k e y是一个整数，I D是一个字符。假设这8个元素为[ ( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后得到数组[ ( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h) ]。如果k = 1，返回I D为g 的元素；如果k = 8，返回I D为h 的元素；如果k = 6，返回是I D为f 的元素；如果k = 2，返回I D为d 的元素。实际上，对最后一种情况，所得到的结果可能不唯一，因为排序过程中既可能将I D为d 的元素排在a [ 1 ]，也可能将I D为b 的元素排在a [ 1 ]，原因是它们具有相同大小的k e y，因而两个元素中的任何一个都有可能被返回。但是无论如何，如果一个元素在k = 2时被返回，另一个就必须在k = 3时被返回。

选择问题的一个应用就是寻找中值元素，此时k = [n / 2 ]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量。其他k值也是有用的。例如，通过寻找第n / 4 , n / 2和3 n / 4这三个元素,可将人口划分为4份。

选择问题可在O ( n l o g n )时间内解决，方法是首先对这n个元素进行排序（如使用堆排序式或归并排序），然后取出a [ k - 1 ]中的元素。若使用快速排序（如图1 4 - 11所示），可以获得更好的平均性能，尽管该算法有一个比较差的渐近复杂性O( n2 )。

可以通过修写程序1 4 - 6来解决选择问题。如果在执行两个w h i l e循环后支点元素a [ l ]被交换到a [ j ] ,那么a [ l ]是a [ l : j ]中的第j - l + 1个元素。如果要寻找的第k 个元素在a [ l : r ]中，并且j - l + 1等于k，则答案就是a [ l ]；如果j - l + 1 < k，那么寻找的元素是r i g h t中的第k - j + l - 1个元素，否则要寻找的元素是left 中的第k个元素。因此，只需进行0次或1次递归调用。新代码见程序1 4 - 7。S e l e c t中的递归调用可用f o r或w h i l e循环来替代（练习2 5）。

程序14-7 寻找第k 个元素

template

T Select(T a[], int n, int k)

{// 返回a [ 0 : n - 1 ]中第k小的元素

// 假定a[n] 是一个伪最大元素

if (k < 1 || k > n) throw OutOfBounds();

return select(a, 0, n-1, k);

}

template

T select(T a[], int l, int r, int k)

{// 在a [ l : r ]中选择第k小的元素

if (l >= r) return a[l];

int i = l, // 从左至右的游标

j = r + 1; // 从右到左的游标

T pivot = a[l];

// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换

while (true) {

do {// 在左侧寻找>= pivot 的元素

i = i + 1;

} while (a < pivot);

do {// 在右侧寻找<= pivot 的元素

j = j - 1;

} while (a[j] > pivot);

if (i >= j) break; // 未发现交换对象

Swap(a, a[j]);

}

if (j - l + 1 == k) return pivot;

// 设置p i v o t

a[l] = a[j];

a[j] = pivot;

// 对一个段进行递归调用

if (j - l + 1 < k)

return select(a, j+1, r, k-j+l-1);

else return select(a, l, j-1, k);

}

程序1 4 - 7在最坏情况下的复杂性是( n2 )，此时left 总是为空，而且第k个元素总是位于r i g h t.

如果假定n 是2的幂，则可以取消公式（2 - 1 0）中的向下取整操作符。通过使用迭代方法，可以得到t (n) = (n)。若仔细地选择支点元素，则最坏情况下的时间开销也可以变成(n)。一种选择支点元素的方法是使用“中间的中间（ m e d i a n - o f - m e d i a n）”规则，该规则首先将数组a中的n 个元素分成n/r 组，r 为某一整常数，除了最后一组外，每组都有r 个元素。然后通过在每组中对r 个元素进行排序来寻找每组中位于中间位置的元素。最后根据所得到的n/r 个中间元素，递归使用选择算法，求得所需要的支点元素。

例2-6 [中间的中间] 考察如下情形：r=5, n=27, 并且a= [ 2，6，8，1，4，1 0，2 0，6，2 2，11，9，8，4，3，7，8，1 6，11，1 0，8，2，1 4，1 5，1，1 2，5，4 ]。这2 7个元素可以被分为6组[ 2 , 6 , 8 , 1 , 4 ]，[ 1 0 , 2 0 , 6 , 2 2 , 11 ]，[ 9 , 8 , 4 , 3 , 7 ]，[ 8 , 1 6 , 11 , 1 0 , 8 ]，[ 2 , 1 4 , 1 5 , 1 , 1 2 ]和[ 5 , 4 ]，每组的中间元素分别为4 , 11 , 7 , 1 0 , 1 2和4。[ 4 , 11 , 7 , 1 0 , 1 2 , 4 ]的中间元素为7。这个中间元素7被取为支点元素。由此可以得到l e ft= [ 2 , 6 , 1 , 4 , 6 , 4 , 3 , 2 , 1 , 5 , 4 ]，m i d d l e= [ 7 ] ,r i g h t= [ 8 , 1 0 , 2 0 , 2 2 , 11 , 9 , 8 , 8 , 1 6 , 11 , 1 0 , 8 , 1 4 , 1 5 , 1 2 ]。

如果要寻找第k个元素且k< 1 2，则仅仅需要在l e f t中寻找；如果k= 1 2，则要找的元素就是支点元素；如果k> 1 2，则需要检查r i g h t中的1 5个元素。在最后一种情况下，需在r i g h t中寻找第(k- 1 2 )个元素。

定理2-2 当按“中间的中间”规则选取支点元素时，以下结论为真：

1) 若r=9, 那么当n≥9 0时，有m a x { |l e f e|, |r i g h t| }≤7n / 8。

2) 若r= 5，且a 中所有元素都不同，那么当n≥2 4时，有max{| left |, | right | }≤3n/ 4。

证明这个定理的证明留作练习2 3。

根据定理2 - 2和程序1 4 - 7可知，如果采用“中间的中间”规则并取r= 9，则用于寻找第k个元素的时间t (n)可按如下递归公式来计算：

在上述递归公式中，假设当n＜9 0时使用复杂性为nl o gn的求解算法，当n≥9 0时，采用“中间的中间”规则进行分而治之求解。利用归纳法可以证明，当n≥1时有t (n)≤7 2cn (练习2 4 )。

当元素互不相同时，可以使用r= 5来得到线性时间性能。

[ 本帖最后由 风花雪月 于 2006-10-10 01:03 编辑 ]

风花雪月

给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。

例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。

通过检查所有的n(n- 1 ) / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解，而对于大的问题则首先把它划分为两个较小的问题，其中一个问题（称为A）的大小为「n /2ù，另一个问题（称为B）的大小为「n /2ù。初始时，最近的点对可能属于如下三种情形之一： 1) 两点都在A中（即最近的点对落在A中）；2) 两点都在B中；3) 一点在A，一点在B。假定根据这三种情况来确定最近点对，则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解，而在第二种情况下可对B进行递归求解。


if (n较小) {用直接法寻找最近点对

R e t u r n ; }

// n较大

将点集分成大致相等的两个部分A和B

确定A和B中的最近点对

确定一点在A中、另一点在B中的最近点对

从上面得到的三对点中，找出距离最小的一对点

图14-13 寻找最近的点对


为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。

例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1，垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A，右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上，可将其中两个加入A, 另一个加入B，以便A、B中包含相同的点数。假设d ,m加入A，g加入B。

设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于，这样，就可以淘汰那些距垂线距离≥ 的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线，宽为2 。边界线及其以外的点均被淘汰掉，只有阴影中的点被保留下来，以便确定是否存在第三类点对（对应于第三种情况）其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q)，p?A, q?B且p, q 的距离小于，则p?RA，q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点，p的y 坐标为p.y，那么只需检查RB 中满足p.y- ＜q.y＜p.y+ 的q 点，看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此，只需将RB 中位于×2 阴影内的点逐个与p 配对，以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p 的比较区（comparing region）。

例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h)，其距离约为0 . 3 1 6。B中最近点对为(f, j)，其距离为0 . 3，因此= 0 . 3。当考察是否存在第三类点时，除d, g, i, l, m 以外的点均被淘汰，因为它们距分割线x= 1的距离≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比较区中没有点，只需考察i即可。i 的比较区中仅含点l。计算i 和l的距离，发现它小于，因此(i, l) 是最近的点对。

为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。

1. 选择数据结构

为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。

每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。

程序14-8 点类

class Point1 {

friend float dist(const Point1&, const Point1&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&,float&);

friend void main();

p u b l i c :

int operator<=(Point1 a) const

{return (x <= a.x);}

p r i v a t e :

int ID; // 点的编号

float x, y; // 点坐标

} ;

class Point2 {

friend float dist(const Point2&, const Point2&);

friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);

friend bool closest(Point1 *, int, Point1&, Point1&, float&);

friend void main();

p u b l i c :

int operator<=(Point2 a) const

{return (y <= a.y);}

p r i v a t e :

int p; // 数组X中相同点的索引

float x, y; // 点坐标

} ;

所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序，在分割过程中如果当前考察的点是X [l :r]，那么首先计算m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计算出A和B中的最近点对之后，还需要计算RA 和RB，然后确定是否存在更近的点对，其中一点属于RA，另一点属于RB。如果点已按y 坐标排序，那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操作符＜＝。成员p 用于指向X中的对应点。

确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数d i s t (见程序1 4 - 9 )来计算点a, b 之间的距离。T可能是P o i n t 1或P o i n t 2，因此d i s t必须是P o i n t 1和P o i n t 2类的友元。

程序14-9 计算两点距离

template

inline float dist(const T& u, const T& v)

{ / /计算点u 和v之间的距离

float dx = u.x-v. x ;

float dy = u.y-v. y ;

return sqrt(dx * dx + dy * dy);

}

如果点的数目少于两个，则函数c l o s e s t (见程序1 4 - 1 0 )返回f a l s e，如果成功时函数返回t r u e。当函数成功时，在参数a 和b 中返回距离最近的两个点，在参数d 中返回距离。代码首先验证至少存在两点，然后使用M e rg e S o r t函数(见程序14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标进行排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p给出了点i 在X中的位置。上述准备工作做完以后，调用函数close (见程序1 4 - 11 )，该函数实际求解最近点对。

程序14-10 预处理及调用c l o s e

bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)

{// 在n >= 2 个点中寻找最近点对

// 如果少于2个点，则返回f a l s e

// 否则，在a 和b中返回距离最近的两个点

if (n < 2) return false;

// 按x坐标排序

M e r g e S o r t ( X , n ) ;

// 创建一个按y坐标排序的点数组

Point2 *Y = new Point2 [n];

for (int i = 0; i < n; i++) {

// 将点i 从X 复制到Y

Y.p = i;

Y.x = X.x;

Y.y = X.y;

}

M e r g e S o r t ( Y,n); // 按y坐标排序

// 创建临时数组

Point2 *Z = new Point2 [n];

// 寻找最近点对

c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;

// 删除数组并返回

delete [] Y;

delete [] Z;

return true;

}

程序1 4 - 11 计算最近点对

void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)

{//X[l:r] 按x坐标排序

//Y[l:r] 按y坐标排序

if (r-l == 1) {// 两个点

a = X[l];

b = X[r];

d = dist(X[l], X[r]);

r e t u r n ; }

if (r-l == 2) {// 三个点

// 计算所有点对之间的距离

float d1 = dist(X[l], X[l+1]);

float d2 = dist(X[l+1], X[r]);

float d3 = dist(X[l], X[r]);

// 寻找最近点对

if (d1 <= d2 && d1 <= d3) {

a = X[l];

b = X[l+1];

d = d1;

r e t u r n ; }

if (d2 <= d3) {a = X[l+1];

b = X[r];

d = d2;}

else {a = X[l];

b = X[r];

d = d3;}

r e t u r n ; }

/ /多于三个点，划分为两部分

int m = (l+r)/2; // X[l:m] 在A中，余下的在B中

// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表

int f = l, // Z[l:m]的游标

g = m+1; // Z[m+1:r]的游标

for (int i = l; i <= r; i++)

if (Y.p > m) Z[g++] = Y;

else Z[f++] = Y;

// 对以上两个部分进行求解

c l o s e ( X , Z , Y, l , m , a , b , d ) ;

float dr;

Point1 ar, br;

c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;

// (a,b) 是两者中较近的点对

if (dr < d) {a = ar;

b = br;

d = dr;}

M e r g e ( Z , Y,l,m,r);// 重构Y

/ /距离小于d的点放入Z

int k = l; // Z的游标

for (i = l; i <= r; i++)

if (fabs(Y[m].x - Y.x) < d) Z[k++] = Y;

// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对

for (i = l; i < k; i++){

for (int j = i+1; j < k && Z[j].y - Z.y < d;

j + + ) {

float dp = dist(Z, Z[j]);

if (dp < d) {// 较近的点对

d = dp;

a = X[Z.p];

b = X[Z[j].p];}

}

}

}

函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。

首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以创建分别与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的角色互相交换，依次执行两个递归调用来获取A和B中的最近点对。在两次递归调用返回后，必须保证Z不发生改变，但对Y则无此要求。不过，仅Y [ l : r ]可能会发生改变。通过合并操作（见程序1 4 - 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。

为实现图1 4 - 1 6的策略，首先扫描Y [ 1 : r ]，并收集距分割线小于的点，将这些点存放在Z [ 1 : k - 1 ]中。可按如下两种方式来把RA中点p 与p 的比较区内的所有点进行配对：1) 与RB 中y 坐标≥p.y 的点配对；2) 与y 坐标≤p.y 的点配对。这可以通过将每个点Z [ i ]（1≤i < k，不管该点是在RA

还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。

2. 复杂性分析

令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).

这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。

[ 本帖最后由 风花雪月 于 2006-10-10 01:03 编辑 ]

风花雪月

分而治之算法

君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题——找出二维空间中距离最近的两个点。

本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。


算法思想


分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

例2-1 [找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。

现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。

例2-2 [金块问题] 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。

假设袋中有n 个金块。可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。程序2 - 2 6和2 - 2 7是另外两种方法，前者需要进行2n-2次比较，后者最多需要进行2n-2次比较。

下面用分而治之方法对这个问题进行求解。当n很小时，比如说， n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。

假设n= 8。这个袋子被平分为各有4个金块的两个袋子A和B。为了在A中找出最重和最轻的金块，A中的4个金块被分成两组A1和A2。每一组有两个金块，可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较，又能找出HA 2和LA 2。现在通过比较HA1和HA2，能找出HA；通过LA 1和LA2的比较找出LA。这样，通过4次比较可以找到HA 和LA。同样需要另外4次比较来确定HB 和LB。通过比较HA 和HB（LA 和LB），就能找出所有金块中最重和最轻的。因此，当n= 8时，这种分而治之的方法需要1 0次比较。如果使用程序1 - 3 1，则需要1 3次比较。如果使用程序2 - 2 6和2 - 2 7，则最多需要1 4次比较。设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设n是2的幂。当n= 2时，c(n) = 1。对于较大的n，c(n) = 2c(n/ 2 ) + 2。当n是2的幂时，使用迭代方法（见例2 - 2 0）可知

c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐个比较的方法少用了2 5％的比较次数。

例2-3 [矩阵乘法] 两个n×n 阶的矩阵A与B的乘积是另一个n×n 阶矩阵C，C可表示为假如每一个C(i, j) 都用此公式计算，则计算C所需要的操作次数为n3 m+n2 (n- 1) a，其中m表示一次乘法，a 表示一次加法或减法。

为了得到两个矩阵相乘的分而治之算法，需要： 1) 定义一个小问题，并指明小问题是如何进行乘法运算的； 2) 确定如何把一个大的问题划分成较小的问题，并指明如何对这些较小的问题进行乘法运算； 3) 最后指出如何根据小问题的结果得到大问题的结果。为了使讨论简便，假设n 是2的幂（也就是说， n是1，2，4，8，1 6，.）。

首先，假设n= 1时是一个小问题，n> 1时为一个大问题。后面将根据需要随时修改这个假设。对于1×1阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。

考察一个n> 1的大问题。可以将这样的矩阵分成4个n/ 2×n/ 2阶的矩阵A1，A2，A3，和A4。当n 大于1且n 是2的幂时，n/ 2也是2的幂。因此较小矩阵也满足前面对矩阵大小的假设。矩阵Bi 和Ci 的定义与此类似.

根据上述公式，经过8次n/ 2×n/ 2阶矩阵乘法和4次n/ 2×n/ 2阶矩阵的加法，就可以计算出A与B的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二步，将递归使用分而治之算法把8个小矩阵再细分（见程序2 - 1 9）。算法的复杂性为(n3 )，此复杂性与程序2 - 2 4直接使用公式（2 - 1）所得到的复杂性是一样的。事实上，由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果的时间将比用程序2 - 2 4还要长。

为了得到更快的算法，需要简化矩阵分割和再组合这两个步骤。一种方案是使用S t r a s s e n方法得到7个小矩阵。这7个小矩阵为矩阵D, E, ., J，矩阵D到J可以通过7次矩阵乘法， 6次矩阵加法，和4次矩阵减法计算得出。前述的4个小矩阵可以由矩阵D到J通过6次矩阵加法和两次矩阵减法得出.

用上述方案来解决n= 2的矩阵乘法。将某矩阵A和B相乘得结果C，如下所示：

因为n> 1，所以将A、B两矩阵分别划分为4个小矩阵，每个矩阵为1×1阶，仅包含一个元素。1×1阶矩阵的乘法为小问题，因此可以直接进行运算。利用计算D～J的公式，得：

D= 1（6-8）=-2

E= 4（7-5）= 8

F=（3 + 4）5 = 3 5

G=（1 + 2）8 = 2 4

H=（3-1）（5 + 6）= 2 2

I=（2-4）（7 + 8）=-3 0

J=（1 + 4）（5 + 8）= 6 5

根据以上结果可得：

对于上面这个2×2的例子，使用分而治之算法需要7次乘法和1 8次加/减法运算。而直接使用公式（2 - 1），则需要8次乘法和7次加/减法。要想使分而治之算法更快一些，则一次乘法所花费的时间必须比11次加/减法的时间要长。

假定S t r a s s e n矩阵分割方案仅用于n≥8的矩阵乘法，而对于n<8的矩阵乘法则直接利用公式（2 - 1）进行计算。则n= 8时，8×8矩阵相乘需要7次4×4矩阵乘法和1 8次4×4矩阵加/减法。每次矩阵乘法需花费6 4m+ 4 8a次操作，每次矩阵加法或减法需花费1 6a次操作。因此总的操作次数为7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接计算方法，则需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接计算方法快，至少要求5 1 2-4 4 8次乘法的开销比6 2 4-4 4 8次加/减法的开销大。或者说一次乘法的开销应该大于近似2 . 7 5次加/减法的开销。

假定n<1 6的矩阵是一个“小”问题，S t r a s s e n的分解方案仅仅用于n≥1 6的情况，对于n<1 6的矩阵相乘，直接利用公式（ 2 - 1）。则当n= 1 6时使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接计算时需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的开销与一次加/减法的开销相同，则S t r a s s e n方法需要7 8 7 2次操作及用于问题分解的额外时间，而直接计算方法则需要7 9 3 6次操作加上程序中执行f o r循环以及其他语句所花费的时间。即使直接计算方法所需要的操作次数比St r a s s e n方法少，但由于直接计算方法需要更多的额外开销，因此它也不见得会比S t r a s s e n方法快。

n 的值越大，Strassen 方法与直接计算方法所用的操作次数的差异就越大，因此对于足够大的n，Strassen 方法将更快。设t (n) 表示使用Strassen 分而治之方法所需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于k（k至少为8，也许更大，具体值由计算机的性能决定）. 用迭代方法计算，可得t(n) = (nl og27 )。因为l og27 ≈2 . 8 1，所以与直接计算方法的复杂性(n3 )相比，分而治之矩阵乘法算法有较大的改进。

注意事项

分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不过在有些情况下，不使用这样的递归栈而采用一个非递归程序来完成分而治之算法也是可能的，并且在这种方式下，程序得到结果的速度会比递归方式更快。解决金块问题的分而治之算法（例2 - 2）和归并排序方法（ 2 . 3节）就可以不利用递归而通过一个非递归程序来更快地完成。

例2-4 [金块问题] 用例2 - 2的算法寻找8个金块中最轻和最重金块的工作可以用二叉树来表示。这棵树的叶子分别表示8个金块（a, b,., h)，每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点A表示寻找8个金块中最轻、最重金块的问题，而节点B表示找出a,b,c 和d 这4个金块中最轻和最重金块的问题。算法从根节点开始。由根节点表示的8金块问题被划分成由节点B和C所表示的两个4金块问题。在B节点，4金块问题被划分成由D和E所表示的2金块问题。可通过比较金块a 和b 哪一个较重来解决D节点所表示的2金块问题。在解决了D和E所表示的问题之后，可以通过比较D和E中所找到的轻金块和重金块来解决B表示的问题。接着在F，G和C上重复这一过程，最后解决问题A。

可以将递归的分而治之算法划分成以下的步骤：

1) 从图2 - 2中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问题的大小为1或2。

2) 比较每个大小为2的问题中的金块，确定哪一个较重和哪一个较轻。在节点D、E、F和G上完成这种比较。大小为1的问题中只有一个金块，它既是最轻的金块也是最重的金块。

3) 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。对于节点A到C执行这种比较。

根据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和

最大值，这个工作对应于3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。

下面进行复杂性分析。注意到当n为偶数时，在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 )次比较，比较的总次数为3 n / 2 - 2。当n 为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数，当n>0时，比较的总次数为「3n/2ù-2次。

程序14-1 找出最小值和最大值的非递归程序

template

bool MinMax(T w[], int n, T& Min, T& Max)

{// 寻找w [ 0 : n - 1 ]中的最小和最大值

// 如果少于一个元素，则返回f a l s e

// 特殊情形： n <= 1

if (n < 1) return false;

if (n == 1) {Min = Max = 0;

return true;}

/ /对Min 和M a x进行初始化

int s; // 循环起点

if (n % 2) {// n 为奇数

Min = Max = 0;

s = 1;}

else {// n为偶数，比较第一对

if (w[0] > w[1]) {

Min = 1;

Max = 0;}

else {Min = 0;

Max = 1;}

s = 2;}

// 比较余下的数对

for (int i = s; i < n; i += 2) {

// 寻找w 和w [ i + 1 ]中的较大者

// 然后将较大者与w [ M a x ]进行比较

// 将较小者与w [ M i n ]进行比较

if (w > w[i+1]) {

if (w > w[Max]) Max = i;

if (w[i+1] < w[Min]) Min = i + 1;}

else {

if (w[i+1] > w[Max]) Max = i + 1;

if (w < w[Min]) Min = i;}

}

return true;

}

练习

1. 将例1 4 - 1的分而治之算法扩充到n> 1个硬币的情形。需要进行多少次重量的比较？

2. 考虑例1 4 - 1的伪币问题。假设把条件“伪币比真币轻”改为“伪币与真币的重量不同”，同样假定袋中有n 个硬币。

1) 给出相应分而治之算法的形式化描述，该算法可输出信息“不存在伪币”或找出伪币。算法应递归地将大的问题划分成两个较小的问题。需要多少次比较才能找到伪币（如果存在伪币）？

2) 重复1) ，但把大问题划分为三个较小问题。

3. 1) 编写一个C++ 程序，实现例1 4 - 2中寻找n 个元素中最大值和最小值的两种方案。使用递归来完成分而治之方案。

2) 程序2 - 2 6和2 - 2 7是另外两个寻找n 个元素中最大值和最小值的代码。试分别计算出每段程序所需要的最少和最大比较次数。

3) 在n 分别等于1 0 0，1 0 0 0或10 000的情况下，比较1）、2）中的程序和程序1 4 - 1的运行时间。对于程序2 - 2 7，使用平均时间和最坏情况下的时间。1）中的程序和程序2 - 2 6应具有相同的平均时间和最坏情况下的时间。

4) 注意到如果比较操作的开销不是很高，分而治之算法在最坏情况下不会比其他算法优越，为什么？它的平均时间优于程序2 - 2 7吗？为什么？

4. 证明直接运用公式（1 4 -2）~（1 4 - 5）得出结果的矩阵乘法的分而治之算法的复杂性为(n3 )。因此相应的分而治之程序将比程序2 - 2 4要慢。

5. 用迭代的方法来证明公式（1 4 - 6）的递归值为(n l og27)。

*6. 编写S t r a s s e n矩阵乘法程序。利用不同的k 值（见公式（1 4 - 6））进行实验，以确定k 为何值时程序性能最佳。比较程序及程序2 - 2 4的运行时间。可取n 为2的幂来进行比较。

7. 当n 不是2的幂时，可以通过增加矩阵的行和列来得到一个大小为2的幂的矩阵。假设使用最少的行数和列数将矩阵扩充为m 阶矩阵，其中m 为2的幂。

1) 求m / n。

2) 可使用哪些矩阵项组成新的行和列，以使新矩阵A' 和B' 相乘时，原来的矩阵A和B相乘的结果会出现在C' 的左上角？

3) 使用S t r a s s e n方法计算A' * B' 所需要的时间为(m2.81 )。给出以n 为变量的运行时间表达式。

[ 本帖最后由 风花雪月 于 2006-10-10 01:04 编辑 ]

风花雪月

贪婪算法

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

本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。




最优化问题



本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合限制条件的问题求解方案称为可行解（ feasible solution），使优化函数取得最佳值的可行解称为最优解（optimal solution）。

例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i 种饮料，对它作出相对评价，将一个数值si 作为满意度赋予第i 种饮料。

通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量（以盎司为单位），而此婴儿需要t 盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？

设各种饮料的满意度已知。令xi 为婴儿将要饮用的第i 种饮料的量，则需要解决的问题是：

找到一组实数xi（1≤i≤n），使n ?i = 1si xi 最大，并满足：n ?i=1xi =t 及0≤xi≤ai 。

需要指出的是：如果n ?i = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使婴儿解渴。

对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述：

输入：n，t，si ，ai（其中1≤i≤n，n 为整数，t、si 、ai 为正实数）。

输出：实数xi（1≤i≤n），使n ?i= 1si xi 最大且n ?i=1xi =t（0≤xi≤ai）。如果n ?i = 1ai
在这个问题中，限制条件是n ?i= 1xi =t 且0≤xi≤ai，1≤i≤n。而优化函数是n ?i= 1si xi 。任何满足限制条件的一组实数xi 都是可行解，而使n ?i= 1si xi 最大的可行解是最优解。

例1-2 [装载问题] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i 个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。

这个问题可以作为最优化问题进行描述：设存在一组变量xi ，其可能取值为0或1。如xi 为0，则货箱i 将不被装上船；如xi 为1，则货箱i 将被装上船。我们的目的是找到一组xi ，使它满足限制条件n ?i = 1wi xi ≤c 且x i ? {0, 1}, 1 ≤i≤n。相应的优化函数是n ?i= 1xi 。

满足限制条件的每一组xi 都是一个可行解，能使n ?i= 1xi 取得最大值的方案是最优解。

例1-3 [最小代价通讯网络] 城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。

在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。

[ 本帖最后由 风花雪月 于 2006-10-10 01:04 编辑 ]

风花雪月

在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。
例1-4 [找零钱] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。

假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。

贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。

例1-5 [机器调度] 现有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi ，si < fi 。[si , fi ] 为处理任务i 的时间范围。两个任务i，j 重指两个任务的时间范围区间有重叠，而并非是指i，j 的起点或终点重合。例如：区间[ 1，4 ]与区间[ 2，4 ]重叠，而与区间[ 4，7 ]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。

假设有n= 7件任务，标号为a 到g。它们的开始与完成时间如图13-1a 所示。若将任务a分给机器M1，任务b 分给机器M2，. . .，任务g 分给机器M7，这种分配是可行的分配，共使用了七台机器。但它不是最优分配，因为有其他分配方案可使利用的机器数目更少，例如：可以将任务a、b、d分配给同一台机器，则机器的数目降为五台。

一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务，且按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分给旧的机器。否则，将任务分配给一台新的机器。 根据例子中的数据，贪婪算法共分为n = 7步，任务分配的顺序为a、f、b、c、g、e、d。第一步没有旧机器，因此将a 分配给一台新机器（比如M1）。这台机器在0到2时刻处于忙状态。在第二步，考虑任务f。由于当f 启动时旧机器仍处于忙状态，因此将f 分配给一台新机器(设为M2 )。第三步考虑任务b, 由于旧机器M1在Sb = 3时刻已处于闲状态，因此将b分配给M1执行，M1下一次可用时刻变成fb = 7，M2的可用时刻变成ff = 5。第四步，考虑任务c。由于没有旧机器在Sc = 4时刻可用，因此将c 分配给一台新机器（M3），这台机器下一次可用时间为fc = 7。第五步考虑任务g，将其分配给机器M2，第六步将任务e 分配给机器M1, 最后在第七步，任务2分配给机器M3。（注意：任务d 也可分配给机器M2）。

上述贪婪算法能导致最优机器分配的证明留作练习（练习7）。可按如下方式实现一个复杂性为O (nl o gn)的贪婪算法：首先采用一个复杂性为O (nl o gn)的排序算法（如堆排序）按Si 的递增次序排列各个任务，然后使用一个关于旧机器可用时间的最小堆。

例1-6 [最短路径] 给出一个有向网络，路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点s 到达目的顶点d 的最短路径。

贪婪算法分步构造这条路径，每一步在路径中加入一个顶点。假设当前路径已到达顶点q，

且顶点q 并不是目的顶点d。加入下一个顶点所采用的贪婪准则为：选择离q 最近且目前不在路径中的顶点。

这种贪婪算法并不一定能获得最短路径。例如，假设在图1 3 - 2中希望构造从顶点1到顶点5的最短路径，利用上述贪婪算法，从顶点1开始并寻找目前不在路径中的离顶点1最近的顶点。到达顶点3，长度仅为2个单位，从顶点3可以到达的最近顶点为4，从顶点4到达顶点2，最后到达目的顶点5。所建立的路径为1 , 3 , 4 , 2 , 5，其长度为1 0。这条路径并不是有向图中从1到5的最短路径。事实上，有几条更短的路径存在，例如路径1，4，5的长度为6。

根据上面三个例子，回想一下前几章所考察的一些应用，其中有几种算法也是贪婪算法。例如，霍夫曼树算法，利用n- 1步来建立最小加权外部路径的二叉树，每一步都将两棵二叉树合并为一棵，算法中所使用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。L P T调度规则也是一种贪婪算法，它用n 步来调度n 个作业。首先将作业按时间长短排序，然后在每一步中为一个任务分配一台机器。选择机器所利用的贪婪准则为：使目前的调度时间最短。将新作业调度到最先完成的机器上（即最先空闲的机器）。

注意到在机器调度问题中，贪婪算法并不能保证最优，然而，那是一种直觉的倾向且一般情况下结果总是非常接近最优值。它利用的规则就是在实际环境中希望人工机器调度所采用的规则。算法并不保证得到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（ h e u r i s t i c s )。因此L P T方法是一种启发式机器调度方法。定理9 - 2陈述了L P T调度的完成时间与最佳调度的完成时间之间的关系，因此L P T启发式方法具有限定性

能（ bounded performance ）。具有限定性能的启发式方法称为近似算法（ a p p r o x i m a t i o na l g o r i t h m）。

本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。

[ 本帖最后由 风花雪月 于 2006-10-10 01:05 编辑 ]

风花雪月

这个问题来自例1 - 2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。

例1-7 假设n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用贪婪算法时，所考察货箱的顺序为7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱7 , 3 , 6 , 8 , 4 , 1的总重量为3 9 0个单位且已被装载，剩下的装载能力为1 0个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且?xi = 6。

定理1-1 利用贪婪算法能产生最佳装载。

证明可以采用如下方式来证明贪婪算法的最优性：令x = [x1 , ..., xn ]为用贪婪算法获得的解，令y =[ y1 , ..., yn ]为任意一个可行解，只需证明n ?i= 1xi ≥n ?i= 1yi 。不失一般性，可以假设货箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分几步将y 转化为x，转换过程中每一步都产生一个可行的新y，且n ?i = 1yi 大于等于未转化前的值，最后便可证明n ?i = 1xi ≥n ?j = 1yi 。

根据贪婪算法的工作过程，可知在[0, n] 的范围内有一个k，使得xi =1, i≤k且xi =0, i>k。寻找[ 1 ,n]范围内最小的整数j，使得xj≠yj 。若没有这样的j 存在，则n ?i= 1xi =n ?i = 1yi 。如果有这样的j 存在，则j≤k，否则y 就不是一个可行解，因为xj≠yj ，xj = 1且yj = 0。令yj = 1，若结果得到的y 不是可行解，则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0，由于wj≤wl ，则得到的y 是可行的。而且，得到的新y 至少与原来的y 具有相同数目的1。

经过数次这种转化，可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1，因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序（见3 . 5节间接寻址的定义），随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)（也可利用9 . 5 . 1节的堆排序及第2章的归并排序），算法其余部分所需时间为O (n)，因此程序1 3 - 1的总的复杂性为O (nl o gn)。

程序13-1 货箱装船

template

void ContainerLoading(int x[], T w[], T c, int n)

{// 货箱装船问题的贪婪算法

// x = 1 当且仅当货箱i被装载， 1<=i<=n

// c是船的容量, w 是货箱的重量

// 对重量按间接寻址方式排序

// t 是间接寻址表

int *t = new int [n+1];

I n d i r e c t S o r t ( w, t, n);

// 此时, w[t] <= w[t[i+1]], 1<=i


// 初始化x

for (int i = 1; i <= n; i++)

x = 0;

// 按重量次序选择物品

for (i = 1; i <= n && w[t] <= c; i++) {

x[t] = 1;

c -= w[t];} // 剩余容量

delete [] t;

}

[ 本帖最后由 风花雪月 于 2006-10-10 01:06 编辑 ]

风花雪月

在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。

在这个表达式中，需求出xt 的值。xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。 例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。

0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。

还可以利用另一方案，价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可

装入包的pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。

我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1背包问题是一个N P-复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中，用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %，所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问，是否存在一个x (x<1 0 0 )，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。贪婪算法结果为x=[1,0], 这种方案的值为1 0。对于y≥1 0 / 9，最优解的值为9 y。因此，贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %，对于大的y，这个值趋近于1 0 0 %。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x% (x<100) 之内。首先将最多k 件物品放入背包，如果这k 件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。

例13-9 考虑n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。当k= 0时，背包按物品价值密度非递减顺序装入，首先将物品1放入背包，然后是物品2，背包剩下的容量为5个单元，剩下的物品没有一个合适的，因此解为x = [ 1 , 1 , 0 , 0 ]。此解获得的价值为1 6。

现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }产生与k= 0时相同的结果，考虑子集{ 3 }，置x3 为1。此时还剩5个单位的容量，按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1，它适合，因此取x1 为1，这时仅剩下3个单位容量了，且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1 , 0 , 1 , 0 ]，获得的价值为1 8。若从子集{ 4 }开始，产生的解为x = [ 1 , 0 , 0 , 1 ]，获得的价值为1 9。考虑子集大小为0和1时获得的最优解为[ 1 , 0 , 0 , 1 ]。这个解是通过k= 1的贪婪启发式算法得到的。

若k= 2，除了考虑k< 2的子集，还必需考虑子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。首先从最后一个子集开始，它是不可行的，故将其抛弃，剩下的子集经求解分别得到如下结果：[ 1 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ]，这些结果中最后一个价值为2 3，它的值比k= 0和k= 1时获得的解要高，这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法（k - o p t i m a l）。也就是，若从答案中取出k 件物品，并放入另外k 件，获得的结果不会比原来的好，而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当k= 1时，保证最终结果在最佳值的5 0 %以内；当k= 2时，则在3 3 . 3 3 %以内等等，这种启发式方法的执行时间随k 的增大而增加，需要测试的子集数目为O (nk )，每一个子集所需时间为O (n)，因此当k >0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。

[ 本帖最后由 风花雪月 于 2006-10-10 01:06 编辑 ]

风花雪月

一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边(i, j) 表示先后关系：任务j 开始前任务i 必须完成。图1 - 4显示了六个任务的工程，边（ 1 , 4）表示任务1在任务4开始前完成，同样边（ 4 , 6）表示任务4在任务6开始前完成，边（1 , 4）与（4 , 6）合起来可知任务1在任务6开始前完成，即前后关系是传递的。由此可知，边（1 , 4）是多余的，因为边（1 , 3）和（3 , 4）已暗示了这种关系。

在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边（ i, j）表示在装配序列中任务i 在任务j 的前面，具有这种性质的序列称为拓扑序列（topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序（topological sorting）。图1 - 4的任务有向图有多种拓扑序列，其中的三种为1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（ 3 , 4），这种序列与边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点：从剩下的顶点中，选择顶点w，使得w 不存在这样的入边（ v,w），其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则（即有向图中存在边（ v,w）且v 不在已构造的序列中），则无法完成拓扑排序，因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。

现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V = 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2 5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V

得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。

1. 贪婪算法的正确性

为保证贪婪算法算的正确性，需要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若

算法没有失败，V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。

定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。

证明注意到当失败时| V |


2. 数据结构的选择

为将图1 - 5用C + +代码来实现，必须考虑序列V的描述方法，以及如何找出可加入V的候选顶点。一种高效的实现方法是将序列V用一维数组v 来描述的，用一个栈来保存可加入V的候选顶点。另有一个一维数组I n D e g r e e，I n D e g r e e[ j ]表示与顶点j相连的节点i 的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（ i, j）。当I n D e g r e e[ j ]变为0时表示j 成为一个候选节点。序列V初始时为空。I n D e g r e e[ j ]为顶点j 的入度。每次向V中加入一个顶点时，所有与新加入顶点邻接的顶点j，其I n D e g r e e[ j ]减1。对于有向图1 - 4，开始时I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由于顶点1和2的I n D e g r e e值为0，因此它们是可加入V的候选顶点，由此，顶点1和2首先入栈。每一步，从栈中取出一个顶点将其加入V，同时减去与其邻接的顶点的I n D e g r e e值。若在第一步时从栈中取出顶点2并将其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由于I n D e g r e e [ 5 ]刚刚变为0，因此将顶点5入栈。

程序1 3 - 2给出了相应的C + +代码，这个代码被定义为N e t w o r k的一个成员函数。而且，它对于有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针对有向图来定义的。为解决这个问题，利用同样的模板来定义成员函数AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。这些函数可重载N e t w o r k中的函数并可输出错误信息。如果找到拓扑序列，则Topological 函数返回t r u e；若输入的有向图无拓扑序列则返回f a l s e。当找到拓扑序列时，将其返回到v [ 0 :n- 1 ]中。

3. Network:Topological 的复杂性

第一和第三个f o r循环的时间开销为(n )。若使用（耗费）邻接矩阵,则第二个for 循环所用的时间为(n2 )；若使用邻接链表,则所用时间为(n+e)。在两个嵌套的while 循环中，外层循环需执行n次，每次将顶点w 加入到v 中，并初始化内层while 循环。使用邻接矩阵时，内层w h i l e循环对于每个顶点w 需花费(n)的时间；若利用邻接链表，则这个循环需花费dwout 的时间，因此，内层while 循环的时间开销为(n2 )或(n+e)。所以，若利用邻接矩阵，程序1 3 - 2的时间复杂性为(n2 )，若利用邻接链表则为(n+e)。

程序13-2 拓扑排序

bool Network::Topological(int v[])

{// 计算有向图中顶点的拓扑次序

// 如果找到了一个拓扑次序，则返回t r u e，此时，在v [ 0 : n - 1 ]中记录拓扑次序

// 如果不存在拓扑次序，则返回f a l s e

int n = Ve r t i c e s ( ) ;

// 计算入度

int *InDegree = new int [n+1];

InitializePos(); // 图遍历器数组

for (int i = 1; i <= n; i++) // 初始化

InDegree = 0;

for (i = 1; i <= n; i++) {// 从i 出发的边

int u = Begin(i);

while (u) {

I n D e g r e e [ u ] + + ;

u = NextVe r t e x ( i ) ; }

}

// 把入度为０的顶点压入堆栈

LinkedStack S;

for (i = 1; i <= n; i++)

if (!InDegree) S.Add(i);

// 产生拓扑次序

i = 0; // 数组v 的游标

while (!S.IsEmpty()) {// 从堆栈中选择

int w; // 下一个顶点

S . D e l e t e ( w ) ;

v[i++] = w;

int u = Begin(w);

while (u) {// 修改入度

I n D e g r e e [ u ] - - ;

if (!InDegree) S.Add(u);

u = NextVe r t e x ( w ) ; }

}

D e a c t i v a t e P o s ( ) ;

delete [] InDegree;

return (i == n);

}

[ 本帖最后由 风花雪月 于 2006-10-10 01:07 编辑 ]

风花雪月

分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。


/ /使用快速排序方法对a[ 0 :n- 1 ]排序

从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点

把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点

递归地使用快速排序方法对left 进行排序

递归地使用快速排序方法对right 进行排序

所得结果为l e f t + m i d d l e + r i g h t

图14-9 快速排序的伪代码


考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。

把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。

程序14-6 快速排序

template

void QuickSort(T*a, int n)

{// 对a[0:n-1] 进行快速排序

{// 要求a[n] 必需有最大关键值

quickSort(a, 0, n-1);

template

void quickSort(T a[], int l, int r)

{// 排序a [ l : r ]， a[r+1] 有大值

if (l >= r) return;

int i = l, // 从左至右的游标

j = r + 1; // 从右到左的游标

T pivot = a[l];

// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换

while (true) {

do {// 在左侧寻找>= pivot 的元素

i = i + 1;

} while (a < pivot);

do {// 在右侧寻找<= pivot 的元素

j = j - 1;

} while (a[j] > pivot);

if (i >= j) break; // 未发现交换对象

Swap(a, a[j]);

}

// 设置p i v o t

a[l] = a[j];

a[j] = pivot;

quickSort(a, l, j-1); // 对左段排序

quickSort(a, j+1, r); // 对右段排序

}

若把程序1 4 - 6中d o - w h i l e条件内的<号和>号分别修改为< =和> =，程序1 4 - 6仍然正确。实验结果表明使用程序1 4 - 6的快速排序代码可以得到比较好的平均性能。为了消除程序中的递归，必须引入堆栈。不过，消除最后一个递归调用不须使用堆栈。消除递归调用的工作留作练习（练习1 3）。程序1 4 - 6所需要的递归栈空间为O (n)。若使用堆栈来模拟递归，则可以把这个空间减少为O ( l o gn)。在模拟过程中，首先对left 和right 中较小者进行排序，把较大者的边界放入堆栈中。在最坏情况下l e f t总是为空，快速排序所需的计算时间为(n2 )。在最好情况下， l e f t和r i g h t中的元素数目大致相同，快速排序的复杂性为(nl o gn)。令人吃惊的是，快速排序的平均复杂性也是(nl o gn)。

定理2-1 快速排序的平均复杂性为(nl o gn)。

证明用t (n) 代表对含有n 个元素的数组进行排序的平均时间。当n≤1时，t (n)≤d，d为某一常数。当n <1时，用s 表示左段所含元素的个数。由于在中段中有一个支点元素，因此右段中元素的个数为n-s- 1。所以左段和右段的平均排序时间分别为t (s), t (n-s- 1 )。分割数组中元素所需要的时间用cn 表示，其中c 是一个常数。因为s 有同等机会取0 ~n- 1中的任何一个值.

如对（2 - 8）式中的n 使用归纳法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8为自然对数的基底。在归纳开始时首先验证n= 2时公式的正确性。根据公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在归纳假设部分，假定t(n)≤kn l o ge n（当2≤n＜m 时，m 是任意一个比2大的整数＝.

图1 4 - 1 0对本书中所讨论的算法在平均条件下和最坏条件下的复杂性进行了比较。


方法最坏复杂性平均复杂性

冒泡排序n2 n2

计数排序n2 n2

插入排序n2 n2

选择排序n2 n2

堆排序nl o gn nl o gn

归并排序nl o gn nl o gn

快速排序n2 nl o gn

图14-10 各种排序算法的比较


中值快速排序（ median-of-three quick sort）是程序1 4 - 6的一种变化，这种算法有更好的平均性能。注意到在程序1 4 - 6中总是选择a [ 1 ]做为支点，而在这种快速排序算法中，可以不必使用a [ 1 ]做为支点，而是取{a[1],a[(1+r)/2],a[r]} 中大小居中的那个元素作为支点。例如，假如有三个元素，大小分别为5，9，7，那么取7为支点。为了实现中值快速排序算法，一种最简单的方式就是首先选出中值元素并与a[1] 进行交换，然后利用程序1 4 - 6完成排序。如果a [ r ]是被选出的中值元素，那么将a[1] 与a[r] 进行交换，然后将a [ 1 ]（即原来的a [ r ]）赋值给程序1 4 - 6中的变量p i v o t，之后继续执行程序1 4 - 6中的其余代码。

图2 - 11中分别给出了根据实验所得到的归并排序、堆排序、插入排序、快速排序的平均时间。对于每一个不同的n, 都随机产生了至少1 0 0组整数。随机整数的产生是通过反复调用s t d l i b . h库中的r a n d o m函数来实现的。如果对一组整数进行排序的时间少于1 0个时钟滴答，则继续对其他组整数进行排序，直到所用的时间不低于1 0个时钟滴答。在图2 - 11中的数据包含产生随机整数的时间。对于每一个n，在各种排序法中用于产生随机整数及其他开销的时间是相同的。因此，图2 - 11中的数据对于比较各种排序算法是很有用的。

对于足够大的n，快速排序算法要比其他算法效率更高。从图中可以看到快速排序曲线与插入排序曲线的交点横坐标比2 0略小，可通过实验来确定这个交点横坐标的精确值。可以分别用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9进行实验，以寻找精确的交点。令精确的交点横坐标为nBr e a k。当n≤nBreak 时，插入排序的平均性能最佳。当n＞nBreak 时，快速排序性能最佳。当n＞nBreak 时，把插入排序与快速排序组合为一个排序函数，可以提高快速排序的性能，实现方法是把程序1 4 - 6中的以下语句：

if(l >= r)r e t u r n ;

替换为

if (r-1
这里I n s e r t i o n S o r t ( a , l , r )用来对a [ 1 : r ]进行插入排序。测量修改后的快速排序算法的性能留作练习（练习2 0）。用更小的值替换n B r e a k有可能使性能进一步提高（见练习2 0）。

大多数实验表明，当n＞c时（c为某一常数），在最坏情况下归并排序的性能也是最佳的。而当n≤c时，在最坏情况下插入排序的性能最佳。通过将插入排序与归并排序混合使用，可以提高归并排序的性能

[ 本帖最后由 风花雪月 于 2006-10-10 01:07 编辑 ]

风花雪月

二分图是一个无向图，它的n 个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A' 覆盖集合B（或简单地说，A' 是一个覆盖）。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时，A' 为最小覆盖。

例1-10 考察如图1 - 6所示的具有1 7个顶点的二分图，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。

二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k 个集合S= {S1 , S2 ,., Sk }，每个集合Si 中的元素均是全集U中的成员。当且仅当èi S'Si =U时，S的子集S' 覆盖U，S '中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S' 为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 , ., Sk ，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。

例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖， S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。

集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。

例1-12 考察图1 - 6所示的二分图，初始化A' = 且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。顶点1能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }），顶点2 覆盖一个( { 4 } )，顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 , 9 , 1 0 , 11 }。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点{ 1 0 , 11} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A' = { 1 6 , 1 , 1 7 }。

图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。

1. 数据结构的选取及复杂性分析

为实现图13 - 7的算法，需要选择A' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A' 仅使用加法运算，则可用一维整型数组C来描述A '，用m 来记录A' 中元素个数。将A' 中的成员记录在C[ 0 :m-1] 中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi 值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。

例1-13 考察图1 - 6，初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。假设在例1 - 1 2中，第一步选择顶点1 6，为更新N e wi 的值检查B中所有最近被覆盖的顶点，这些顶点为5 , 6 , 8 , 1 2 , 1 4和1 5。当检查顶点5时，将顶点2和1 6的N e wi 值分别减1，因为顶点5不再是被顶点2和1 6覆盖的未覆盖节点；当检查顶点6时，顶点1 , 2 ,和1 6的相应值分别减1；同样，检查顶点8时，1，2，3和1 6的值分别减1；当检查完所有最近被覆盖的顶点，得到的N e wi 值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和1 3；检查顶点4时，N e w1 , N e w2, 和N e w1 7 的值减1；检查顶点7时，N e w1 的值减1，因为顶点1是覆盖7的唯一顶点。

为了实现顶点选取的过程，需要知道N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，N e w是一个整型数组，New 即等于N e wi，且c o v为一个布尔数组。若顶点i未被覆盖则c o v [ i ]等于f a l s e，否则c o v [ i ]为t r u e。现将图1 - 7的伪代码进行细化得到图1 - 8。

m=0; //当前覆盖的大小

对于A中的所有i，New=Degree

对于B中的所有i，C o v [ i ] = f a l s e

while (对于A中的某些i,New>0) {

设v是具有最大的N e w [ i ]的顶点；

C [ m + + ] = v ;

for ( 所有邻接于v的顶点j) {

if (!Cov[j]) {

Cov[j]= true;

对于所有邻接于j的顶点，使其N e w [ k ]减1

} } }

if (有些顶点未被覆盖) 失败

else 找到一个覆盖

图1-8 图1-7的细化

更新N e w的时间为O (e)，其中e 为二分图中边的数目。若使用邻接矩阵，则需花(n2 ) 的时间来寻找图中的边，若用邻接链表，则需(n+e) 的时间。实际更新时间根据描述方法的不同为O (n2 ) 或O (n+e)。逐步选择顶点所需时间为(S i z e O f A)，其中S i z e O f A=| A |。因为A的所有顶点都有可能被选择，因此所需步骤数为O ( S i z e O f A )，覆盖算法总的复杂性为O ( S i z e O f A 2+n2) = O ( n2)或O (S i z e Of A2+n + e)。

2. 降低复杂性

通过使用有序数组N e wi、最大堆或最大选择树（max selection tree）可将每步选取顶点v的复杂性降为( 1 )。但利用有序数组，在每步的最后需对N e wi 值进行重新排序。若使用箱子排序，则这种排序所需时间为(S i z e O f B ) ( S i z e O fB =|B| ) （见3 . 8 . 1节箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序数组并不总能提高性能。

如果利用最大堆，则每一步都需要重建堆来记录N e w值的变化，可以在每次N e w值减1时进行重建。这种减法操作可引起被减的N e w值最多在堆中向下移一层，因此这种重建对于每次N e w值减1需( 1 )的时间，总共的减操作数目为O (e)。因此在算法的所有步骤中，维持最大堆仅需O (e)的时间，因而利用最大堆时覆盖算法的总复杂性为O (n2 )或O (n+e)。

若利用最大选择树，每次更新N e w值时需要重建选择树，所需时间为(log S i z e O f A)。重建的最好时机是在每步结束时，而不是在每次N e w值减1时，需要重建的次数为O (e)，因此总的重建时间为O (e log S i z e OfA)，这个时间比最大堆的重建时间长一些。然而，通过维持具有相同N e w值的顶点箱子，也可获得和利用最大堆时相同的时间限制。由于N e w的取值范围为0到S i z e O f B，需要S i z e O f B+ 1个箱子，箱子i 是一个双向链表，链接所有N e w值为i 的顶点。在某一步结束时，假如N e w [ 6 ]从1 2变到4，则需要将它从第1 2个箱子移到第4个箱子。利用模拟指针及一个节点数组n o d e（其中n o d e [ i ]代表顶点i，n o d e [ i ] . l e f t和n o d e [ i ] . r i g h t为双向链表指针），可将顶点6从第1 2个箱子移到第4个箱子，从第1 2个箱子中删除n o d e [ 0 ]并将其插入第4个箱子。利用这种箱子模式，可得覆盖启发式算法的复杂性为O (n2 )或O(n+e)。（取决于利用邻接矩阵还是线性表来描述图）。

3. 双向链接箱子的实现

为了实现上述双向链接箱子，图1 - 9定义了类U n d i r e c t e d的私有成员。N o d e Ty p e是一个具有私有整型成员l e f t和r i g h t的类，它的数据类型是双向链表节点，程序1 3 - 3给出了U n d i r e c t e d的私有成员的代码。





void CreateBins (int b, int n)

创建b个空箱子和n个节点

void DestroyBins() { delete [] node;

delete [] bin;}

void InsertBins(int b, int v)

在箱子b中添加顶点v

void MoveBins(int bMax, int ToBin, int v)

从当前箱子中移动顶点v到箱子To B i n

int *bin;

b i n [ i ]指向代表该箱子的双向链表的首节点

N o d e Type *node;

n o d e [ i ]代表存储顶点i的节点

图1-9 实现双向链接箱子所需的U n d i r e c t e d私有成员


程序13-3 箱子函数的定义

void Undirected::CreateBins(int b, int n)

{// 创建b个空箱子和n个节点

node = new NodeType [n+1];

bin = new int [b+1];

// 将箱子置空

for (int i = 1; i <= b; i++)

bin = 0;

}

void Undirected::InsertBins(int b, int v)

{// 若b不为０，则将v 插入箱子b

if (!b) return; // b为0，不插入

node[v].left = b; // 添加在左端

if (bin) node[bin].left = v;

node[v].right = bin;

bin = v;

}

void Undirected::MoveBins(int bMax, int ToBin, int v)

{// 将顶点v 从其当前所在箱子移动到To B i n .

// v的左、右节点

int l = node[v].left;

int r = node[v].right;

// 从当前箱子中删除

if (r) node[r].left = node[v].left;

if (l > bMax || bin[l] != v) // 不是最左节点

node[l].right = r;

else bin[l] = r; // 箱子l的最左边

// 添加到箱子To B i n

I n s e r t B i n s ( ToBin, v);

}

函数C r e a t e B i n s动态分配两个数组： n o d e和b i n，n o d e [i ]表示顶点i, bin[i ]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果b≠0，函数InsertBins 将顶点v 插入箱子b 中。因为b 是顶点v 的New 值，b = 0意味着顶点v 不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n 加入New 值为b 的双向链表箱子的最前面，这种加入方式需要将node[v] 加入bin 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left 置为b。若箱子不空，则当前第一个节点的left 指针被置为指向新节点。node[v] 的右指针被置为b i n [ b ]，其值可能为0或指向上一个首节点的指针。最后， b i n [ b ]被更新为指向表中新的第一个节点。MoveBins 将顶点v 从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n[ j ]都有：如j>bMa x，则b i n [ j ]为空。代码首先确定n o d e [ v ]在当前双向链表中的左右节点，接着从双链表中取出n o d e [ v ]，并利用I n s e r t B i n s函数将其重新插入到b i n [ To B i n ]中。

4. Undirected::BipartiteCover的实现

函数的输入参数L用于分配图中的顶点（分配到集合A或B）。L [i ] = 1表示顶点i在集合A中，L[ i ] = 2则表示顶点在B中。函数有两个输出参数： C和m，m为所建立的覆盖的大小， C [ 0 , m - 1 ]是A中形成覆盖的顶点。若二分图没有覆盖，函数返回f a l s e；否则返回t r u e。完整的代码见程序1 3 - 4。

程序13-4 构造贪婪覆盖

bool Undirected::BipartiteCover(int L[], int C[], int& m)

{// 寻找一个二分图覆盖

// L 是输入顶点的标号, L = 1 当且仅当i 在Ａ中

// C 是一个记录覆盖的输出数组

// 如果图中不存在覆盖，则返回f a l s e

// 如果图中有一个覆盖，则返回t r u e ;

// 在m中返回覆盖的大小; 在C [ 0 : m - 1 ]中返回覆盖

int n = Ve r t i c e s ( ) ;

// 插件结构

int SizeOfA = 0;

for (int i = 1; i <= n; i++) // 确定集合A的大小

if (L == 1) SizeOfA++;

int SizeOfB = n - SizeOfA;

CreateBins(SizeOfB, n);

int *New = new int [n+1]; / /顶点i覆盖了Ｂ中N e w [ i ]个未被覆盖的顶点

bool *Change = new bool [n+1]; // Change为t r u e当且仅当New 已改变

bool *Cov = new bool [n+1]; // Cov 为true 当且仅当顶点i 被覆盖

I n i t i a l i z e P o s ( ) ;

LinkedStack S;

// 初始化

for (i = 1; i <= n; i++) {

Cov = Change = false;

if (L == 1) {// i 在A中

New = Degree(i); // i 覆盖了这么多

InsertBins(New, i);}}

// 构造覆盖

int covered = 0, // 被覆盖的顶点

MaxBin = SizeOfB; // 可能非空的最大箱子

m = 0; // C的游标

while (MaxBin > 0) { // 搜索所有箱子

// 选择一个顶点

if (bin[MaxBin]) { // 箱子不空

int v = bin[MaxBin]; // 第一个顶点

C[m++] = v; // 把v 加入覆盖

// 标记新覆盖的顶点

int j = Begin(v), k;

while (j) {

if (!Cov[j]) {// j尚未被覆盖

Cov[j] = true;

c o v e r e d + + ;

// 修改N e w

k = Begin(j);

while (k) {

New[k]--; // j 不计入在内

if (!Change[k]) {

S.Add(k); // 仅入栈一次

Change[k] = true;}

k = NextVe r t e x ( j ) ; }

}

j = NextVe r t e x ( v ) ; }

// 更新箱子

while (!S.IsEmpty()) {

S . D e l e t e ( k ) ;

Change[k] = false;

MoveBins(SizeOfB, New[k], k);}

}

else MaxBin--;

}

D e a c t i v a t e P o s ( ) ;

D e s t r o y B i n s ( ) ;

delete [] New;

delete [] Change;

delete [] Cov;

return (covered == SizeOfB);

}

程序1 3 - 4首先计算出集合A和B的大小、初始化必要的双向链表结构、创建三个数组、初始化图遍历器、并创建一个栈。然后将数组C o v和C h a n g e初始化为f a l s e，并将A中的顶点根据它们覆盖B中顶点的数目插入到相应的双向链表中。

为了构造覆盖，首先按SizeOfB 递减至1的顺序检查双向链表。当发现一个非空的表时，就将其第一个顶点v 加入到覆盖中，这种策略即为选择具有最大Ne o v [ j ]置为t r u e，表示顶点j 现在已被覆盖，同时将已被覆盖的B中的顶点数目加1。由于j 是最近被覆w 值的顶点。将所选择的顶点加入覆盖数组C并检查B中所有与它邻接的顶点。若顶点j 与v 邻接且还未被覆盖，则将C盖的，所有A中与j 邻接的顶点的New 值减1。下一个while 循环降低这些New 值并将New 值被降低的顶点保存在一个栈中。当所有与顶点v邻接的顶点的Cov 值更新完毕后，N e w值反映了A中每个顶点所能覆盖的新的顶点数，然而A中的顶点由于New 值被更新，处于错误的双向链表中，下一个while 循环则将这些顶点移到正确的表中。

[ 本帖最后由 风花雪月 于 2006-10-10 01:08 编辑 ]

风花雪月

在这个问题中，给出有向图G，它的每条边都有一个非负的长度（耗费） a [i ][ j ]，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点s 为1，从顶点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。

利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a的方法按路径长度顺序产生最短路径。

首先最初产生从s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是D i j k s t r a算法。

可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图1 3 - 1 0中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。

通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p [ i ]给出从s 到达i的路径中顶点i 前面的那个顶点。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从s 到顶点i 的路径可反向创建。从i 出发按p,p[p],p[p[p]], .的顺序，直到到达顶点s 或0。在本例中，如果从i = 5开始，则顶点序列为p=4, p[4]=3, p[3]=1=s，因此路径为1 , 3 , 4 , 5。

为能方便地按长度递增的顺序产生最短路径，定义d [ i ]为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点i。最初，仅有从s 到s 的一条长度为0的路径，这时对于每个顶点i，d [ i ]等于a [ s ] [ i ]（a 是有向图的长度邻接矩阵）。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。

综上所述，可以得到图1 3 - 11所示的伪代码， 1) 将与s 邻接的所有顶点的p 初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s 到i 的最短路径，即是由s到它自身那条路径再扩充一条边得到。当找到更短的路径时， p [ i ]值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新d 的值。





1) 初始化d[i ] =a [i ]（1≤i≤n），

对于邻接于s的所有顶点i，置p[i ] =s, 对于其余的顶点置p[i ] = 0；

对于p≠0的所有顶点建立L表。

2) 若L为空，终止，否则转至3 )。

3) 从L中删除d值最小的顶点。

4) 对于与i 邻接的所有还未到达的顶点j，更新d[ j ]值为m i n{d[ j ], d[i ] +a[i ][ j ] }；若d[ j ]发生了变化且j 还未

在L中，则置p[ j ] = 1，并将j 加入L，转至2。

图1 - 11 最短路径算法的描述

1. 数据结构的选择

我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d 值最小的顶点。如果L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n )。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d 值，所以在4) 中可能需要改变一些d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为O ( n2 l o g n )。

若L用无序的链表来维护，则3) 与4) 花费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n )的时间，每次减操作需( 1 )的时间（需要减去d[j] 的值，但链表不用改变）。利用无序链表将图1 - 11的伪代码细化为程序1 3 - 5，其中使用了C h a i n (见程序3 - 8 )和C h a i n I t e r a t o r类（见程序3 - 1 8）。

程序13-5 最短路径程序

template

void AdjacencyWDigraph::ShortestPaths(int s, T d[], int p[])

{// 寻找从顶点s出发的最短路径, 在d中返回最短距离

// 在p中返回前继顶点

if (s < 1 || s > n) throw OutOfBounds();

Chain L; // 路径可到达顶点的列表

ChainIterator I;

// 初始化d, p, L

for (int i = 1; i <= n; i++){

d = a;

if (d == NoEdge) p = 0;

else {p = s;

L . I n s e r t ( 0 , i ) ; }

}

// 更新d, p

while (!L.IsEmpty()) {// 寻找具有最小d的顶点v

int *v = I.Initialize(L);

int *w = I.Next();

while (w) {

if (d[*w] < d[*v]) v = w;

w = I.Next();}

// 从L中删除通向顶点v的下一最短路径并更新d

int i = *v;

L . D e l e t e ( * v ) ;

for (int j = 1; j <= n; j++) {

if (a[j] != NoEdge && (!p[j] ||

d[j] > d + a[j])) {

// 减小d [ j ]

d[j] = d + a[j];

// 将j加入L

if (!p[j]) L.Insert(0,j);

p[j] = i;}

}

}

}

若N o E d g e足够大，使得没有最短路径的长度大于或等于N o E d g e，则最后一个for 循环的i f条件可简化为：if (d[j] > d + a[j])) NoEdge 的值应在能使d[j]+a[j] 不会产生溢出的范围内。

2. 复杂性分析

程序1 3 - 5的复杂性是O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有可能在最短路径中。因此这种算法的最小可能时间为O ( e )。由于使用耗费邻接矩阵来描述图，仅决定哪条边在有向图中就需O ( n2 )的时间。因此，采用这种描述方法的算法需花费O ( n2 )的时间。不过程序1 3 - 5作了优化（常数因子级）。即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e )（因为只有与i 邻接的顶点的d 值改变）。从L中选择及删除最小距离的顶点所需总时间仍然是O( n2 )。

[ 本帖最后由 风花雪月 于 2006-10-10 01:09 编辑 ]

风花雪月

在例1 - 2及1 - 3中已考察过这个问题。因为具有n 个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。

1. Kruskal算法

(1) 算法思想

K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

考察图1-12a 中的网络。初始时没有任何边被选择。图13-12b 显示了各节点的当前状态。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。





/ /在一个具有n 个顶点的网络中找到一棵最小生成树

令T为所选边的集合，初始化T=

令E 为网络中边的集合

w h i l e(E≠ )&&(| T |≠n- 1 ) {

令(u,v)为E中代价最小的边 E=E- { (u,v) } / /从E中删除边

i f( (u,v)加入T中不会产生环路)将（ u,v）加入T

}

i f(| T | = =n-1) T是最小耗费生成树

e l s e 网络不是互连的，不能找到生成树

图13-13 Kruskao算法的伪代码


(2) 正确性证明

利用前述装载问题所用的转化技术可以证明图1 3 - 1 3的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点： 1) 只要存在生成树，K r u s k a l算法总能产生一棵生成树； 2) 产生的生成树具有最小耗费。令G为任意加权无向图（即G是一个无向网络）。从1 2 . 11 . 3节可知当且仅当一个无向图连通时它有生成树。而且在Kruskal 算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E= 和| T |< n- 1。

现在来证明所建立的生成树T具有最小耗费。由于G具有有限棵生成树，所以它至少具有一棵最小生成树。令U为这样的一棵最小生成树， T与U都刚好有n- 1条边。如果T=U, 则T就具有最小耗费，那么不必再证明下去。因此假设T≠U，令k(k >0) 为在T中而不在U中的边的个数，当然k 也是在U中而不在T中的边的数目。 通过把U变换为T来证明U与T具有相同的耗费，这种转化可在k 步内完成。每一步使在T而不在U中的边的数目刚好减1。而且U的耗费不会因为转化而改变。经过k 步的转化得到的U将与原来的U具有相同的耗费，且转化后U中的边就是T中的边。由此可知， T具有最小耗费。每步转化包括从T中移一条边e 到U中，并从U中移出一条边f。边e 与f 的选取按如下方式进行：

1) 令e 是在T中而不在U中的具有最小耗费的边。由于k >0，这条边肯定存在。

2) 当把e 加入U时，则会形成唯一的一条环路。令f 为这条环路上不在T中的任意一条边。

由于T中不含环路，因此所形成的环路中至少有一条边不在T中。

从e 与f 的选择方法中可以看出， V=U+ {e} -{ f } 是一棵生成树，且T中恰有k- 1条边不在V中出现。现在来证明V的耗费与U的相同。显然，V的耗费等于U的耗费加上边e 的耗费再减去边f 的耗费。若e 的耗费比f 的小，则生成树V的耗费比U的耗费小，这是不可能的。如果e 的耗费高于f，在K r u s k a l算法中f 会在e 之前被考虑。由于f 不在T中，Kruskal 算法在考虑f 能否加入T时已将f 丢弃，因此f 和T中耗费小于或等于f 的边共同形成环路。通过选择e，所有这些边均在U中，因此U肯定含有环路，但是实际上这不可能，因为U是一棵生成树。e 的代价高于f 的假设将会导致矛盾。剩下的唯一的可能是e 与f 具有相同的耗费，由此可知V与U的耗费相同。

(3) 数据结构的选择及复杂性分析

为了按耗费非递减的顺序选择边，可以建立最小堆并根据需要从堆中一条一条地取出各边。当图中有e 条边时，需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边。边的集合T与G中的顶点一起定义了一个由至多n 个连通子图构成的图。用顶点集合来描述每个子图，这些顶点集合没有公共顶点。为了确定边（ u,v）是否会产生环路，仅需检查u,v 是否在同一个顶点集中（即处于同一子图）。如果是，则会形成一个环路；如果不是，则不会产生环路。因此对于顶点集使用两个F i n d操作就足够了。当一条边包含在T中时，2个子图将被合并成一个子图，即对两个集合执行U n i o n操作。集合的F i n d和U n i o n操作可利用8 . 1 0 . 2节的树（以及加权规则和路径压缩）来高效地执行。F i n d操作的次数最多为2e，Un i o n操作的次数最多为n- 1（若网络是连通的，则刚好是n- 1次）。加上树的初始化时间，算法中这部分的复杂性只比O (n+e) 稍大一点。

对集合T所执行的唯一操作是向T中添加一条新边。T可用数组t 来实现。添加操作在数组

的一端进行，因为最多可在T中加入n- 1条边，因此对T的操作总时间为O (n)。

总结上述各个部分的执行时间，可得图1 3 - 1 3算法的渐进复杂性为O (n+el o ge)。

(4) 实现

利用上述数据结构，图1 - 1 3可用C + +代码来实现。首先定义E d g e N o d e类（见程序1 3 - 6 )，它是最小堆的元素及生成树数组t 的数据类型。

程序13-6 Kruskal算法所需要的数据类型

template

class EdgeNode {

p u b l i c :

operator T() const {return weight;}

p r i v a t e :

T weight;//边的高度

int u, v;//边的端点

} ;

为了更简单地使用8 . 1 0 . 2节的查找和合并策略，定义了U n i o n F i n d类，它的构造函数是程序8 - 1 6的初始化函数，U n i o n是程序8 - 1 6的加权合并函数，F i n d是程序8 - 1 7的路径压缩搜索函数。

为了编写与网络描述无关的代码，还定义了一个新的类U N e t Wo r k，它包含了应用于无向网络的所有函数。这个类与U n d i r e c t e d类的差别在于U n d i r e c t e d类中的函数不要求加权边，而U N e t Wo r k要求边必须带有权值。U N e t Wo r k中的成员需要利用N e t w o r k类中定义的诸如B e g i n和N e x t Ve r t e x的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起构成了W N e t w o r k类（见程序1 3 - 7）。

程序13-7 WNetwork类

template

class WNetwork : virtual public Network

{

public :

virtual void First(int i, int& j, T& c)=0;

virtual void Next(int i, int& j, T& c)=0;

} ;

象B e g i n和N e x t Ve r t e x一样，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类中加入函数F i r s t与N e x t。现在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r k中派生而来。由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p h类需要访问U N e t w o r k的成员，所以这两个类还必须从U N e t Wo r k中派生而来。U N e t Wo r k : : K r u s k a l的代码见程序1 3 - 8，它要求将Edges() 定义为N e t Work 类的虚成员，并且把U N e t Wo r k定义为E d g e N o d e的友元）。如果没有生成树，函数返回f a l s e，否则返回t r u e。注意当返回true 时，在数组t 中返回最小耗费生成树。

程序13-8 Kr u s k a l算法的C + +代码

template

bool UNetwork::Kruskal(EdgeNode t[])

{// 使用K r u s k a l算法寻找最小耗费生成树

// 如果不连通则返回false

// 如果连通，则在t [ 0 : n - 2 ]中返回最小生成树

int n = Ve r t i c e s ( ) ;

int e = Edges();

/ /设置网络边的数组

InitializePos(); // 图遍历器

EdgeNode *E = new EdgeNode [e+1];

int k = 0; // E的游标

for (int i = 1; i <= n; i++) { // 使所有边附属于i

int j;

T c;

First(i, j, c);

while (j) { // j 邻接自i

if (i < j) {// 添加到达E的边

E[++k].weight = c;

E[k].u = i;

E[k].v = j;}

Next(i, j, c);

}

}

// 把边放入最小堆

MinHeap > H(1);

H.Initialize(E, e, e);

UnionFind U(n); // 合并/搜索结构

// 根据耗费的次序来抽取边

k = 0; // 此时作为t的游标

while (e && k < n - 1) {

// 生成树未完成，尚有剩余边

EdgeNode x;

H.DeleteMin(x); // 最小耗费边

e - - ;

int a = U.Find(x.u);

int b = U.Find(x.v);

if (a != b) {// 选择边

t[k++] = x;

U . U n i o n ( a , b ) ; }

}

D e a c t i v a t e P o s ( ) ;

H . D e a c t i v a t e ( ) ;

return (k == n - 1);

}

2. Prim算法

与Kr u s k a l算法类似，P r i m算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准则是：从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所有步骤中选择的边形成一棵树。相反，在Kruskal 算法中所有入选的边集合最终形成一个森林。

P r i m算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。然后往T中加入一条代价最小的边（ u , v）使Tè{ (u , v) }仍是一棵树，这种加边的步骤反复循环直到T中包含n- 1条边。注意对于边（ u , v），u、v 中正好有一个顶点位于T中。P r i m算法的伪代码如图1 -1 4所示。在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。图1 - 1 5显示了对图1-12a 使用P r i m算法的过程。把图1 - 1 4的伪代码细化为C + +程序及其正确性的证明留作练习（练习3 1）。


/ /假设网络中至少具有一个顶点

设T为所选择的边的集合，初始化T=

设T V为已在树中的顶点的集合，置T V= { 1 }

令E为网络中边的集合

w h i l e(E< > ) & & (| T | < > n-1) {

令（u , v）为最小代价边，其中u T V, v T V

i f（没有这种边） b re a k

E=E- { (u,v) } / /从E中删除此边

在T中加入边（ u , v）

}

if (| T | = =n- 1 ) T是一棵最小生成树

else 网络是不连通的，没有最小生成树

图13-14 Prim最小生成树算法


如果根据每个不在T V中的顶点v 选择一个顶点n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v) )的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间复杂性为O (n2 )。下一条添加到T中的边是这样的边：其cost (v, near (v)) 最小，且v T V。

3. Sollin算法

S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。

图1 - 6给出了初始状态为图1-12a 时，使用S o l l i n算法的步骤。初始入选边数为0时的情形如图13-12a 时,森林中的每棵树均是单个顶点。顶点1，2，.，7所选择的边分别是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的边是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，将这些边加入入选边的集合后所得到的结果如图1 3 - 1 6 a所示。下一步具有顶点集{ 1 , 6 }的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形成一棵生成树，构建好的生成树见图1 3 - 6 b。S o l l i n算法的C + +程序实现及其正确性证明留作练习

[ 本帖最后由 风花雪月 于 2006-10-10 01:09 编辑 ]

风花雪月

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <malloc.h>
   
4. 
   
5. 
   
6. 
   
7. typedef struct bitnode
   
8. {
   
9. char data;
   
10. struct bitnode *lchild, *rchild;
    
11. }bitnode, *bitree;
    
12. 
    
13. void createbitree(t,n)
    
14. bitnode ** t;
    
15. int *n;
    
16. {
    
17. char x;
    
18. bitnode *q;
    
19. *n=*n+1;
    
20. printf("\n Input %d DATA:",*n);
    
21. x=getchar();
    
22. if(x!='\n')
    
23. getchar();
    
24. if (x=='\n')
    
25. return;
    
26. q=(bitnode*)malloc(sizeof(bitnode));
    
27. q->data=x;
    
28. q->lchild=NULL;
    
29. q->rchild=NULL;
    
30. *t=q;
    
31. printf("This Address is:%o,Data is:%c,\n Left Pointer is:%o,Right Pointer is: %o",q,q->data,q->lchild,q->rchild);
    
32. createbitree(&q->lchild,n);
    
33. createbitree(&q->rchild,n);
    
34. return;
    
35. }
    
36. 
    
37. void visit(e)
    
38. bitnode *e;
    
39. {
    
40. printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);
    
41. }
    
42. 
    
43. void preordertraverse(t)
    
44. bitnode *t;
    
45. {
    
46. if(t)
    
47. {
    
48. visit(t);
    
49. preordertraverse(t->lchild);
    
50. preordertraverse(t->rchild);
    
51. return ;
    
52. }
    
53. else
    
54. return ;
    
55. }
    
56. 
    
57. void countleaf(t,c)
    
58. bitnode *t;
    
59. int *c;
    
60. {
    
61. if(t!=NULL)
    
62. {
    
63. if (t->lchild==NULL && t->rchild==NULL)
    
64. {
    
65. *c=*c+1;
    
66. }
    
67. countleaf(t->lchild,c);
    
68. countleaf(t->rchild,c);
    
69. }
    
70. return;
    
71. }
    
72. 
    
73. int treehigh(t)
    
74. bitnode *t;
    
75. {
    
76. int lh,rh,h;
    
77. if(t==NULL)
    
78. h=0;
    
79. else
    
80. {
    
81. lh=treehigh(t->lchild);
    
82. rh=treehigh(t->rchild);
    
83. h=(lh>rh ? lh:rh)+1;
    
84. }
    
85. return h;
    
86. }
    
87. 
    
88. main()
    
89. {
    
90. bitnode *t; int count=0;
    
91. int n=0;
    
92. printf("\n Please input TREE Data:\n");
    
93. createbitree(&t,&n);
    
94. printf("\n This is TREE Struct: \n");
    
95. preordertraverse(t);
    
96. countleaf(t,&count);
    
97. printf("\n This TREE has %d leaves ",count);
    
98. printf(",High of The TREE is: %d\n",treehigh(t));
    
99. }

复制代码

[ 本帖最后由 风花雪月 于 2006-10-10 01:10 编辑 ]