算法分析与设计课程学习

预备知识:  离散数学、数据结构、程序设计语言C,C++

第一章 算法概述

第二章 递归与分治

第三章 动态规划

第四章 贪心算法

第五章 回朔法

第六章 分支限界法

第七章  概率算法

第八章  NP完全性理论简介

 

第一章 算法概述

算法: 是将问题的输入转化为输出的一系列 计算或操作步骤。

算法Algorithm一词源于19世纪,原意是计算的步 骤或规则,完全属于数学范畴。

 

第二章 递归与分治

递归与分治基本思想：将规模为n的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止.在分治法中,子问题的解法通常与原问题相同,从而导致递归过程。

常见应用：

1、  大整数的乘法

2、  矩阵相乘的Strassen法

3、  棋盘覆盖

4、  合并(merge)排序

5、  快速排序

6、  线性时间选择

7、  最接近点对问题

 

第三章 动态规划算法

基本思想——用以求解最优化问题

将问题的求解过程化为多步选择,在每一步选择上,列出各种可能的结果(各子问题的可行解),舍去那些肯定不能成为最优解的局部解.最后一步得到的解必是最优解。

与贪心算法比较：都是将求解过程化为多步决策.

区别是：

贪心法：每采用一次贪心策略便做出唯一决策,求解过程只产生一个决策序列;求解过程自顶向下,不一定有最优解；

动态规划：求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果.总能得到最优解。

--------------矩阵乘法链

-------------旅行商问题（货担郎问题）

 

第四章 贪心算法

贪心算法基本思想——用以求解最优化问题

将问题的求解过程看作一系列选择（每次选择确定一个输入值）,每次选择都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体最优解。

常见应用：背包问题，最小生成树，最短路径，作业调度，装载问题，哈夫曼编码等等。

--------旅行商问题。

 

第五章 回朔法

基本思想：设问题解可表为n元组(x₁, x₂,… x_n), x_i?s_i , s_i为有限集, n元组的子组(x₁, x₂,… x_i) i满足一定约束条件D. 设已有满足D的部分解(x₁, x₂,… x_i), 添加x_i+1 ?s_i+1,若(x₁, x₂,… x_i ,x_i+1 )满足D, 则继续添加x_i+2 ; 若所有可能的x_i+1 ?s_i+1均不满足D,去掉x_i , 回溯到(x₁, x₂,… x_i-1), 添加未考虑过的x_i , 反复进行,直到(x₁, .., x_k) k?n满足所有约束或证明无解。

常见应用：装载问题，批处理作业跳读问题，迷宫问题，n后问题，图的着色问题等等。

 

第六章 分支限界法

基本思想——用于求解最优化问题：

在问题的边带权解空间树中进行广度优先搜索. 找一个回答结点使对应路权最小。当搜索到一个扩展结点时,一次性扩展它的所有儿子,将满足约束条件且最小耗费函数?目标函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点同样扩展. 直到找到所需的解或活动结点表为空。

常见应用：背包问题，旅行商问题，印刷电路版问题等等。

 

计算复杂性理论

 

网络流