【算法与设计】期末总结

第一章 概述

算法与程序

算法：解决问题的一种方式或者一种过程。算法有若干个指令组成的有穷序列。
程序：算法用某种程序设计语言的具体实现

算法的4种性质：

• 输入
• 输出
• 确定性
• 有限性

程序可以不满足“有限性”

时间复杂性

算法复杂度的高低体现在运行该算法所需要的计算机资源的多少上。资源的多少依赖于要解决问题的规模(N)、算法的输入(I)和算法本身的函数(A)

关于时间复杂性，分为三种情况：最坏情况、最好情况和平均情况。
可操作性最好且最有实际价值的是最坏情况的时间复杂度。

求上界

当N>=N₀时有f(N)<=Cg(N),称为函数f(N)的一个上界是Cg(N)，记作f(N)=O(g(N))
这个上界的阶越低，则评估越精确，结果越有价值

如何求上界？
1.把f(N)函数中的所有阶放大到最高阶，合并后并记为Cg(N)
2.此时f(N)<=Cg(N)，把这两个函数去化简即可得条件，即n值。

例子：f(n)=3n²+10n
最高阶是n²，所有阶放大到最高阶得3n²+10n²=13n²,记为Cg(N)
此时，C=13，g(N)=n²
当3n²+10n <= 3n²+10n²时，即10n <= 10n²时，条件成立。
故n₀>=1
综上，当n₀=1时,C=13，f(n)=O(n²)

注意：放大方向不变，方式可以改变（即可以增大阶层且缩小系数），如3n²+10n <= 3n²+n²,此时结果的C和n₀都不一样，但f(n)始终一样。

第二章 递归与分治

递归：代码效率好，但是空间效率和时间效率差

如何改进？？
消除递归，有两种方式:阶乘（循环）和阶加（循环、通项公式）

双递归函数——Ackerman函数

定义：一个函数及它的一个变量由函数自身定义时

分治策略

基本思想：将问题分解为k个小规模的子问题，这些子问题相互独立且原问题相同。递归地解这些子问题，将个子问题的解合并得到原问题的解。

大整数乘法

普通乘法的时间复杂度是O(n²)
通过分支策略可达到O(n^1.59)

两位×两位

步骤：
1.两位数分出高低位
2.套用公式求p,q,r

遇到负数，高低位都带符号
如-23：高位-2，低位-2。至此，-23=(-2)*10+(-3)

最简的分治（递归出口）：一位x一位

四位x四位

一直递归，直到满足出口

三位x三位

往前补0，公式不变

两位x六位

补零或者把六位拆成3个两位

第三章 动态规划

	动态规划	分治
同	分解子问题	分解子问题
异	子问题相互依赖	子问题相互独立

基本思想：
分解成子问题求解时，有些子问题被重复计算许多次。用一个表来记录所有已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量的重复计算。

步骤：
1.找到最优解，刻画其结构性质
2.递归地定义最优值
3.以自底向上的方式计算最优值
4.根据计算最优值时得到的信息，构造最优解

矩阵连乘

题目背景：
若两矩阵相乘，需满足第一矩阵的行=第二矩阵的列
即A_mxn X B_pxq的条件为n==p
此时，乘法次数为=m x n x q

连乘次序会影响乘法次数

按照上述步骤：
1.最优解及其结构性质：最小乘法次数 及 最小乘法次数的断开处
记A[i:j]是A_iA_i+1…A_j
问题：A[1:n]，可以在k=1,2,⋯n−1处断开，若A[1：n]最优，则A[1：k]与A[k+1:n]也最优

2.建立递归关系
记A[i:j]，其中1≤i≤j≤n，最少乘法次数记m[i][j]
(1)当i=j时→ A[i:i] →指A[i] 本身→乘法次数为0,即 m[i][j]=0
(2)当i<j时， 在k处断开， k可以取值i, i+1, ∙∙∙, j−1，在某k处乘法次数最少

定义数组p存储矩阵信息
p[0]为第1矩阵的行
p[1]为第1矩阵列（也为第2矩阵行）
p[2]为第2矩阵列（也为第3矩阵行）
p[3]为第3矩阵列（也为第4矩阵行）
…
p[n]为第n矩阵列

3.计算最优值
对于结果的存储，使用m表存储最小乘法次数（即最优值），用s表存储k值（即最优解）

代码实现：

//构造最优值
void MatrixChain(int *p, int n, int **m, int **s)//P一维数组记下标；n矩阵个数；m表；s记分段
{for(int i=1;i<=n;i++)m[i][i]=0;//对角线上都填0for(int r=2;r<=n;r++)//在m表中，从第2条填到第n条(对角线)for(int i=1;i<=n-r+1;i++)//i是行下标，从第1行开始填一个倒三角的表{int j=i+r-1;//列下标m[i][j]=0+m[i+1][j]+p[i-1]*p[i]*p[j];//实现递归计算，先初始化第1项，省略了m[i][i]s[i][j]=i;//s记分段点，此为s的初值for(int k=i+1;k<j;k++)//递归式从k=i+1到j-1，找最小{int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//递归式计算 if(t<m[i][j]){m[i][j]=t;//记入最小值s[i][j]=k;//记入划分位置}}}
}

4.构造最优解
算法MatrixChain只是计算出了最优值，并未给出最优解。但是MatrixChain已记录了构造最优解所需要的全部信息。s[i][j]中的数表明，最佳方式应在矩阵的何处断开。

//构造最优解
void Traceback(int i,int j,int **s)//求A[i:j]的最优解构造，利用s[][]，设已知s[i][j]=k
{if(i==j)return ;//A[i:i]不必构造，递归出口Traceback(i,s[i][j],s);//求A[i:k]的构造，记1Traceback(s[i][j]+1,j,s);//求A[k+1:j]的构造，记2cout<<"Multiply A["<<i<<":"<<s[i][j]<<"]and A["<<(s[i][j]+1)<<":"<<j<<"]"<<endl;//输出Ai,k And Ak+1,j，表明在k处断开，记3
}

基本要素

最优子结构

设计动态规划算法的第一步通常是要刻画最优解的结构。
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

子问题重叠

在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

备忘录

动态规划的变形——备忘录

动态规划：保存所有子问题的解
变形：动态规划是自底向上；备忘录是自顶向下

第四章 贪心算法

工作量：贪心算法 < 动态规划
但是贪心算法的结果可能不是最优结果，因为贪心算法并不是从整体最优上加以考虑，它所做出的选择只是某种意义上的局部最优选择

所以，贪心算法的关键是贪心策略的选择。

活动安排问题

该问题要求高效地安排一系列争用某一个公共资源的活动。有n个活动，开始和结束的时间s_i≤f_i，如何安排最多个活动？

贪心策略：按结束时间递增排序，从前向后能安排则安排

例题：当前有4个活动。

i	1	2	3	4
s[i]	1	3	0	5
f[i]	4	5	6	7

若选择最早结束优先，能使选入活动最多
若最早开始优先，仅能安排这一个活动
若最短占用优先，则能安排这一个活动

推广：
假设要在足够多的的会场里安排一批活动，即每个活动都要被安排，并希望使用尽可能少的会场。
（1）贪心策略思路1：先在第1会场安排最多活动，其次在第2会场安排最多，……，依此类推 。
（2）贪心策略思路2：视为区间重叠问题。时间点：起点和终点。
按时间点排序起点分配1个会场，终点回收，保证此会场可重复利用

基本要素

贪心选择性质

贪心选择性质是指所求问题的整体最优解是可以通过局部最优的选择，即贪心选择达到的。
在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。
而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解做出这个选择后产生的相应子问题。

最优子结构性质

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

与动态规划的区别

**贪心算法：**先依据贪心策略选择并解一个子问题，再进行下一步。
**动态规划算法：**先解决所有的子问题，比较得出一个最优子问题，再进行下一步。

背包问题

问题描述：容量为c的背包，有n种物品，每种物品重w_i，价值为v_i，其中1≤i≤n，
物品不可（可以）分开。
问：如何装入使价值最大？

c	n	w1	w2	w3	v1	v2	v3
50	3	10	20	30	60	100	120

物体可分

c>0，w_i>0，v_i>0，1≤i≤n。找（x₁，x₂，⋯，x_n），0≤x_i≤1，可为分数，即仅取一部分，
使$$\sum _{i=1}^{n}wi\ast xi<=c$$ 达到最大
$$\sum _{i=1}^{n}vi\ast xi$$

//物品可分：贪心算法 
#include <iostream>
#include <iomanip> 
using namespace std;void Knapsack(int n, int c, int*v, int *w, double *x);int main() 
{	int n=3;//物品数量 int c=50;//背包容量 int *v=new int[n+1];//价值 int *w=new int[n+1];//重量 int i;double *x=new double[n+1];	for(i=1;i<=n;i++)x[i]=0;	//将数据按贪心策略排序 v[1]=60;v[2]=100;v[3]=120;w[1]=10;w[2]=20;w[3]=30;Knapsack(n,c,v,w,x); for(i=1;i<=n;i++){		if(x[i]>0)cout<<"物品"<<i<<"装入"<<setiosflags(ios::fixed)<<setprecision(2)<<x[i]<<endl;elsecout<<"物品"<<i<<"不装入"<<endl;}return 0;
}void Knapsack(int n, int c, int*v, int *w, double *x)
{int i;for(i=1;i<=n;i++){if(w[i]>c)break;else{x[i]=1;c=c-w[i]; }			}	if(i<=n)	x[i]=(double)c/w[i];		
}

step1：准备
按单位价格递减排序，x[ ]初值为0，先都没选
step2：循环
按递减装入物品至不可装为止，从1检查到n
物品装入置x[i]=1，c=c−w[i]
step3：最后
将当前i物品分开，送入c/w[i]

物体不可分

其中，c>0，w_i>0，v_i>0，1≤i≤n，
找（x₁，x₂，⋯，x_n），x_i∈{0,1}，
（物品没装x_i=0，装入x_i=1）
使$$\sum _{i=1}^{n}wi\ast xi<=c$$ 达到最大
$$\sum _{i=1}^{n}vi\ast xi$$

根据上述步骤：
1.最优子结构性质：
若(y_1，y_2，⋯，y_n)是最优解，则(y_2，⋯，y_n)是子问题的最优解

2.递归关系
m(i,j)记背包容量j，可选物品为i，i+1，⋯，n时，0-1背包问题的最优解

3.计算最优值

template <class Type>
void Knapsack(Type *v, int *w, int n, Type **m)
{int jMax=min(w[n]-1,c);//找<w[n]的临界值,并避免物品n比背包容量还要大的情况 //最小子问题，填写最后一行m[n][j] for(int j=0;j<=jMax;j++)m[n][j]=0;for(int j=w[n];j<=c;j++)m[n][j]=v[n];for(int i=n-1;i>1;i--){jMax=min(w[i]-1,c);for(int j=0;j<=jMax;j++)m[i][j]=m[i+1][j];//物品i装不进去for(int j=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//能装但不装，装进去，两个值中取较大值 }//填最后一行 m[1][c]=m[2][c];//若物品1装不进去 if(c>=w[1])//若物品1可以装 m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]); 
}

 step1：实现递归出口，填矩阵m的第n行(前3行)step2：循环，实现递归式，填矩阵m的第(n−1)行到第2行step3：填m[1][c]

4.构造最优解

template <class Type>
void Traceback(Type **m, int *w, int c, int n, int *x)//m表已经填好，已知w、c、n，输出x[]，0不装，1装入
{for(int i=1;i<n;i++){if(m[i][c]==m[i+1][c])x[i]=0;//相同则不装else{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;		}

第五章 回溯法

溯法有“通用的解题法”之称。
用它可以系统地搜索一个问题的所有解或任意解
它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该点为根的子树的搜索，逐层向其祖先结点回溯；否则进入该子树，继续按深度优先策略搜索。

问题的解空间

 用回溯法解问题时，应明确定义问题的解空间。
指包含解的“集合”，结构常为树或者图。
问题的解空间至少应包含问题的一个（最优）解。

0-1背包

迭代回溯

有两种方案：
第一种是保存所有子集
第二种是添加剪枝函数

3个状态：左子树、右子树、回溯
在左、右子树添加约束函数、限界函数

两种剪枝函数：
约束函数：在扩展结点处剪去不满足约束的子树；
限界函数：剪去得不到最优解的子树。

0-1背包问题（树结构）

期末考点

1.熟练求出上界的n₀,C,g(N)
2.清楚Ackerman函数的代码实现
3.熟练掌握大整数相乘的p,q,r；掌握其求解过程
4.清楚大整数乘法的代码实现，尤其是递归出口
5.掌握动态规划中0-1背包的代码实现、m表、s表、及其求最优值的解
6.在动态规划中0-1背包的代码中，可能会考察代码填空，变量的各阶段的值
7.掌握备忘录代码的具体实现
8.回溯法中的旅行售货员内容 及 整本书的定义内容不会考察。

掌握的意思是必考；清楚代表可能重点考察

期末在头歌上考，有代码填空及代码分析两种题型