算法设计读书笔记
- 格式：doc
- 大小：333.00 KB
- 文档页数：9
算法设计与分析读书笔记
班级：计算1213 学号：201221121029 姓名：徐国强
算法设计的任务是对各类具体的问题设计高质量的算法，以及研究设计算法的一般规律和方法。
常用的算法设计方法主要有哈夫曼编码算法，分治法、动态规划法，贪婪法和回溯法，分支限界法等。
下面是学习到的几个算法的笔记.
读书笔记1：
1、问题描述
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
其压缩率通常在20%～90%之间。
哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。
一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。
有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。
若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。
前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。
这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。
译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。
为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。
从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。
图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。
在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。
每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。
给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。
C的一个前缀码编码方案对应于一棵二叉树T。
字符c 在树T中的深度记为d T(c)。
d T(c)也是字符c的前缀码长。
则平均码长定
义为：使平均码长达到最小的前缀码编码方案称为C 的最优前缀码。
2、构造哈弗曼编码
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
其构造步骤如下：
(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
(2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。
(3)假设编码字符集中每一字符c的频率是f(c)。
以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。
一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。
经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。
2.分治法读书笔记：
问题描述：
设有n=2^k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：
(1)每个选手必须与其他n-1个选手各赛一次；
(2)每个选手一天只能参赛一次；
(3)循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
其中1≤i≤n，1≤j≤n-1。
8个选手的比赛日程表如下图：
算法思路：按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
如上图，所列出的正方形表是8个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分
别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
算法步骤：
(1)用一个for循环输出日程表的第一行for(int i=1;i<=N;i++) a[1][i] = i
(2)然后定义一个m值，m初始化为1，m用来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置。
(3)用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。
for (ints=1;s<=k;s++) N/=2;
(4)用一个for循环对③中提到的每一部分进行划分
for(intt=1;t<=N;t++)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分
同理，对第二部分（即三四行），划分为两部分，第三部分同理。
(5)最后，根据以上for循环对整体的划分和分治法的思想，进行每一个单元格的填充。
填充原则是：对角线填充
for(int i=m+1;i<=2*m;i++) //i控制行
for(int j=m+1;j<=2*m;j++) //j控制列
{
a[i][j+(t-1)*m*2]= a[i-m][j+(t-1)*m*2-m];/*右下角的值等于左上角的值*/
a[i][j+(t-1)*m*2-m] =a[i-m][j+(t-1)*m*2];/*左下角的值等于右上角的值*/
}
运行过程：
(1)由初始化的第一行填充第二行
(2)由s控制的第一部分填完。
然后是s++，进行第二部分的填充
(3)最后是第三部分的填充
3，分支限界法：
问题描述
印刷电路板将布线区域划分成n×m个方格如图a所示。
精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。
在布线时，电路只能沿直线或直角布线，如图b所示。
为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。
一个布线的例子：图中包含障碍。
起始点为a，目标点为b。
算法思想
解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。
与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。
接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。
这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。
即加入剪枝的广度优先搜索。
