哈工程算法期末考试知识点(可缩印)

《哈工程算法期末考试知识点(可缩印)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、简答题:算法分类按照问题类型分类:查找/排序/串处理/图/组合问题/几何问题/数值问题等按照算法技术分类:直接法/分治技术/贪婪技术/动态规划/近似算法/分支定界法/回溯法/线性规划/网络流/概率算法/并行算法等算法评价常见的多项式阶有:O(1)

2、的适用条件:1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。大整数乘法:XY=ac2^n+((a-c)(b-d)+ac+bd)2^n/2+bdStrassen矩阵乘法使用动态规划方法的基本条件:–最优子结构•当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构•缩小子问题的集合,只要哪些优化问题包含了优化子问题,降低实现复杂性–重叠子

3、问题•在问题的求解过程中,很多子问题的解被多次重复使用–无后效性•即一个问题被划分阶段后，阶段I中的状态只能由i+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系动态规划法的求解步骤:•找出最优解的性质，并刻划其结构特征。•递归地定义最优值。•以自底向上的方式计算出最优值。•根据计算最优值时得到的信息，构造最优解矩阵连乘:最长公共子序列:设序列X=和Y=的最长公共子序列是Z=如果xm=ynzk=xm=yn是和

4、-1>的最长公共子序列如果xm¹yn且zk¹xm是和的最长公共子序列如果xm¹yn且zk¹yn是和的最长公共子序列凸多边形的最优三角剖分:0-1背包问题:贪心法适合的问题：它有n个输入，而他的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的。那些使目标函数取极值的可行解，成为最优解。Greedy算法的处理流程•1、读入一个问题•2、进行贪心排序•3、处理问题

5、•4、综合结果并输出Greedy算法产生优化解的条件:贪心选择性质和最优子结构性质贪心与动态规划法的比较:动态规划：每一步作一个选择——依赖于子问题的解。Greedy方法：每一步作一个选择——不依赖于子问题的解。动态规划方法可用的条件①优化子结构②子问题相交性③子问题空间小Greedy方法可用的条件①优化子结构②Greedy选择性Greedy算法正确性证明方法:①证明算法所求解的问题具有优化子结构；②证明算法所求解的问题具有Greedy选择性；③算法按照②中的Greedy选择性进行局部优化选择回溯法的解题步骤:(1)针对所给问题，定义问题的解空间；(2

6、)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常见的两种分支限界法:（1）队列式(FIFO/LIFO)分支限界法按照队列先进先出（FIFO）或后进先出（LIFO）原则选取下一个结点为扩展结点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。分支限界法与回溯法的对比:证明题:凸多边形最优三角剖分:最优子结构性质证明：若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkv

7、n的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。0-1背包问题:0-1背包问题具有最优子结构性质活动选择问题引理.1.设S={1,2,…,n}是n个活动集合，[si，fi]是活动的起始终止时间，且f1<=f2<=…<=fn，S的活动选择问题的某个优化解包括活动1.证.设A是一个优化解，按结束时间排序A中活动，设其第一个活动为k，第二个活动为j.如果k=1

8、，引理成立.如果k≠1，令B=A-{k}∪{1},由于A中活动相容，且f1<=fk,B中活动相