计算机算法 ------任课教师：于文，信院小仙女，嘻嘻（如有侵权，请联系我）
主要知识点及练习 ------自己整理的，从老师的PPT上
第一章 概述
算法的基本概念
算法是指解决问题的一种方法或一个过程
算法是若干指令的有穷序列，满足性质：
- 输入：有0个或多个由外部提供的量作为算法的输入
- 输出：算法产生至少一个量作为输出
- 确定性：组成算法的每条指令是清晰，无歧义的
- 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的
语句的频度和算法的时间复杂度
对算法时间的度量用其基本操作重复执行的次数来近似，称为时间复杂度，记作T(n)
第二章 递归
分治法的总体思想
将要解决的较大规模的问题不断地分割成更小规模的子问题，直到能够很容易地得到子问题的解
对小规模的问题进行求解
将小问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解
分割、求解、合并
分治和递归的关系
由分治法产生的子问题往往是原问题的较小模式
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小
最终使子问题缩小到很容易直接求出其解
这自然导致递归过程的产生
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
递归的2个要素：边界条件、递归方程
递归举例：阶乘、 Fibonacci数列、 Ackerman（双递归函数）、全排列、整数划分
递归的优缺点
优点：
结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性
因此它为设计算法、调试程序带来很大方便
缺点：
递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多
怎样将递归算法转化为非递归算法？
分治法的适用条件
原问题可分割成k个子问题，1<k<=n
这些子问题都可解
可利用这些子问题的解求出原问题的解
问题可以分割为若干个规模较小的（相同）问题
问题的规模缩小到一定的程度就可以容易地解决
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
重复子问题适合什么算法解决？
分治法的复杂性分析
假设
分治法将规模为n的问题分成k个规模为n／m的子问题
分解阀值n0=1
解决规模为1的问题耗费1个单位时间
将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f(n)个单位时间
分治法举例：二分搜索、大整数乘法、Strassen矩阵乘法、棋盘覆盖、归并排序
第三章 动态规划
动态规划算法的基本步骤
1.分析最优解的结构
找出最优解的性质，并刻划其结构特征
2.建立递归关系
递归地定义最优值
3.计算最优值
以自底向上的方式计算出最优值
4.构造最优解
根据计算最优值时得到的信息
分析最优解的结构
分析最优解的结构
计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的
矩阵连乘计算次序问题的最优解包含着其子问题的最优解
这种性质称为最优子结构性质
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征
找出最优解的性质，并刻划其结构特征
建立递归关系
递归地定义最优值
计算最优值
以自底向上的方式计算出最优值
构造最优解
根据计算最优值时得到的信息
动态规划基本要素：最优子结构、重叠子问题
1.最优子结构
原问题的最优解包含着其子问题的最优解
在分析问题的最优子结构性质时，所用的方法具有普遍性
首先假设由原问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾
2.重叠子问题
递归算法求解某些问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次
动态规划算法，每一个子问题只解一次，而后将其解保存在一个表格中
当再次需要解此子问题时，只是简单地用常数时间查看一下结果
示例：矩阵连乘、0-1背包、最长公共子序列、最大子段和
第四章 贪心
贪心算法的本质：做出在当前看来最好的选择
贪心算法基本要素：最优子结构性质、贪心选择性质
1.最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征
2.贪心选择性质：
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解
通常用反证法证明
贪心算法与动态规划算法的另一个区别在于解决问题的方式
动态规划算法通常以自底向上的方式解各子问题
从最小规模问题开始解决问题
贪心算法则通常以自顶向下的方式进行
以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题
示例：活动安排、(普通)背包、最优装载、哈夫曼树、单源最短路径
第五章 回溯法
具有限界函数的深度优先搜索法
回溯法的基本思想：
1.针对所给问题，定义问题的解空间
2.确定易于搜索的解空间结构
3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
3.1用约束函数在扩展结点处剪去不满足约束的子树
3.2用上界函数剪去得不到最优解的子树
扩展结点：一个正在产生儿子的结点称为扩展结点
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点：一个所有儿子已经产生的结点称做死结点
示例：0-1背包、n后问题
第六章 分支界限
广度优先或最小耗费（最大效益）优先的方式搜索解空间树
先入先出队列式分支限界、优先队列式分支限界：
常见的两种分支限界法
队列式(FIFO)分支限界法：将活结点表组织成一个队列，按照队列先进先出原则选取下一个节点为扩展节点
优先队列式分支限界法：将或节点表组织成一个优先队列，并按优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
与回溯法相似，分支限界法在寻求问题的最优解时，可以用限界函数加速搜索
该函数给出每个可行结点相应的子树可能获取的最大/小值
分支限界法和回溯法的关系
分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法
一般情况下，分支限界法与回溯法求解目标不同
回溯法的求解目标：找出解空间树中满足约束条件的所有解（从中选优）
分支限界法的求解目标：找出满足约束条件的一个解
也可以找出所有解，但有时效率不如回溯法，尤其当使用优先队列时
由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同
回溯法：以深度优先的方式搜索解空间树
分支限界法：以广度优先或以最小耗费优先的方式搜索解空间树
在分支限界算法中，用（优先）队列存储所有的活结点
分支限界法的基本思想
1.根结点入队
2.从活结点表（队列）中取下一结点（出队）成为当前扩展结点
3.如果该结点为孩子结点，判断并记录最优值和最优解
4.否则，一次性产生其所有孩子结点，舍弃导致不可行解或导致非最优解的孩子结点，将其余孩子结点加入活结点表中
5.重复上述2-4，直到找到所需的解或活结点表为空时为止
搜索方式
解题目标
示例：0-1背包
第七章 机器学习
基本概念和术语
研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能
致力于研究如何通过计算机手段，利用经验来改善系统自身的性能
经验是什么？
怎样改善自身的性能？
怎样判断性能的改善？
数据集、样本、特征、标签、训练集、测试集
数据集 data set
每条记录称为一个实例 instance 或样本 sample
描述一个事件或对象
每条记录包含若干属性 attribute 或 特征 feature
反映事件或对象在某方面的表现或性质
具有n个特征的样本可以用n维空间的一个点来表示
样本 特征向量 (x1, x2, …, xn)
从数据中学习得到模型的过程称为学习 learning 或训练 training
通过执行某个算法
训练的结果需要进行测试 testing
一般情况下，数据分为2部分
训练过程中使用的数据称为训练数据（训练样本、训练集）
测试过程中使用的数据称为测试数据（测试样本、测试集）
关于样本结果的信息称为标记 label (y)
算法分类
根据训练数据是否有标记信息，学习任务大致划分为两大类
1.监督学习：一般用于预测任务
1.1分类：欲预测的是离散值
1.2回归：欲预测的是连续值
2.非监督学习：一般用于描述任务
2.1聚类：将数据集中的样本分成若干组
2.2关联：数据样本之间的关联
监督学习
分类：KNN、决策树
分类算法举例：KNN
K最近邻(kNN，k-Nearest Neighbor)分类算法是分类技术中最简单的方法之一
算法的核心思想是：如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性
理论上比较成熟
比较适合类域的交叉或重叠较多的待分样本集来
决策树
决策树算法通过对训练集的学习,挖掘出有用的规则,用于对新集进行预测
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别
回归
非监督学习
聚类：K-Means
聚类分析（Cluster Analysis）将数据划分成不同的组/簇
组内相似、组间不同
理解
生物系统分类、发现类似功能的基因组
分类页面便于搜索
疾病的不同的类别
精准营销
总结
减小数据数量
/**********/
假设要把样本集分为k个簇，算法描述如下
适当选择k个簇的初始形心；
对任意一个样本，求其到k个形心的距离，将该样本归类到距离最小的形心所在的簇；
利用均值等方法更新该簇的形心值；
重复2-3直至所有的k个簇形心更新稳定或误差平方和最小
误差平方和即簇内所有点到形心的距离之和
最大优势：简洁和快速
关键：初始中心的选择和距离公式。
关联
优点
算法逻辑简单，易于实现
算法稳定，健壮性比较好
建模和分类速度快
可用少量数据建模
缺点
条件独立
常用于文档分类和垃圾过滤
一些重要的编程题可能会考的（PPT上有的）：
- 递归 F(n)=11F(n-1)+F(n-2) n=0 n=1 n>1
int factorial(int n)
{
if (n == 0) return 1;
return n*factorial(n-1);
}
- Hanoi塔问题
// 将n个圆盘从A移到B，使用辅助塔座C
void hanoi(int n, int a, int b, int c) {
if (n > 0) {
hanoi(n-1, a, c, b);
move(a,b);
hanoi(n-1, c, b, a);
}
}
- 分治法的基本步骤
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //解决小规模的问题
divide P into smaller subinstances P1,P2,...,Pk；//分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //递归地解各子问题
return merge(y1,...,yk); //将各子问题的解合并为原问题的解
}
- 归并排序（递归）
void MergeSort(Type a[], int left, int right){
if(left>=right) return; // 解决一个元素的问题
mid=(left+right)/2; // 中间点作为分割点
mergeSort(a, left, mid); // 分治解决问题1
mergeSort(a, mid+1, right); // 分治解决问题2
merge(a, left, mid, right);
//合并a[left:mid], a[mid+1, right]
}
- 二分查找（递归）
int bsearch_r(data[], low, high, key){
if(low>high) return -1; // 问题规模为0
mid = (low+high)/2; // 分割
if(key==data[mid]) return mid; // 规模为1
else if(key<data[mid])
return bsearch_r(data, low, mid-1, key); // 规模为n/2
else return bsearch_r(data, mid+1, high, key); // 规模为n/2
}
- 棋盘覆盖
chessBoard(P){
if ( | P | <= 1) return;
t=++tile; // t为骨牌编码，tile为全局变量，初始化为0
将P分割成P1,P2,P3,P4；
for (i=1,i<=4,i++){
if (Pi为非特殊棋盘) {
用t号骨牌，对Pi最靠近分割中心的单元进行覆盖，
使之成为特殊棋盘;
}
chessBoard(Pi);
}
}
void chessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
t = ++tile; s = size/2;
if (特殊方格在1区)
chessBoard(tr, tc, dr, dc, s);
else {
用 t 号L型骨牌覆盖1区右下角
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (特殊方格在2区)
chessBoard(tr, tc+s, dr, dc, s);
else {
用 t 号L型骨牌覆盖2区左下角
chessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (特殊方格在3区)
chessBoard(tr+s, tc, dr, dc, s);
else {
用 t 号L型骨牌覆盖3区右上角
chessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (特殊方格在4区)
chessBoard(tr+s, tc+s, dr, dc, s);
else {
用 t 号L型骨牌覆盖左上角
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}
- 归并排序
void MergeSort(Type a[], int left, int right){
if(left>=right) return; // 解决一个元素的问题
mid=(left+right)/2; // 中间点作为分割点
mergeSort(a, left, mid); // 分治解决问题1
mergeSort(a, mid+1, right); // 分治解决问题2
merge(a, left, mid, right);
//合并a[left:mid], a[mid+1, right]
}
- 归并排序 – 合并
void Merge(int a[], int left, int mid, int right){
int i=left, j=mid+1, k=0;
while((i<=mid)&&(j<=right))
if(a[i]<=a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
while(i<=mid) b[k++] = a[i++];
while(j<=right) b[k++] = a[j++];
i = left; k = 0;
while(i<=right) a[i++] = b[k++];
}
- 快速排序
void QuickSort (int a[], int p, int r){
if (p<r) {
int q=Partition(a,p,r);
QuickSort (a,p,q-1); //对左半段排序
QuickSort (a,q+1,r); //对右半段排序
}
}
int Partition (int a[], int p, int r)
{ // 以a中的第一个元素x作为基准
// 将< x的元素交换到左边区域
// 将> x的元素交换到右边区域
int i = p, j = r + 1;
Type x=a[p];
while (true) {
i++; while (a[i] <x) i++;
j--; while (a[j] >x) j--;
if (i >= j) break;
Swap(a[i], a[j]);
}
a[p] = a[j];
a[j] = x;
return j; // 返回基准的最终位置
}
/**************/
int RandomizedPartition (int a[], int p, int r)
{
int i = Random(p,r);
Swap(a[i], a[p]);
return Partition (a, p, r);
}
- 矩阵连乘问题
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; // 为对角线赋值
for (int r = 2; r <= n; r++){ // r为问题规模，从2个矩阵相乘开始算起
for (int i = 1; i <= n - r+1; i++) { // n-r+1 为子问题的个数
int j=i+r-1; // j-i =r-1
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i;
for (int k = i+1; k < j; k++) { // 找最小值
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;}
}}}}
- 0-1背包问题
j=C;
for(i=n;i>0;i--){
if(m[i][j]>m[i-1][j]){
x[i]=1;
j=j-w[i];
}
else x[i]=0;
}
- 最长公共子序列——计算最优值
void LCSLength(int m，int n，char *x，char *y，int **c，int **b){
// m, n: 分别为序列X和Y的长度
// c: Xi或Yj的最长公共子序列的长度 b: 用来还原最长公共子序列
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) { // i-1行的值较大
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; } // j-1列的值较大
}
}
- 最长公共子序列——构造最优解
void LCS(int i，int j，char *x，int **b){
if (i ==0 || j==0) return;
if (b[i][j]== 1){
LCS(i-1，j-1，x，b);
printf(“%c ”, x[i]);
}
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b); }
- 最大子段和——枚举法1
int MaxSum(int n, int *a, int& besti, int& bestj) {
int sum = 0;
for(int i=0; i<n; i++) { //起始项
for(int j=i; j<n; j++){ //结束项
int thissum = 0;
for(int k=i; k<=j; k++){ //求和
thissum += a[k];
}
if(thissum>sum){ //求最大子段和
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
- 最大子段和——枚举法2
int MaxSum(int n,int *a,int& besti,int& bestj) {
int sum = 0;
for(int i=0; i<n; i++){ //控制求和起始项
int thissum = 0;
for(int j=i; j<=n; j++){ //控制求和结束项
thissum += a[j];//求和
if(thissum>sum) {
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
- 递归回溯
void backtrack (int t) {
if (t>n) output(x);
else
for (int i=f(n,t);i<=g(n,t);i++) {
x[t]=h(i);
if (constraint(t)&&bound(t)) backtrack(t+1);
}
}
- 迭代回溯
void iterativeBacktrack () {
int t=1;
while (t>0) {
if (f(n,t)<=g(n,t))
for (int i=f(n,t);i<=g(n,t);i++) {
x[t]=h(i);
if (constraint(t)&&bound(t)) {
if (solution(t)) output(x);
else t++; }
}
else t--;
}
}
- n后问题
bool Place(int k) { // 判断x[k]是否满足约束条件
for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
- n后问题（递归）
void Backtrack(int t) {
if (t>n) {
sum++;
output(x);
}
else
for (int i=1;i<=n;i++) {
x[t]=i; //第t个皇后放在第i列上
if (Place(t)) {
Backtrack(t+1);
}
}
}
}
- n后问题（迭代）
void Backtrack(void){
x[1]=0;
int k=1;
while(k>0){
x[k]+=1;
while( (x[k]<=n) && !(Place(k)) ) x[k]+=1;
if(x[k]<=n) //如果n皇后所在的列小于n
if(k==n) {
sum++;
output(x);
}
else{
k++;
x[k]=0;
}
else k--;
}
}
- 0-1背包问题（队列式）
branchknap(float w[],float v[]){
根结点入队
while(队列不为空){
Node *current = 出队 // 扩展结点
if (current为叶子结点){
if (current路径能得到最优值)
更新bestv和bestx;
}
else{
if (current的左孩子可行) 左孩子入队
右孩子入队
}
}
}
- 0-1背包问题（优先队列式）——可进一步优化
branchknap(float w[],float v[]){
根结点入队
while(队列不为空){
Node *current = 单位重量价值最大元素出队 // 扩展结点
if (current为叶子结点){
if (current路径能得到最优值)
更新bestv和bestx;
}
else{
if (current的左孩子可行) 左孩子入队
if (current的右孩子有可能产生最优解) 右孩子入队
}
}
}
- 0-1背包问题（优先队列式）——优化后
branchknap(float w[],float v[]){
根结点入队
while(队列不为空){
Node *current = 单位重量价值最大元素出队 // 扩展结点
if (current为叶子结点){
if (current路径能得到最优值)
更新bestv和bestx;
}
else{
if (current的左孩子可行并有可能产生最优解)
左孩子入队
if (current的右孩子有可能产生最优解) 右孩子入队
}
}
}