算法分析与设计期末复习
第1章 概论
1.1 算法的概念
1.1.1 什么是算法
P3 页有算法的 5 个重要特性,通过它们判断一段程序是否为算法。
算法的5个重要特性:
(1)有限性:一个算法在执行有限步之后结束,每一步在有限时间内完成
(2)确定性:算法中的每一条指令有明确的含义,不会产生歧义
(3)可行性:算法中的每一条运算都是足够基本的,他们在原则上都能精确的执行
(4)输入性:一个算法有零个或多个输入
(5)输出性:一个算法有一个或多个输出
P2 页则有 5 个算法设计的目标,衡量一个算法的优劣。结合例子代码去理解。
算法设计应满足的目标:
(1)正确性:要求算法能够正确的执行预先规定的功能和性能要求,这是最重要也是最基本的标准
(2)可使用性:要求算法能够很方便的使用,(用户友好性)
(3)可读性:算法应该易于人的理解,可读性好,算法的逻辑应该清晰、简单、结构化
(4)健壮性:要求算法有很好的容错性,即提供异常处理,能够对不合理的数据进行检查,不经常出现异常中断或死机等情况
(5)高效率和低存储量需求:效率---算法的执行时间
存储量----算法执行过程中需要的最大存储空间
效率和低存储量都和问题的规模有关
例子代码看书
1.1.2 算法描述
除了用代码描述算法,还可以用伪代码、自然语言等。其它内容基本没用。
总结:算法描述的方式有:
代码、伪代码、自然语言
1.1.3 算法和数据结构
掌握联系与区别
算法的操作对象是数据结构
联系:一种数据结构包括逻辑结构、存储结构、算法(运算)三要素。
区别:没有本质区别。本课程介绍的算法主要面向具体的、实际的问题
1.1.4 算法设计的基本步骤
基本没用。
不过,能看到 P6 页,图 1.5 中,算法设计的最后一步是“算法分析”,可以有一点启示,这里的“分析”是分析算法复杂度,来评估其效率。而不是有人认为的分析问题,以找到解决问题的途径。
1.2 算法分析
目的是分析某算法的时间或空间效率处于什么级别。
设该算法处理的数据规模为 n,则用函数 f(n)表示算法中基本语句的执行次数(或占用的空间大小),则算法分析就是分析随 n值增大时,f(n)的增长率级别,比如是处于log2(n),n,n^2等哪个级别。
下面举例说明为什么“级别”这么重要:
设有一个 n元素的数组,有2个功能一样的查找算法 A、B,A的级别是n,B的级别是n^2, 则数组长度由 10 增长到 20,A算法的基本语句执行次数增长 1倍,若要达到以前一样的速度,可以用双核 CPU;B算法的基本语句执行次数增长 10 倍,若要达到以前一样的速度,必须用 10 核 CPU。数据量增长一倍,硬件资源投入需增加 10 倍,若数据量很大,则很困难。
1.2.1 算法时间复杂度分析
基本语句的定义:
某算法中执行频度最高的语句(这是老师复习资料中的定义)
课本上关于基本语句的定义是:
执行次数与整个算法的执行次数成正比的语句,通常基本语句是算法中最深层循环内的语句
下面的代码将矩阵对角线元素相加,第5行为基本语句,f(n)=n.
1 |
|
若将循环改为:
1 |
|
则这两句都是基本语句
这时f(n)=2n,或f(n)=n都可以,采用后面这种形式,
“基本语句“代表频度最高语句的集合。无论采取哪种,后续在分析复杂度时,结果是一样的。
求出f(n)后,若它是一个和式,则只保留最高级别的项,并去掉常数系数就是复杂度。比如:
某算法的f(n)=10n2+1000n+10000,则它的复杂度为O(n2),这句话也记作
f(n)=O(n^2)(注:这里等号的含义表示某算法复杂度,不是通常数学含义)
若f(n)=10000,则算法复杂度为f(n)=0(1)
P12页递归算法的时间复杂度分析比较常用,应掌握。结合例子,看看怎么根据代码写出T(n)的递推关系式,然后展开,观察特点,化简。
1.2.2算法空间复杂度分析
算法占用的空间只计算临时空间。
比如上面这两个算法比较,由于它们都一定包括输入的数组a,因此比较时就不需要计入数组a的空间了。
对下面的函数而言,由于任何的函数调用,都需要系统的压栈操作,以保存返回地址等信息。因此它的空间复杂度时O(1),不是零。
1 |
|
1.3算法设计工具——STL
知道C++模板概念或Java泛型的同学可以不看。
本课程只用到vector,queen,priority_quene 这三个,见P16页的表,P18开始有一些示例代码。
教材后面代码涉及的STL相关知识比较浅显。
问题
什么是算法:
算法是求解问题的一系列计算步骤,用来将输入数据转换成输出结果
第2章递归算法设计技术
2.1什么是递归
2.1.1递归的定义
有三个术语:递归,间接递归,尾递归。
【术语理解】
如果一个递归过程或者递归函数中的递归调用语句是最后一条执行语句
,称这种递归调用为尾递归
若p函数定义中调用了p函数,称为直接递归
若p函数定义调用了q函数,而q函数定义调用了p函数,称之为间接递归
任何间接递归都可以等价的转化为直接递归,本章主要讨论直接递归
直接递归和尾递归不冲突
2.1.2何时使用递归
(1)定义是递归的
斐波那契数列,求n!等问题,许多数学公式、数列、概念的定义是递归的
(2)数据结构是递归的
单链表就是一种递归的数据结构、二叉树的二叉链存储结构
(3)问题的求解方式是递归的
如汉诺塔问题
要解决的问题能够分解成更小规模的子问题,子问题与原问题间有相似性时,可使用递归。
这种相似性,按照实际问题的特点,又分成 定义递归、结构递归、步骤递归。结合阶乘、单链表、汉诺塔去理解。
2.1.3递归模型
模型包括2部分:递归出口
(终止条件),递归体
。教材上按照“问题“定义的方式来举例,不看也行,我们知道一个递归程序中,递归出口与递归体分别是哪一段就可以。
2.1.4递归算法的执行过程
函数f(x)函数调用g(y)时,需要将g(y)返回后将要用到的信息压栈(自动进行)。
1 |
|
需要压栈的信息有形参x,局部变量t,返回时,需要将g的返回值压栈。这样f恢复后从第4行接着执行时,需要的信息都从栈顶取得。
递归调用时,要一层层地压栈。结合教材上的例子,看看究竟栈是如何变化的
2.2递归算法设计
2.2.1递归与数学归纳法
数学归纳法与递归算法的联系很弱,不看。
2.2.2递归算法设计的一般步骤
递归算法的设计能力依赖于经验,多看多练,记忆步骤并没什么用。只看例2.5增加经验值。
例2.5 用递归法求一个整数数组a中的最大元素
设f(a,i)求解数组a中前i个元素(a[0]...a[i-1])中的最大元素,这是一个大问题;
则f(a,i-1)为求解数组a中前i-1个元素(a[0]...a[i-2])中的最大元素,这是一个小问题;
只考虑第一个元素时的情况 f(a,1)=a[0]
当i>1时,f(a,i)=MAX{f(a,i-1),a[i-1]}
对应的递归算法如下:
1 |
|
2.2.3递归数据结构及其递归算法设计
看每个例题增加经验值,文字一概不看。
递归数据结构:采用递归方式定义的数据结构称为递归数据结构
例如正整数的定义:n是正整数,则n+1也为正整数 n+1是一种基本的递归运算
递归运算具有封闭性
基于递归数据结构的递归算法设计
例题一:一个不带头节点的单链表L,设计一个算法释放其中的所有节点
递归模型如下: 1
2f(L)=不做任何事 当L==NULL时
f(L)=f(L->next); 其他情况 //释放*L节点
递归算法如下: 1
2
3
4
5
6
7
8void DestroyList(LinkNode *&L)
{
if(L!=NULL)
{
DestroyList(L->next);
free(L); //顺序不能搞反
}
}
1 |
|
第二个算法相对更好一些,因为它在每次递归调用后立即释放当前节点,能更及时地回收内存。
例题二:设计一个算法删除其中所有节点值为x的节点
递归模型如下: 1
2
3f(L,x)=不做任何事 当L=NULL时
f(L,x)=删除L节点,L指向后继节点 当L->data=x时
f(L,x)=f(L->next,x) 当L->data!=x时
递归算法如下: 1
2
3
4
5
6
7
8
9
10
11
12
13void Delallx(LinkNode *&L,ElemType x)
{
LinkNode *p;
if(L==NULL) return; //递归出口
if(L->data==x)
{
p=L;
L=L->next;
free(p);
Delallx(L,x);
}
else Delallx(L->next,x); //递归体
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15BTNode *CreateBTree(ElemType a[],ElemType b[],int n)
//由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链
{
int k;
if (n<=0) return NULL;
ElemType root=a[0]; //根结点值
BTNode *bt=(BTNode *)malloc(sizeof(BTNode));
bt->data=root;
for (k=0;k<n;k++) //在b中查找b[k]=root的根结点
if (b[k]==root)
break;
bt->lchild=CreateBTree(a+1,b,k); //递归创建左子树
bt->rchild=CreateBTree(a+k+1,b+k+1,n-k-1); //递归创建右子树
return bt;
}
例题四:假设二叉树采用二叉链存储结构,设计一个递归算法释放二叉树bt中的所有节点
1 |
|
例题五:由二叉树bt复制产生另一个二叉树bt1 1
2
3
4
5
6
7
8
9
10
11
12void CopyBTree(BTNode *bt,BTNode *&bt1)
{
if(bt==NULL) //递归出口
bt1=NULL;
else
{
bt1=(BTNode*)malloc(sizeof(BTNode));
bt1->data=bt->data;
CopyBTree(bt->lchild,bt1->lchild);
CopyBTree(bt->rchild,bt1->rchild);
}
}
例题六:输出从根节点到x值的节点的路径(有点像搜索问题)
先看递归模型:
1 |
|
本身为目标节点,或者当前节点的左右子节点是目标节点时,才能将对应的节点加入到path中
算法如下: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool Findxpath1(BTNode *bt,int x,vector<int> &path) //解法1
//求根结点到x结点的(逆向)路径
{
if (bt==NULL) //空树返回false
return false;
if (bt->data==x) //找到值为x的结点
{
path.push_back(x); //结点值加入path中,并返回true
return true;
}
else if (Findxpath1(bt->lchild,x,path) || Findxpath1(bt->rchild,x,path)) //在判断语句中设置递归,比较有意思~
{
path.push_back(bt->data); //结点值加入path中,并返回true
return true;
}
}
解法二: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17bool Findxpath2(BTNode *bt,int x,vector<int> tmppath,vector<int> &path) //解法2
//求根结点到x结点的(正向)路径
{
if (bt==NULL) //空树返回false
return false;
tmppath.push_back(bt->data); //当前结点加入path
if (bt->data==x) //当前结点值为x,返回true
{
path=tmppath;
return true;
}
bool find=Findxpath2(bt->lchild,x,tmppath,path);//在左子树中查找
if (find) //左子树中成功找到
return true;
else //左子树中没有找到,在右子树中查找
return Findxpath2(bt->rchild,x,tmppath,path);
}
2.2.4基于归纳思想的递归算法设计
例题不典型,不看。
2.3递归算法设计示例
2.3.1简单选择排序和冒泡排序
增加经验值。体会大数组的排序,转变成小数组的排序
例题一:简单选择排序:在无序区选择最小元素放在开头处
1 |
|
例题二:冒泡排序:采用交换的方式将无序区中最小的元素放到开头
1 |
|
感觉递归的冒泡排序更复杂一点呢,怎么说呢,不是很喜欢......
2.3.2求解n皇后问题
增加经验值。体会大棋盘,转变成小棋盘。
1 |
|
2.4递归算法转化为非递归算法
2.4.1用循环结构替代递归过程
直接转换法适合尾递归。想想为什么?
尾递归只有一个递归调用语句,而且是处于算法的最后,当递归调用返回时返回到上一层再递归调用下一句语句,而这个返回的位置正好是算法的末尾
采用循环结构求解n!的非递归算法如下:(属于尾递归) 1
2
3
4
5
6
7
8
9int fun1(int n)
{
int f=1,i;
for(i=2;i<=n;i++)
{
f=f*i;
}
return f;
}
采用循环结构求解斐波那契数列的非递归算法如下:(属于单向递归)
1
2
3
4
5
6
7
8
9
10
11
12
13
14int F(int n)
{
int i,f1,f2,f3;
if(n==1||n==2)
return 1;
f1=1,f2=1;
for(i=3;i<=n;i++)
{
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
2.4.2用栈消除递归过程
代替函数调用使用的系统栈,是对函数调用过程的模拟,通过教材上的例子体会。
2.5递推式的计算
递归算法的复杂度分析时,其基本语句的执行次数写成递推式,要化简后才能得到复杂度。第一章通过将递推式展开,来寻找数列的规律,然后求和的方法来做到这一点。这里提供了更一般化的方法。
2.5.1用特征方程求解递归方程
不常用,不看。
2.5.2用递归树求解递归方程
常用。
例题:分析以下递归方程的时间复杂度
1 |
|
时间复杂度为:O(n^2),详见课本P77
课本还有一个例题也值得关注下!
2.5.3用主方法求解递归方程
常用。
一般方法
看书P78
对于一般的方程:
T(n)=aT(n/b)+f(n)
a,b是常数且a大于等于1,b大于1
比较函数n^(logba)(以b为底)与f(n)的大小关系
取较大的那一个
第3章分治法
3.1分治法概述
3.1.1分治法的设计思想
P84页本小节第1段,是分治法的定义。后面看到具体实例的时候,要回顾该定义是怎么体现在其中的。别的文字没什么用。
递归解决子问题(这是在第二章的基础上进行的!!!)
3.1.2分治法的求解过程
P85页最上方绿色字体,是三个步骤。其实也是对分治法定义的解析。别的文字没什么用。
分解成若干个子问题
求解子问题
合并子问题
3.2求解排序问题
3.2.1快速排序
从数据结构、算法这两门课的角度看,都是经典。其中快排中“划分”这一步骤,应用特别广泛。
划分:整个序列被基准分割成两个子序列,基准位于两个子序列中间,一小一大
1 |
|
3.2.2归并排序
归并排序,结合微助教上的“求逆序数”来看。
二路归并、多路归并
自底向上的二路归并排序算法,将两个相邻的有序子序列合并为一个有序子序列的过程。
自顶向下的二路归并排序算法,属于典型的二分法算法
课本习题:3.8.3
求排列的逆序数(分治)
一、题目描述
在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1,i2,…,in,如果其中存在j,k,满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。显然,由1,2,…,n 构成的所有n!个排列中,最小的逆序数是0,对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列,求它的逆序数。
输入
第一行是一个整数n,表示该排列有n个数(n <= 100000)。 第二行是n个不同的正整数,之间以空格隔开,表示该排列。
输出
输出该排列的逆序数。
样例输入
6
2 6 3 4 5 1
样例输出
8
提示
1、利用二分归并排序算法(分治); 与二路归并排序非常相似。
2、在合并过程中,(low<=i<=mid,mid+1<=j<=high),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分比i大的元素都比a[j]大,产生的逆序数个数为mid-i+1.
1 |
|
【问题】为何能够基于归并排序求解逆序数?
在合并过程中,(low<=i<=mid,mid+1<=j<=high),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分比i大的元素都比a[j]大,产生的逆序数个数为mid-i+1.
这里需要搞懂!!!
3.3求解查找问题
3.3.1查找和次大元素
较简单,浏览一下,对理解分治法不错,帮助提高写递归程序的能力
1 |
|
3.3.2折半查找
体会分治法可以使用递归与非递归2种形式
折半查找(二分查找)
折半查找要求序列是有序的,假设递增
折半查找的递归与非递归算法
1 |
|
算法的时间复杂度计算:
对应的搜索树的高度为:log2n(向下取整)+1
折半查找的时间复杂度为O(log2n)
3.3.3寻找一个序列中第k小的元素
特别重要
。以它为基础,可解算法里很多题
先给这个序列进行排序,采用类似快速排序的思想
1 |
|
3.3.4寻找两个等长有序序列的中位数
重要,同时又一定难度
。在搞清算法原理的基础上,会觉得比较精妙,看似繁杂的步骤,也不用记忆,很自然就知道怎么解,参考微助教。思考的起点是:一个序列,从它的两端各去掉相同数量的元素,中位数不变
1 |
|
还有等价的非递归算法,不做说明(就是改成了while循环而已)
或者考虑将其排个序,合成一个递增数组,然后直接求中位数
例3.2不看。
3.4求解组合问题
3.4.1求解最大连续子序列和问题
比起3.3.1,3.3.2的例子更有启发性的例子。在大致阅读文字,粗浅地了解原理后,阅读代码能更清楚地反映细节。
采用分治法解决,书上的思想将问题分为三种情况展开讨论:
先对整个序列从中部划分左右各一半
(1)最大子序列和完全在左半部,递归求解左半部的最大子序列和
(2)最大子序列和完全在右半部,递归求解右半部的最大子序列和
(3)最大子序列和横跨左右半部,该子序列和中一定会含有mid元素,求出最大值
上述三种情况再求最大值即可
1 |
|
上述算法无法求解最大连续子序列积的问题,因为该问题的子序列不满足最优性原理!
分治法需要满足最优性原理
即整个问题的最优解由各个子问题的最优解构成!
3.4.2求解棋盘覆盖问题
了解原理。体会分治法从一维走向二维
这里第一遍复习时没看,后面有时间补,感觉不是很重要
3.4.3求解循环日程安排问题
日常有用,对分治法的理解帮助不大,不用看。
3.5求解大整数乘法和矩阵乘法问题
不典型,不看。
3.6并行计算简介
具体的硬件相关,不看。
第4章蛮力法
4.1蛮力法概述
蛮力法
,也叫暴力法(brute force method),穷举法。
原理
:把所有可能的解列举出来,找出满足条件的解。
特点
:通用性强,效率低。
通过看后面小节中的例子,来理解上述三点。其它内容可不看。
(教材上将蛮力法应用的场景分成4种,可以在后面几节的例子里去体会它们属于哪一种。这些也不紧要。)
4.2蛮力法的基本应用
4.2.1采用直接穷举思路的一般格式
例4.1
前提知识是一个数m除了本身以外的其他因子都在1-m/2之间,只需要遍历这个区间即可,减少运算量
1 |
|
例4.3 计算一个逻辑算式各个符号代表什么具体的数字 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//例4.3
void fun()
{ int a,b,c,d,e,m,n,s;
for (a=1;a<=9;a++)
for (b=0;b<=9;b++)
for (c=0;c<=9;c++)
for (d=0;d<=9;d++)
for (e=0;e<=9;e++) //5个自变量,5重循环
if (a==b || a==c || a==d || a==e || b==c || b==d
|| b==e || c==d || c==e || d==e) //个不相等才行
continue;
else
{ m=a*1000+b*100+c*10+d;
n=a*1000+b*100+e*10+d;
s=e*10000+d*1000+c*100+a*10+d;
if (m+n==s)
printf("兵:%d 炮:%d 马:%d 卒:%d 车:%d\n",
a,b,c,d,e);
}
}
4.2.2简单选择排序和冒泡排序
不看
4.2.3字符串匹配
看
直接穷举法,也称为BF算法
1 |
|
例题4.5
比较简单,不看了
4.2.4求解最大连续子序列和问题
三种方法,很有代表性。结合图4.5,看代码来分析a[i][j]元素的计算量的多寡,课件上更清晰。
第三章使用分治法求解过,现在使用穷举法思想解决之,看课本解释
思路一
1 |
|
本质上是三重循环,时间复杂度为O(n^3)
思路二
1 |
|
解法二两重循环,时间复杂度为O(n^2)
思路三
1 |
|
解法三只需要遍历一遍数组,时间复杂度为O(n)
4.2.5求解幂集问题
算法中的基本问题,要掌握。
幂集问题可以使用穷举法实现,例题代码如下:
1 |
|
求幂集问题上面的例题有三个元素,可以对应三位二进制 从000-111 0表示不选,1表示选择
利用二叉选择树来进行求解亦可
4.2.6求解简单0/1背包问题
经典问题。以前一节为基础。
可以尝试在前一节的基础上开展,0表示不选,1表示选择
求出幂集即可求出结果,具体实现细节不多赘述
因为是蛮力法嘛,就是求出全部的排列情况,就知道哪个方案最好了
4.2.7求解全排列问题
算法中的基本问题,要掌握。
给定正数n,求解1-n的所有全排列
1 |
|
4.2.8求解任务分配问题
经典问题。以前一节为基础。
在前一节的基础上可以理解为一种排列就是一种分配方案(和顺序的1234相比)
4.3递归在蛮力法中的应用
4.3.1用递归方法求解幂集问题
结合4.2.5看。
4.3.2用递归方法求解全排列问题
结合4.2.7看。
4.3.3用递归方法求解组合问题
难度比前2节大,更精妙,理解之后很愉快。
从1-n个正整数中取出k个不重复的正整数的所有组合
1 |
|
4.4图的深度优先和广度优先遍历
不看
第5章回溯法
5.1回溯法概述
5.1.1问题的解空间
1.术语:解空间、可行解、最优解。
本节的例子,只能说明术语 解空间。到5.2节的0—1背包问题,可体会这三个术语究竟指什么。
2.术语:子集树、排列树
结合图5.2理解子集树、图5.4理解排列树。
子集树
:当所给的问题是从n个元素的集合S中找到满足某种性质的子集时,对应的解空间树称为子集树。
排列树
当所给的问题是确定n个元素满足某种性质的排列时,对应的解空间树称为排列树。
本小节的图5.3的例子由于问题本身比较繁琐,并不适合作为例子理解回溯法,故不要看
5.1.2什么是回溯法
1.术语:活结点、扩展结点、死结点
所有例子都可用于理解它们
2.术语:剪枝函数、约束函数、限界函数
下一小节例5.2可用于理解约束函数,直到5.2节的0—1背包问题才出现限界函数。在此之前的其它例子,都不包括剪枝函数。
剪枝函数
包括约束函数
和限界函数
;
约束函数
是在拓展结点处剪除不满足约束条件的路径(注意是在拓展的时候
)
限界函数
是剪去得不到问题解或者最优解的路径(这里可以理解为遍历树时剔除的分枝
)
5.1.3回溯法的算法框架及其应用
算法的框架只粗略浏览一下即可,必须要多看几个实例,从实例中去总结经验,再反过来看这个框架才能理解。
回溯法的框架
分为非递归
和递归
两种
书上的例子都可以看看
递归回溯框架:
求幂集问题(子集树)
1 |
|
1 |
|
例题5.4 排列树框架
可以理解为运算符合和这些数字之间的排列组合,检查是否满足题目的条件
1 |
|
5.1.4回溯法与深度优先遍历的异同
本节的精华都在最后一句:回溯法=DFS+剪枝
。结合前面的例子来理解。其它的描述都不看。
5.1.5回溯法的时间分析
看过后,再看后面的例子时,都要进行复杂度分析
。
通常,解空间树为子集树时对应算法的时间复杂度为O(n^2)
;涉及到选与不选的问题
解空间树为排列树时对应的算法时间复杂度为O(n!)
,涉及到排列组合的问题
5.2求解0/1背包问题
本节无废话,子集树的典型。
重点关注左右子树剪枝的过程以及不同情况下的剪枝思路
5.3~5.9都看,其中5.5节、5.7节使用排列树框架为好(教材上用的是子集树框架)
可参照微助教中的课件“全排列简洁版”,看看排列树怎么编写回溯代码
。

求解n后问题的非递归回溯算法
1 |
|
每次放一个新皇后,都从该行的列头进行试探
每个皇后都要试探n列,其解空间是一个子集树,每个节点都可能有n棵子树,时间复杂度是O(n^n)
5.7 任务分配问题需要重点关注
第四章的任务分配采用蛮力法,求出所有分配方案的全排列,再选择成本最低的方案
本章使用回溯法来解决
1 |
|
算法分析:每个人员试探1-n个任务,对应的解空间是一个n叉树时间,复杂度为O(n^n)
【第五章回溯法总结】
回溯法在解空间树中按照深度优先
的策略来拓展节点
回溯法需要借助栈
这种数据结构来保存从根节点到当前拓展节点的路径
是一种通用解题法
既带有系统性,也带有跳跃性的搜索算法
回溯法的效率不依赖于确定解空间的时间
第6章分枝限界法
6.1分枝限界法概述
6.1.1什么是分枝限界法
在本节第2段提到,所谓“分枝”,就是采用广度优先策略搜索解空间树
,这是与回溯法的主要区别,其它的区别都是间接来自这一点。
回溯法搜索方式是深度优先
回溯法的目标是找出所有解,分枝限界法的目标是找到最优解
分枝限界法依靠的数据结构是队列和优先队列
6.1.2分枝限界法的设计思想
数据结构课里面,广度优先搜索(树的层次遍历)借助队列
实现。本节不看也可以。
感觉和A*有点像呢
确定合适的限界函数
组织待处理节点的活结点表
如何确定解向量的各个分量
6.1.3分枝限界法的时间性能
它的剪枝数量不定,因此速度与回溯法无法理论比较,要借助实验。用大O表示法,它们的都与解空间树结点数相关,在剪枝数目难以确定的情况下,都是按满二叉树计算的。
由于入队的结点,相互之间没有办法保存相互间的父子关系,分限法经常需要在每个结点中记录当前的解;回溯法是按深度优先搜索的,搜索的顺序就是沿着父—子”路径的,因此通常只用一个数组,保留一个当前的解,在搜索的过程中,根据父子关系的变化,动态地修改该数组即可。在看0—1背包分限法是,体会这一段文字,看看它的代码中队列结点的结构题类型中有一个int x[MAXN]数组。
因此,从理论上得到的复杂度,分限法往往比回溯法高
6.2求解0/1背包问题
通读掌握,非常典型。
队列和优先队列两种分枝限界法
队列:先进先出
采用队列式分枝限界法
,对于每个节点求解上界
1 |
|
1 |
|
采用优先队列式分枝限界
大根堆,按ub越大越先出队来进行计算
求解上界的函数不变
最坏的时间空间复杂度都为O(2^n),n是物品的个数
6.3求解图的单源短路径
不典型,可不看。
6.4求解任务分配问题
需看懂。
需要涉及求解节点下界的算法
1 |
|
6.5求解流水作业调度问题
问题本身比较复杂,弄清楚问题本身到底是什么意思即一些细节,要花不少时间,用来说明分限法并不好,不看。
第7章贪心算法
7.1贪心法概述
7.1.1什么是贪心法
本节并没有值得看的内容。
7.1.2用贪心法求解的问题应具有的性质
这2个性质非常重要
。要结合7.2节的例子来理解,不然这段文字比较抽象,要形成一个自己的通俗的理解。这样才能举一反三。证明这2个性质,比具体算法的编码更重要
1、贪心选择性质
所求解的问题的整体最优解可以通过一系列的局部最优的选择(即贪心选择)来达到,每一步所做的贪心选择最终导致问题的整体最优解
数学归纳法
2、最优子结构性质
如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质
反证法
7.1.3贪心法的一般求解过程
没用
7.2求解活动安排问题
简单、入门非常好
求解兼容活动最多的个数
将活动按结束时间递增排序
算法的时间主要花费在排序上,排序的时间复杂度为O(nlog2n),整个算法的时间复杂度也是如此
7.3求解背包问题
典型需掌握
选择的贪心策略:选择单位重量下价值最大的物品,在价值与容量之间寻求平衡
需要根据单位价值递减排序然后依次选择
7.4求解装载问题
掌握
情景:不考虑集装箱的体积限制,只限制重量,要求尽可能多的集装箱
策略:采用贪心算法,优先选择重量轻的集装箱
对w从小到大进行排序
7.5求解田忌赛马问题
问题本身太复杂,不适合做贪心算法的示例,不看。
7.6求解多机调度问题
实际上只能得到近似解,不看。
7.7哈夫曼编码
掌握证明
前缀码的概念
每次都合并两棵根节点权值最小的二叉树,这体现出了贪心法的思想
带权路径长度和 WPL 等于权值乘以节点的路径长度再求和
具有最小带权路径长度和的树是哈夫曼树(最优树)
算法的证明:
贪心选择性质:构造一棵哈夫曼树的过程可以从合并两个权值最小的字符开始
满足最优子结构性质:该问题的最优解包含其子问题的最优解
7.8求解流水作业调度问题
问题本身太复杂,不适合做贪心算法的示例,不看。
第8章动态规划
8.1动态规划概述
8.1.1从求解斐波那契数列看动态规划法
通过斐波那契数列的计算,理解什么是重叠子问题
,这个例子足够简单
8.1.2动态规划的原理
学握逆序解法
从后往前进行推理的算法
8.1.3动态规划求解的基本步骤
在本节开始部分提到了应用动态规划的3个性质,(1)(3)是主要的,应理解;性质(2)无后效性在一些其它教材里是没有的。除了刚开始的这一段关于性质的描述,后面文字的没 有用处。
(1)最优性原理:问题的最优解包含的子问题的解也是最优的,具有最优子结构,满足最优性原理
(2)无后效性:某状态以后的过程不会影响以前的状态,只与当前状态有关
(3)有重叠子问题:子问题之间不是独立的,一个子问题在下一个阶段被多次使用到
8.1.4动态规划与其他方法的比较
需要理解它
基本思想与分治法类似,但是分治法的各个子问题独立,dp的子问题重叠
dp又与贪心类似,
dp只有多项式的时间复杂度,效率较高
8.2求解整数拆分问题
掌握
1 |
|
采用递归算法来实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int dpf(int n,int k)
{
if (dp[n][k]!=0) return dp[n][k]; //这一步是递归dp的精髓
if (n==1 || k==1) //注意下面四种情况属于是并列式的,在一个节点只能出现一种情况,因此每种情况都需要设置 return
{
dp[n][k]=1;
return dp[n][k];
}
else if (n<k)
{
dp[n][k]=dpf(n,n);
return dp[n][k];
}
else if (n==k)
{
dp[n][k]=dpf(n,k-1)+1;
return dp[n][k];
}
else
{
dp[n][k]=dpf(n,k-1)+dpf(n-k,k);
return dp[n][k];
}
}
这种方式也叫备忘录的方式
8.3求解连续子序列和问题
不看
8.4求解三角形小路径问题
看
8.5求解长公共子序列问题
掌握
8.6求解长递增子序列问题
不看
8.7求解编辑距离问题
不看
8.8求解0/1背包问题
掌握
8.9求解完全背包问题
不看
8.10求解资源分配问题
不看
8.11求解会议安排问题
不看
8.12滚动数组
看
滚动数组:压缩存储空间,使用求模的方式来实现
第11章计算复杂性理论简介
11.1计算模型
11.1.1求解问题的分类
本节的概念比较清晰,在最后一句提到了需要关于图灵机的概念。现代计算机可抽象成图灵机,因此我们就按照现代计算机去理解就行,不用研究图灵机模型
11.1.2图灵机模型
不看
11.2P类和NP类问题
掌握
用确定性图灵机用多项式时间界可以解决的问题称为P类问题
用非确定性图灵机以多项式时间界可解的问题称为NP类问题,N表示非确定性
P类问题属于NP类问题的一个子集
11.3 NPC问题
证明不看,只掌握文字性的描述
TSP问题是NPC问题
题型
一选择题(共10分,每空2分)
第1、3、5、7、8章各一题
二判断题(共5分、5题)
第6章2题,第5、8、11章各一题
三、程序填空题(共20分,10空)
第3、4章各一题
四、算法过程分析(共32分、2题
第6、8章各一题
五、算法复杂度分析(共24分、2题
第5、8章各一题
回溯法:解空间为子集树O(2^n),解空间为派列树O(n!)
六、证明一个问题适用贪心算法(9分)
注:有10分左右,它待解的问题,并不是书上或作业上练过的问题
结合微助教上面的作业,以及“课件”下面的各章“学习”要点复习。