【数据结构与算法分析】第十章 算法技巧设计
【数据结构与算法分析】第十章 算法技巧设计
1.贪婪算法
三种贪婪算法：
Dijkstra算法、Prim算法、Kruskal算法
贪婪算法的工作原理：
分阶段工作，在每一个阶段，选择最优的，不考虑将来的后果。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
1.1 霍夫曼编码
贪婪算法的第二个应用，称为文件压缩。用于降低文件的总的所需的比特数。
例：一个文件中有10个a,15个e、12个i，3个s、4个t、13个空格和1个newline，总比特数为174
一般降低文件大小的策略：让代码的长度从字符到字符是变化不等的，使频率高的字符其代码短。
哈夫曼算法
基本定义：
-
一棵树的权等于它的树叶的频率之和。
-
每个字符代码的长度是否不同不重要，只要没有字符代码是别的字符代码的前缀即可，这种编码为前缀码。
-
trie树：每个字符通过从根节点开始用0指示左分支，用1指示右分支。
哈夫曼算法过程：假设字符个数为C，每个都选取最小权的两棵树进行合并，形成新树，进行C-1次后，得到最优哈夫曼编码树。称为贪婪算法原因是每个阶段都选择最小的两棵树，未进行全局的考虑
具体过程如下：（1）取最小权为s和nl进行第一个合并，产生新树T1
（2）取最小权T1和t进行第二次合并，取最小权T2和a进行第三次合并
（3）取最小权i和sp进行第四次合并
（4） 取最小权T3和e进行第五次合并
（5）取最小权T4和T5进行第六次合并
1.2近似装箱问题
装箱问题分为联机装箱和脱机装箱两种。例：对一批大小为0.2、0.5、0.4、0.7、0.1、0.3、0.8的货物进行装箱，箱子大小为1
联机算法
下项合适算法
当处理任何一项物品时。检查它是否能装进刚刚装进物品的同一个箱中，不行就开辟一个新箱
首次适合算法
依次扫描前面的箱子把新的物品放在能盛下它的第一个箱子中。
最佳适合算法
该算法是把一项新物品放到所有箱子中能容纳它的最满的箱子中。
脱机算法
将各项物品排序，把最大的物品放在最先，应用首次适合算法或最佳适合算法，得到首次适合递减算法和最佳适合递减算法。
2.分治算法
分治算法要求最优子结构 和独立(非重叠)子问题，算法通常由两部分组成divide-conquer。思路是递归解决较小的子问题，然后从子问题的解构建原问题的解。分治算法通常至少含有两个内部递归
伪代码：算法描述语言
最近点问题：
naive算法花费O(N*N)时间复杂度，可以将点空间划分为两半，递归的解两个子问题，然后进行合并
选择问题：
五分化中项的中项方法系统开销太大，根本不实用。
整数相乘：
不仅要进行子问题的划分，还要通过合并变换减少实际的乘法次数
矩阵相乘：
两个矩阵的乘法：
矩阵乘法代码实现：
void MatriMulitiply(Matrix A,Matrix B,Matrix C,int N)
{
int i,j,k;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
C[i][j]=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
for(k=0;k<N;k++)
C[i][j]+=A[i][k]*B[k][j];
}
3.动态规划
通常递归算法会重复一些子问题，造成不必要的性能下降。动态规划的思路是弃用递归，将子问题的答案系统的记录在中间表（table）中。其特点是最优子结构和重叠子问题。
4.随机化算法
好的随机化算法没有不好的输入，而只有不好的随机数（考虑快排枢纽元的选取）。
4.1随机数发生器
实现真正的随机数生成器是不可能的，依赖于算法，都是些伪随机数。
产生随机数最简答的方法是线性同余生成器
序列的最大生成周期为M-1，还需要仔细选择A，贸然修改通常意味着失败。需要注意的是，直接按照前面公式实现有可能发生溢出大数的现象，通常需要进行变换。
4.2跳跃表
借助随机化算法实现以O(NlogN)期望时间支持查找和插入操作数据结构。本质是多指针链表。当查找时，从跳跃表节点的最高阶链开始寻找；当插入元素时，其阶数是随机的（抛硬币直到正面朝上时的总次数）
4.3素性测试
某些密码方案依赖于大数分解的难度。费马小定理（下1）：如果定理宣称一个数不是素数，那这个数肯定不是素数；若宣称是素数的话，有可能不是素数。可借助平方探测的特殊情况（下2）加以判断。
5.回溯算法
虽然分析回溯算法的复杂度可能很高，但实际上的性能却很好，明显优于穷举法。有时还会借助裁剪的方法进一步降低复杂度。与分支限界法不同，回溯算法通常是深度优先递归的搜索所有解，而分支限界通常是广度优先，找出满足条件的一个解。