递归与分治

1、   分治法的基本思想

“分”：将问题分解为规模更小的子问题

“治”：求解规模较小的子问题

“合”：将已解决的子问题合并，得出原问题的解

2、   应用分治法求解的2个前提

最优子结构性质，平衡子问题

3、   分治法所能解决的问题所具有的几个基本特征

1）问题小到一定程度就可以容易地解决

2）问题可以分解为若干个规模较小的相同问题，即最优子结构性质

3）分解出的子问题的解可以合并为原问题的解

4）问题所分解出的各个子问题是相互独立的

（PS：能否利用分治法完全取决于是否具有第四条特征）

4、   整数划分和汉诺塔问题：基本思想或递归方程

1）整数划分：

    基本思想：把题目化成n的m划分问题，根据n和m大小情况写出递归方程

    递归方程：

       ①n=1 or m=1 return 1

②n=m return f(n,n-1)+1

       ③n>m>1 return f(n-m,m)+f(n,m-1)

       ④n<m return f(n,n)

2）汉诺塔问题：

       基本思想：

当n=1的时候，直接从A移到B；当n>1的时候，先把n-1个较小的借助B从A移到C，再把最大的从A移到B，最后把n-1个较小的借助A从C移到B。

递归方程：

If n=1 move(A,B)

Else

hanoi(A,C,B,n-1)

move(A,B)

hanoi(C,B,A,n-1)

 

5、   二分搜索技术：基本思想、算法实现和算法分析

1） 基本思想

    在一个升序的数组中找到key的位置：先和数组中间位置的值比较，如果小于就把范围移到low~mid-1，如果大于就把范围移到mid+1~high，然后继续与中间的值比较;如果等于就直接返回中间位置的下标。

2） 算法实现

Mid = (low+high)/2

If key=arr [mid]return mid

If key<arr[mid]return search(low,mid-1,key)

If key>arr[mid]return search(mid+1,high,key)

 

3） 算法分析

                     每执行一次问题的规模就减小一半，所以O(logn)

 

6、   合并排序和快速排序算法的基本思想、排序过程、实现伪/源代码及其计算时间复杂度分析

 

三、动态规划

1、   动态规划算法的基本要素及其含义

1)       最优子结构性质：（优化原则）

l  一个最优决策序列的任何子序列，一定是最优决策子序列；

l  自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解；

2)       重叠子问题性质：

每次产生的子问题并不总是新问题，有些子问题被反复计算多次；

对每个子问题只解一次，并将其解保存在备忘录中，当再次需要解此子问题时，仅用常数时间查找结果。

 

2、   动态规划算法的基本解题步骤

1)       找出最优解的性质、刻划其结构特征

2)       递归地定义最优值（建立目标函数）

3)       以自底向上的方式计算出最优值

4)       根据计算最优值时得到的信息构造最优解

 

3、   动态规划与分治算法的异同点

1)       分解出的子问题不是互相独立的

2)       不同子问题的数目只有多项式量级

3)       若有分治法，有些子问题被多次重复计算

 

4、   问题最优子结构性质的判断

反证法：

1)       假设由问题的最优解导出的子问题的解不是最优的

2)       说明这个假设下可构造出比原问题最优解更好的解，从而导致矛盾的产生

 

5、   求解矩阵连乘积、最长公共子序列和0-1背包等问题的算法设计思想

1)       刻画最优值并建立计算最优值的递归方程

2)       算法实现的伪代码及其计算时间复杂度分析

 

6、   求解问题的主要特征：

1)       多阶段优化（决策）问题

2)       从小到大依次求解子问题，最后求解的子问题是原问题

3)       子问题目标函数的最优值之间存在依赖关系

 

 

四、贪心算法

1、   贪心算法的基本思想

w   求解过程是一系列选择，每次选择都是当下最好的选择

w   每选择一次后，问题会简化为一个规模更小的子问题

w   通过局部最优解逐步达到整体的最优解

 

2、   贪心算法的基本要素及其含义

1)       最优子结构性质

问题的整体最优解中包含着它的子问题的最优解

2)       贪心选择性质

整体的最优解可通过一系列局部最优解达到；每次的选择可依赖以前作出的选择，但不依赖于后续选择。

 

3、   贪心算法与动态规划的异同点

共同点：

求解的问题都具有最优子结构性质

差异点：

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

 

4、   活动安排和最优装载问题的贪心算法求解

 

5、   给定数据文件的哈夫曼编码

 

6、   最小生成树问题求解中的MST性质

 

 

五、回溯法

1、  回溯法的基本思想和解题步骤

2、  扩展结点、活结点和死结点的含义和理解

3、  0-1背包问题和旅行售货员问题的解空间、解空间树和深度优先搜索策略的设计及其实现

4、  影响回溯法搜索效率的因素

5、  2类常用的剪枝函数

6、  N后问题、0-1背包、旅行售货员中有关剪枝函数的建立及算法实现