----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------
第一章 绪论 1、重要特性 1.输入 2.输出 3.有穷性 4.确定性 5.可行性
2、描述算法的方法
1.自然语言：优点是直观易懂，缺点是容易出现二义性
2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言 3.程序设计语言：优点是计算机直接运行，缺点是抽象性差 4.伪代码：
3、递归算法分析 1.猜测技术
2.扩展递归技术 3.通用分治递归推式
cn?1? T(n)??k?aT(n/b)?cnn?1?O(nlogb)a?bk?aT(n)??O(nklogb)a?bk
?O(nk)a?bk?
第二章 NP完全理论
第三章 蛮力法
3.1 蛮力法的设计思想
a蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解; 关键——依次处理所有元素。
3.2 查找问题中的蛮力法 3.2.1 顺序查找O(n) 3.2.2串匹配问题 BF O(n*m) BMP O(n+m)
0j?1??next[j]??max{k|1?k?j&\t1t2?tk?1\?\tj?k?1tj?k?2?tj?1\}
?1else?----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------
BM O(n*m)
?m?jj?max{j|tj?c&1?j?m?1} dist(c)??melse?3.3 排序问题中的蛮力法 3.3.1 选择排序O(n)
2
3.3.2 起泡排序O(n) 3.4 组合问题中的蛮力法 3.4.1 生成排列对象O(n!)
n
3.4.2 生成子集O(2)
n
3.4.3 0/1背包问题O(2) 3.4.4 任务分配问题O(n!) 3.5 图问题中的蛮力法 3.5.1 哈密顿回路问题O(n!) 3.5.2 TSP问题O(n!)
3.6 几何问题中的蛮力法
2
3.6.1 最近对问题O(n)
3
3.6.2 凸包问题O(n)
3.7 实验项目——串匹配问题
第四章 分治法
4.1 分治法的设计思想
2
设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 步骤：（1）划分（2）求解子问题（3）合并
4.2 排序问题中的分治法 4.2.1 递归排序O(nlog2n) 4.2.2 快速排序O(nlog2n) 4.3 组合问题中的分治法
4.3.1 最大字段和问题O(nlog2n)
k
4.3.2棋盘覆盖问题O(4)
k
4.3.3 循环赛日程安排问题O(4) 4.4 几何问题中的分治法 4.4.1 最近对问题O(nlog2n) 4.4.2 凸包问题O(nlog2n) 4.5 实验项目——最近对问题
----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------
第五章 减治法
5.1 减治法的设计思想
原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。
5.2 查找问题中的减治法 5.2.1 折半查找O(log2n) 5.2.2 二叉查找树O(log2n) 5.3 排序问题中的减治法 5.3.1 堆排序O(log2n) 5.3.2 选择问题O(log2n) 5.4 组合问题中的减治法 5.4.1 淘汰塞冠军问题O(n) 5.4.2 假币问题O(log2n)
5.5 实验项目——8枚硬币问题
第六章 动态规划法
6.1动态规划法的设计思想
将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。 步骤：
将原始问题分解为相互重叠的子问题，确定动态规划函数； 求解子问题，填表；
根据表，自底向上计算出原问题的解。
6.2 图问题中的动态规划法
n
6.2.1 TSP问题O(2)
d(i,V')?min{cik?d(k,V'?{k})}(k?V')d(k,{})?cki(k?i)6.2.2 多段图的最短路径问题O(n+m)
cost[i]?min{cij?cost[j]}(i?j?n)path[i]?cij?cost[j]6.3 组合问题中的动态规划法 6.3.1 0/1背包问题O(n*C)
----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------
n???wixi?C?i?1??xi?{0,1}(1?i?n)
max?vixii?1nV(i,0)?V(0,j)?0V(i?1,j)j?wi ?V(i,j)??V(i?1,j),V(i?1,j?wi)?vi}j?wi?max{0V(i,j)?V(i?1,j)? xi???1,j?j?wiV(i,j)?V(i?1,j)6.3.2 最长公共子序列问题O(n*m)
L[0][0]?L[i][0]?L[0][j]?0(1?i?m,1?j?n)xi?yj,i?1L[i?1][j?1]?1?L[i][j]???max{L[i][j?1],L[i?1][j]}xi?yj,j?1 .
xi?yi?1?S[i][j]??2xi?yi&L[i][j?1]?L[i?1][j]?3x?y&L[i][j?1]?L[i?1][j]
i?i6.4 查找问题中的动态规划法
6.4.1 最优二叉查找树O(n^3)
C(i,i?1)?0(1?i?n?1)C(i,i)?pi(1?i?n)C(i,j)?min{C(i,k?1)?C(k?1,j)??ps}(1?i?j?n,i?k?j)s?ij
6.4.2 近似串匹配问题
0??i?D(i,j)???min{D(i?1,j?1),D(i?1,j)?1,D(i,j?1)?1}i?0,??min{D(i?1,j?1)?1,D(i?1,j)?1,D(i,j?1)?1}i?0,6.5 实验项目——最大子段和问题
第七章 贪心法
7.1 贪心法的设计思想
i?0j?0
j?0,pi?tij?0,pi?ti贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 贪心法的关键在于决定贪心策略。
----------------------------精品word文档 值得下载 值得拥有---------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------
7.2 图问题中的贪心法 7.2.1 TSP问题O(2) 7.2.2 图着色问题
n
7.2.3 最小生成树问题O(2) 7.3 组合问题中的贪心法 7.3.1 背包问题O(nlog2n) 7.3.2 活动安排问题O(nlog2n) 7.3.3 多机调度问题O(n*m) 7.4 实验项目——哈夫曼编码
第八章 回溯法
8.1 回溯法的设计思想
n
从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。 步骤：
确定解向量和分量的取值范围，构造解空间树； 确定剪枝函数；
对解空间树按深度优先搜索，搜索过程中剪枝； 从所有的可能解中确定最优解。
8.2 图问题中的回溯法 8.2.1 图着色问题
8.2.2 哈密顿回路问题 8.3 组合问题中的回溯法 8.3.1 八皇后问题
8.3.2 批处理作业调度问题 8.4 实验项目——0/1背包问题
第九章 分支界限法
9.1 分支限界法的设计思想
1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数；