组合算法概论

b · 发表于 2004-5-28 04:07:19

<

>组合算法概论(A Brief Introduction to Combinatorial Algorithm)
组合算法是算法分析学当中非常重要的一个分支，关于它在计算机科学的地位我就不敖述了，下面为大家整理了整个材料，算法是我收集的，只是分门别类简单介绍一下，然后把我的材料做了个整理，大家收藏吧，感觉挺有用的，费了我好长时间和精力呀，我现在准备考研了，没有太多时间发很多经典文章了，这片算是大部头了。
关于组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。下面我们着重谈谈几个有代表性的组合算法：
单纯形法：
这是一种线性规划算法，由G.B.Dantzig在1947年提出，后来由他和其他的学者又提出了单纯形法的变形和改进。这些被实践证明都是行之有效的，线性规划研究线性目标函数在一组线性等式与线性不等式约束下的极值问题。这本来是连续问题，Dantzig发现线性规划问题的可行解集（即满足约束条件的点的全体）是一个超多面体。如果它的最优解存在，那么这个最优解一定可以在超多面体的一个顶点取到。由于超多面体的顶点只有有限个，从而使线性规划成为一个组和优化问题。单纯形法是按照一定的规则，从可行解集的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。尽管单纯形法一直使用得很好，但是在最坏情况下它需要指数运行时间，从而使线性规划问题是否属于P类一度成为人们关心的问题。后来的椭球算法和投影算法都很好的解决了这个问题。
排序和检索：
这两部分应当是大家比较熟悉的，所谓排序，就是将给定的元素序列按照某种顺序关系重新排列成有序序列。例如将n个数组成的序列按照从小到大的顺序重新排列；将n个英语单词组成的的序列按照字典顺序重新排列。所谓检索，就是在给定的集合中查找某个特定的元素或是元素组。排序和检索已经成为计算机科学技术中最基本、使用最频繁的算法。下面我们专门谈谈排序算法（sorting algorithm）。
在讨论此种算法时，数据通常是指由若干记录组成的文件，每个记录包含一个或多个数据项，其中能够标志该记录的数据项称为键码。给定一文件的n个记录{R1,R2,…,Rn}及其相应的键码的集合{K1,K2,…,Kn}。所谓排序算法就是在数据处理中将文件中的记录按键码的一定次序要求排列起来的算法。若待排序的文件能够同时装入计算机的主存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，有一部分必须放在外存上，则称此类排序问题为外部排序。当待排序的文件中包含有一些相同键码的记录时，如果经过排序后这些相同的键码的记录的相对次序仍然保持不变，则相应的排序算法是稳定的，否则为不稳定的。如果排序算法设计成单处理机完成的，则此排序算法称为串行（或顺序）排序算法；如果排序算法时设计成多处理机实现的，则称为并行排序算法。
首先谈谈内部排序：内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。
使有序区中记录的数目增加一个或几个的操作称为一趟排序。
逐步扩大记录有序序列长度的方法大致有下列几类：
一．插入排序
假设在排序过程中，记录序列R[1..n]的状态为：
则一趟直接插入排序的基本思想为：将记录R
插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。
显然，完成这个“插入”需分三步进行：
1．查找R的插入位置j+1；
2．将R[j+1..i-1]中的记录后移一个位置；
3．将R复制到R[j+1]的位置上。
[I]直接插入排序
利用顺序查找实现“在R[1..i-1]中查找R的插入位置”的插入排序。
注意直接插入排序算法的三个要点：
1．从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；
 R[0] = R; // 设置“哨兵”
 for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找
 return j+1; // 返回R的插入位置为j+1
2．对于在查找过程中找到的那些关键字不小于R.key的记录，可以在查找的同时实现向后移动；
 for (j=i-1; R[0].key<R[j].key; --j);
 R[j+1] = R[j]
3．i = 2，3，…, n, 实现整个序列的排序。
 template<class Elem>
 void InsertionSort ( Elem R[], int n)
 {
 // 对记录序列R[1..n]作直接插入排序。
 for ( i=2; i<=n; ++i )
 {
 R[0] = R; // 复制为监视哨
 for ( j=i-1; R[0].key < R[j].key; --j )
 R[j+1] = R[j]; // 记录后移
 R[j+1] = R[0]; // 插入到正确位置
 }
 } // InsertSort
时间分析：
实现排序的基本操作有两个：
（1）“比较”序列中两个关键字的大小；
（2）“移动”记录。
对于直接插入排序：
[II]折半插入排序
 因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R的插入位置”，如此实现的插入排序为折半插入排序。其算法如下：
 template<class Elem>
 void BiInsertionSort (Elem R[]， int n)
 {
 // 对记录序列R[1..n]作折半插入排序。
 for ( i=2; i<=L.length; ++i )
 {
 R[0] = R; // 将R暂存到R[0]
 low = 1; high = i-1;
 while (low<=high)
 { //在R[low..high]中折半查找插入的位置
 m = (low+high)/2; // 折半
 if (R[0].key < R[m].key))
 high = m-1; // 插入点在低半区
 else
 low = m+1; // 插入点在高半区
 }
 for ( j=i-1; j>=high+1; --j )
 R[j+1] = R[j]; // 记录后移
 R[high+1] = R[0]; // 插入
 }
 } // BInsertSort
折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。
[III]表插入排序
为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。
算法描述如下：
 template<class Elem>
 void LInsertionSort (Elem SL[]， int n)
 {
 // 对记录序列SL[1..n]作表插入排序。
 SL[0].key = MAXINT ;
 SL[0].next = 1; SL[1].next = 0;
 for ( i=2; i<=n; ++i )
 for ( j=0, k = SL[0].next;
 SL[k].key <= SL.key ; j = k, k = SL[k].next )
 { SL[j].next = i; SL.next = k; }
 // 结点i插入在结点j和结点k之间
 }// LinsertionSort
关于如在排序之后调整记录序列：
算法中使用了三个指针:
其中：p指示第i个记录的当前位置；
 i指示第i个记录应在的位置；
 q指示第i+1个记录的当前位置
 template<class Elem>
 void Arrange ( SLinkListType SL[ ], int n ) {
 // 根据静态链表SL中各结点的指针值调整
 // 记录位置，使得SL中记录按关键字非递减
 // 有序顺序排列
 p = SL[0].next;// p指示第一个记录的当前位置
 for ( i=1; i<n; ++i ) {
 // SL[1..i-1]中记录已按关键字有序排列，
 // 第i个记录在SL中的当前位置应不小于i
 while (p<i) p = SL[p].next;
 // 找到第i个记录，并用p指示
 // 其在SL中当前位置
 q = SL[p].next; // q指示尚未调整的表尾
 if ( p!= i ) {
 SL[p]←→SL; // 交换记录，使第i个
 // 记录到位
 SL.next = p; // 指向被移走的记录，
 // 使得以后可由while循环找回
 }
 p = q; // p指示尚未调整的表尾，
 // 为找第i+1个记录作准备
 }
 } // Arrange
二．交换排序
通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]起泡排序
假设在排序过程中，记录序列R[1..n]的状态为：n-i+1
则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。
算法描述：
 template <class Elem>
 void BubbleSort(Elem R[], int n)
 {
 // i 指示无序序列中最后一个记录的位置
 i = n;
 while (i > 1) {
 lastExchangeIndex = 1;
 for (j = 1; j < i; j++) {
 if (A[j+1] < A[j]) {
 Swap(A[j],A[j+1]);
 lastExchangeIndex = j;
 } //if
 } // for
 i = lastExchangeIndex;
 } // while
 } // BubbleSort
起泡排序的结束条件为：最后一趟没有进行“交换”。
从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。我们可以设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。

b · 发表于 2004-5-28 04:07:36

[II]一趟快速排序
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且R[j].key≤ R.key ≤ R[j].key
 (s≤j≤i-1) 枢轴 (i+1≤j≤t)
例如:关键字序列
 52, 49, 80, 36, 14, 58, 61, 97, 23, 75
调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75
其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证R[high].key≥52，而R[low].key≤52,否则进行记录的“交换”。
算法描述如下:
 template<class Elem>
 int Partition (Elem R[], int low, int high) {
 // 交换记录子序列R[low..high]中的记录，使
 // 枢轴记录到位，并返回其所在位置，此时，
 // 在它之前（后）的记录均不大（小）于它
 pivotkey = R[low].key;
 // 用子表的第一个记录作枢轴记录
 while (low<high) {
 // 从表的两端交替地向中间扫描
 while (low<high && R[high].key>=pivotkey)
 --high;
 R[low]←→R[high];
 // 将比枢轴记录小的记录交换到低端
 while (low<high && R[low].key<=pivotkey)
 ++low;
 R[low]←→R[high];
 // 将比枢轴记录大的记录交换到高端
 }
 return low; // 返回枢轴所在位置
 } // Partition
容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。
将上述“一次划分”的算法改写如下：
 template<class Elem>
 int Partition (Elem R[], int low, int high) {
 // 交换记录子序列R[low..high]中的记录，使
 //枢轴记录到位，并返回其所在位置，此时，
 // 在它之前（后）的记录均不大（小）于它
 R[0] = R[low];
 // 用子表的第一个记录作枢轴记录
 pivotkey = R[low].key; // 枢轴记录关键字
 while (low < high) {
 // 从表的两端交替地向中间扫描
 while(low<HIGH&& R[high].key>=pivotkey)
 --high;
 R[low] = R[high];
 // 将比枢轴记录小的记录移到低端
 while (low<high && R[low].key<=pivotkey)
 ++low;
 R[high] = R[low];
 // 将比枢轴记录大的记录移到高端
 }
 R[low] = R[0]; // 枢轴记录到位
 return low; // 返回枢轴位置
 } // Partition
[III]快速排序
在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。 快速排序的算法描述如下:
 template<class Elem>
 void QSort (Elem R[], int low, int high) {
 // 对记录序列R[low..high]进行快速排序
 if (low < high-1) { // 长度大于1
 pivotloc = Partition(L, low, high);
 // 将L.r[low..high]一分为二
 QSort(L, low, pivotloc-1);
 // 对低子表递归排序，pivotloc是枢轴位置
 QSort(L, pivotloc+1, high);
 // 对高子表递归排序
 }
 } // QSort

 template<class Elem>
 void QuickSort(Elem R[], int n) {
 // 对记录序列进行快速排序
 QSort(R, 1, n);
 } // QuickSort
快速排序的时间分析
假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间
T(n) = Tpass(n)+T(k-1)+T(n-k)
其中 Tpass(n)为对n个记录进行一次划分所需时间，若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同，由此可得快速排序所需时间的平均值为：
设 Tavg(1)≤b
则可得结果
通常，快速排序被认为是在所有同数量级O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。
为避免出现这种情况，需在进行快排之前，进行“予处理”，即：比较 R(s).key, R(t).key和R[(s+t)/2.key，然后取关键字为“三者之中”的记录为枢轴记录。
三．选择排序
从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;
[I]简单选择排序
假设排序过程中，待排记录序列的状态为：
并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列。
简单选择排序的算法描述如下：
template<CLASS Elem>
void SelectSort (Elem R[], int n ) {
// 对记录序列R[1..n]作简单选择排序。
for (i=1; i<N; ++i) { // 选择第i小的记录，并交换到位
j = SelectMinKey(R, i);
 // 在R[i..n]中选择key最小的记录
if (i!=j) R←→R[j];
 // 与第i个记录交换
}
} // SelectSort
时间性能分析
 对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为

移动记录的次数，最小值为0, 最大值为3(n-1)
[II]堆排序

b · 发表于 2004-5-28 04:07:55

堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。
堆的定义:
堆是满足下列性质的数列{r1, r2, …，rn}：
 或
若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。
由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。
堆排序的算法如下所示：
template<CLASS Elem>
void HeapSort ( Elem R[], int n ) {
// 对记录序列R[1..n]进行堆排序。
for ( i=n/2; i>0; --i )
 // 把R[1..n]建成大顶堆
HeapAdjust ( R, i, n );
for ( i=n; i>1; --i ) {
R[1]←→R;
 // 将堆顶记录和当前未经排序子序列
 // R[1..i]中最后一个记录相互交换
HeapAdjust(R, 1, i-1);
 // 将R[1..i-1] 重新调整为大顶堆
}
} // HeapSort
其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。
Template<CLASS Elem>
void HeapAdjust (Elem R[], int s, int m) {
// 已知R[s..m]中记录的关键字除R.key之
// 外均满足堆的定义，本函数调整R 的关
// 键字，使R[s..m]成为一个大顶堆（对其中
// 记录的关键字而言）
rc = R;
for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选
if ( j<M if ( rc.key >= R[j].key ) break; // rc应插入在位置s上
R = R[j]; s = j;
}
R = rc; // 插入
} // HeapAdjust
堆排序的时间复杂度分析：
1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);
2．对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n;
3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过
2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n)
因此，堆排序的时间复杂度为O(nlogn)
四．归并排序：是通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。
 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。
“归并”算法描述如下：
template<CLASS Elem>
void Merge (Elem SR[], Elem TR[], int i, int m, int n) {
// 将有序的SR[i..m]和SR[m+1..n]归并为
// 有序的TR[i..n]
for (j=m+1, k=i; i<=m && j<=n; ++k)
{ // 将SR中记录由小到大地并入TR
if (SR.key<=SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m) TR[k..n] = SR[i..m];
 // 将剩余的SR[i..m]复制到TR
if (j<=n) TR[k..n] = SR[j..n];
 // 将剩余的SR[j..n]复制到TR
} // Merge
归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。
这是一种自顶向下的分析方法：
如果记录无序序列R[s..t]的两部分R[s..(s+t)/2]和R[(s+t)/2+1..t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。
template<CLASS Elem>
void Msort ( Elem SR[], Elem TR1[], int s, int t ) {
// 将SR[s..t]进行2-路归并排序为TR1[s..t]。
if (s==t) TR1 = SR;
else {
m = (s+t)/2;
// 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
Msort (SR, TR2, s, m);
 // 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
//递归地SR[m+1..t]归并为有序的TR2[m+1..t]
Merge (TR2, TR1, s, m, t);
// 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
} // MSort

template<CLASS Elem>
void MergeSort (Elem R[]) {
// 对记录序列R[1..n]作2-路归并排序。
 MSort(R, R, 1, n);
} // MergeSort

容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。
五．基数排序：借助“多关键字排序”的思想来实现“单关键字排序”的算法。
[I]多关键字的排序
假设有n个记录……的序列
 { R1, R2, …，Rn}
每个记录Ri中含有d个关键字(Ki0, Ki1, …,Kid-1),则称上述记录序列对关键字(Ki0, Ki1, …,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1≤i<J≤N)都满足下列(词典)有序关系： (Ki0, Ki1, …,Kid-1)< (Kj0, Kj1, …,Kjd-1)
其中K0被称为“最主”位关键字，Kd-1被称为 “最次”位关键字。
实现多关键字排序通常有两种作法:
最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，…，依次类推，直至最后对最次位关键字排序完成为止。
最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。

b · 发表于 2004-5-28 04:08:26

例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:
[II]链式基数排序
假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。
对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。
例如：对下列这组关键字
{209, 386, 768, 185, 247, 606, 230, 834, 539 }
首先按其“个位数”取值分别为0, 1, …，9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起;然后按其“十位数” 取值分别为0, 1, …，9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。
在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：
１．待排序记录以指针相链，构成一个链表；
２．“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；
３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;
４．对每个关键字位均重复2)和3)两步。
例如：
p→369→367→167→239→237→138→230→139
第一次分配得到
f[0]→230←r[0]
f[7]→367→167→237←r[7]
f[8]→138←r[8]
f[9]→369→239→139←r[9]
第一次收集得到
p→230→367→167→237→138→368→239→139
第二次分配得到
f[3]→230→237→138→239→139←r[3]
f[6]→367→167→368←r[6]
第二次收集得到
p→230→237→138→239→139→367→167→368
第三次分配得到
f[1]→138→139→167←r[1]
f[2]→230→237→239←r[2]
f[3]→367→368←r[3]
第三次收集之后便得到记录的有序序列
p→138→139→167→230→237→239→367→368
我们在技术排序中需要注意的是：
１．“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；
２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。
基数排序的时间复杂度为O(d(n+rd))。
其中，分配为O(n);收集为O(rd)(rd为“基”),d为“分配-收集”的趟数。
下面我们比较一下上面谈到的各种内部排序方法
首先，从时间性能上说：
1. 按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有，基数排序。
2. 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
其次，从空间性能上说：
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2. 快速排序为O(logn)，为栈所需的辅助空间;
3. 归并排序所需辅助空间最多，其空间复杂度为O(n);
4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。
再次，从排序方法的稳定性能上说：
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。对于不稳定的排序方法，只要能举出一个实例说明即可。我们需要指出的是：快速排序和堆排序是不稳定的排序方法。
我们再谈谈关于“排序方法的时间复杂度的下限”
这里讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。
例如，对三个关键字进行排序的判定树如下：
 K1<K2 
 K1<K3 
 K2< K3 K2<K1<K3 
K3<K2<K1 K2<K3<K1 K3<K1<K2 K1<K3<K2 描述排序的判定树有两个特点：
１．树上的每一次“比较”都是必要的;
２．树上的叶子结点包含所有可能情况。
则由上图所示“判定树的深度为4”可以推出“至多进行三次比较”即可完成对三个关键字的排序。反过来说，由此判定树可见，考虑最坏情况，“至少要进行三次比较”才能完成对三个关键字的排序。对三个关键字进行排序的判定树深度是唯一的。即无论按什么先后顺序去进行比较，所得判定树的深度都是3。当关键字的个数超过3之后，不同的排序方法其判定树的深度不同。例如，对4个关键字进行排序时，直接插入的判定树的深度为6, 而折半插入的判定树的深度为5。
可以证明，对4个关键字进行排序，至少需进行5次比较。因为，4个关键字排序的结果有4!=24种可能，即排序的判定树上必须有24个叶子结点，其深度的最小值为6。
一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于log2(n!) +1, 则对n个关键字进行排序的比较次数至少是log2(n!) 。利用斯蒂林近似公式log2(n!)  nlog2n
所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为O(nlogn)。
下面我们再来谈谈外部排序：
常见的外部排序有：
磁盘排序和磁带排序，之所以这么分是因为外排序不但与排序的算法有关，还与外存设备的特征有关。结合外存设备特征，大体上可分为顺序存取（如磁带）和直接存取（如磁盘）两大类。磁带排序时间主要取决于对带的读写。（这里只是交代一下，实际上正如大家知道的，基本上现在已经淘汰了磁带存储的方式）需要指出的是外部排序的这两种方式的工作过程是一致的，外部排序的基本过程由相对独立的两个步骤组成：
１．按可用内存大小，利用内部排序的方法，构造若干(记录的)有序子序列，通常称外存中这些记录有序子序列为“归并段”;
２．通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。
例如：假设有一个含10,000个记录的磁盘文件，而当前所用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。
假设进行2路归并(即两两归并)，则
第一趟由10个归并段得到5个归并段;
第二趟由 5 个归并段得到3个归并段;
第三趟由 3 个归并段得到2个归并段;
最后一趟归并得到整个记录的有序序列。
我们来分析上述外排过程中访问外存(对外存进行读/写)的次数：假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。
由此，对上述例子而言，
1) 求得10个初始归并段需访问外存100次;
2) 每进行一趟归并需访问外存100次;
3) 总计访问外存 100 + 4  100 = 500次。
外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间，显然，除去内部排序的因素外，外部排序的时间取决于逐趟归并所需进行的“趟数”。
例如，若对上述例子采用5路归并，则只需进行2趟归并，总的访问外存的次数将压缩到 100 + 2  100 = 300 次
一般情况下，假设待排记录序列含m个初始归并段，外排时采用k路归并，则归并趟数为 logkm，显然，随之k的增大归并的趟数将减少，因此对外排而言，通常采用多路归并。k的大小可选，但需综合考虑各种因素。
上面谈的都是假设在单处理机上完成的工作，下面将谈谈并行排序：
并行排序：是指利用多台处理机（并行机）进行的排序，其目的主要是为了提高速度。并行排序算法虽然和前面谈到的单处理机上的串行排序算法有不少相似之处，但不能认为它只是它是串行算法的简单推广和扩充。它的最大特点之一就是他和并行计算机的体系结构密切相关，不同体系结构导致不同加速和不同设计风格的并行排序算法。
图与网络优化算法：
 组合算法中内容最丰富的部分就是图与网络优化算法。图论中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。
求最小生成树的Kruskal算法
由于这个是大家都熟悉的，我只简单的说说：为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。Kruskal算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。算法如下:
构造非连通图 ST=( V,{ } );
k = i = 0;
while (k<N-1) { ++i;
从边集 E 中选取第i条权值最小的边(u,v);
若(u,v)加入ST后不使ST中产生回路，
则 输出边(u,v);
 k++;
}

b · 发表于 2004-5-28 04:09:12

求最短路径的Dijkstra算法：
Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(│V│2)，下面是一段精确的描述（本段引自MIT的课程主页，不翻译了，保持原作）中文描述一般的书上都会有：
1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2.
2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
4. Let Si+1 = Si cup {ui+1}.
5. Replace i by i+1. If i=│V│-1 then stop, otherwise go to step 2.
6. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2.
7. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
8. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
9. Let Si+1 = Si cup {ui+1}.
10. Replace i by i+1. If i=│V│-1 then stop, otherwise go to step 2.
求二部图最大匹配（指派问题）的匈牙利算法：
谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ >= │A│
匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束，否则进行第3步；
3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ；
4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2；
5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2；
6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}，转4；
关于求网络最大流和最小割的标号算法：
给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s和汇点t，现在假设在s处有一个水源，t处有一个蓄水池，问从s到t的最大水流量是多少。这就叫做网络流问题。用数学语言描述就是：
设G=(V,E)是一个流网络，设c(u, v)>＝0 表示从u到v的管道的流量上限。设s为源，t为汇。G的流是一个函数f: V×V →R，且满足下面三个特征：
1. 容量限制：对于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v)
2. 斜对称性：对于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u)
3. 流的会话：对于所有的 u ∈ V - {s, t}，要求∑ f(u, v) = 0；v∈V
f(u,v)称为从结点u到v的网络流，它可以为正也可以为负。流 f 的值定义为：
│f│ = ∑ f(s, v)
 v∈V
即从源出发的所有流的总和。
最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。
寻找最大流的基本方法是Ford-Fulkerson方法，该方法有多种实现，其基本思想是从某个可行流F出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试图寻找关于他的可改进路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。
注意到每条边的单位流量费用B(i,j)≥0，所以F=0必是流量为0的最小费用流，这样总可以
从F=0出发求出最小费用最大流。一般的，设已知F是流量V(F)的最小费用流，余下的问题就是如何去寻找关于F的最小费用可改进路。为此我们将原网络中的每条弧<U,V>变成两条方向相反的弧：
1。前向弧<U,V>，容量C和费用B不变，流量F为0；
2。后向弧<V,U>，容量C为0，费用为-B，流量F为0；
每一个顶点上设置一个参数CT，表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的最小费用可改进路时，则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最小费用可改进路时前，源点的CT为0，其它顶点的CT为+∞。
设cost为流的运输费用，初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路，则通过cost ← cost + ∑B(e)*d, （其中e∈P,d为P的可改进量）来累积流的运输费用
的增加量。显然，当求出最小费用最大流时，cost便成为最大流的运输费用了。
另外设置布尔变量break为最小费用可改进路的延伸标志，在搜索了网络中的每一个顶点后
，若break=true表示可改进路还可以延伸，还需要重新搜索网络中的顶点；否则说明最小费
用的可改进路已经找到或者最大流已经求出。
下面是算法的伪代码：
cost ← 0;
repeat
可改进路撤空；
设源点的CT值为0并进入可改进路；
repeat
break ← false;
for u ←1 to N do
 begin
 分析U出发的所有弧<U,V>;
 if (<U,V>的流量可改进）and(源点至U有通路)and(U的CT值+<U,V>的费用 < V的CT值) then
 begin
 break ← true;
 V的CT值 ← U的CT值+<U,V>的费用；
 V进入可改进路经并为之标号；
 end if
 end for
until break=false
if 汇点已标号 then
begin
 从汇点出发倒向修正可改进路的流量；
 cost ← cost + ∑B(e)*d（其中e∈P,d为P的可改进量）；
end if
until 汇点未标号；
可见，上述的算法和求最大流的Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE)，其中V是节点数目，E是边数目。
其他的就不详述了，大家感兴趣的可以查阅TAOCP或者是算法导论的相关内容。

b · 发表于 2004-5-28 04:09:33

贪心法与拟阵：
贪心法是求解关于独立系统组合优化问题的一种简单算法，求最小生成树的Kruskal算法就是一种贪心算法。但是贪心法并不总能找到最优独立集。贪心法能求得最优独立集的充分必要条件是L为一个拟阵。事实上，求最大生成树是关于拟阵的组合优化问题，而二部图的所有匹配构成的独立系统U不是拟阵。
贪心法的基本思路是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
　　求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
穷举搜索：
组合算法要解决的问题只有有限种可能，在没有跟好算法时总可以用穷举搜索的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况，既减少了搜索量，又保证了不漏掉最优解。这方面怒火之炮写过文章，我认为没必要敖述了。
分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：
1) 先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找
一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费
的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个
E-节点是具有最大收益的活节点。
动态规划：
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision
process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究
多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了
子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
1．划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干
个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规
划求解。
2．选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示
出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移
有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是
反过来做，根据相邻两段的各状态之间的关系来确定决策。
3．写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式
化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较
简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。
分治法：
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解
决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1 < k ≤ n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
其基本步骤是：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
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)子问题的思想，它几乎总是
比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案，或者是合并方案不明显，究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
 其他的一些经典的算法，如快速傅里叶变换，大家都非常熟悉，这里就不再涉及。如果想深入学习不妨参考San Diego 州立大学的相关课程主页
<a href="http://www.eli.sdsu.edu/courses/fall95/cs660/notes/" target="_blank" >http://www.eli.sdsu.edu/courses/fall95/cs660/notes/</A>
组合算法的设计是一门艺术，需要高度的技巧和灵感。算法分析的任务是分析算法的优劣，算法分析的任务是分析算法的优劣，主要是讨论算法的时间复杂性和空间复杂性。它的理论基础是组合分析，包括计数和枚举。计算复杂性理论，特别是NP完全性理论，与组合算法是紧密相关的。NP完全性概念的提出，正是为了刻画包括旅行商问题、图着色问题、图着色问题、整数规划等一大批组合问题的计算难度。计算复杂性理论研究算法在时间和空间限制下的能力以及问题的难度，使组合算法的研究有了更加清晰的框架，将组合算法的研究提高到一个新的水平。

wgd243 · 发表于 2004-8-15 18:51:40

<

>thanks

飞云0616 · 发表于 2004-8-17 22:53:35

<

>我还没看
<

>谢谢楼主的工作
<

>我一定会仔细看一遍的

wenhairong · 发表于 2004-8-18 04:14:46

<

>thinks<

>经典

cloud_drift · 发表于 2004-8-18 22:19:26

[em08]楼主好样的！

		自动登录	找回密码
密码			注-册-帐-号

组合算法概论

浏览过的版块