算法复习笔记

把自己最近学习算法的笔记整理出来，供以后复习。

1.   六大算法包含什么问题

分治	动态规划	贪心	回溯	分支限界	随机化
二分搜索技术	矩阵连乘	活动安排问题	图的m着色问题		数值随机化
合并排序&快速排序	最长公共子序列	最小生成树	N皇后		蒙特卡罗
大整数乘法	最大子段和	多机调度问题	连续邮资问题		拉斯维加斯
线性时间选择	凸多边形最优三角剖分	哈夫曼编码	符号三角形		舍伍德
Strassen矩阵乘法	多边形游戏		圆排列问题
最接近点对问题	图像压缩
棋盘覆盖	最优二叉搜索树
循环赛日程	流水作业调度

 

2.   可用多种算法解决的问题整理

a)      装载问题：贪心+回溯+分支限界

b)      单源最短路径问题：贪心+分支限界

c)       最大团问题：回溯+分支限界

d)      旅行售货员：回溯+分支限界

e)      布线问题：动态规划+分支限界

f)        电路板排列问题：回溯+分支限界

g)      0-1背包问题：回溯+分支限界+动态规划

【注】贪心可以解决部分背包问题，但无法解决0-1背包问题

h)      批处理作业问题：回溯+分支限界

 

3.   六大算法综述

a)     分治法

【基本思想】将一个大问题分解为多个子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

【基本步骤】

    ①   分解：将原问题分解成若干个规模较小，相互独立，与原问题相同的子问题

    ②   解决：若子问题容易解决则解决，否则递归解决各个子问题

    ③   合并：将各个子问题的解合并为原问题的解

      【分治法适合问题特征】

    ①   该问题可以分解为若干较小且易解的相同问题，即该问题具有最优子结构性质

    ②   该问题分解出的子问题的解可以合并为该问题的解

    ③   该问题分解出的各个子问题是相互独立的，即子问题之间不包含公共子问题

b)     动态规划

【基本思想】和分治法类似，其思想也是将待求解问题分解成多个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。与分治法不同的是，动态规划分解得到的子问题往往是不互相独立的。此时若用分治法，那么子问题就会分解过多，导致耗费时间。除此外，因为子问题有相同的，所以动态规划会将子问题的答案保存到某张表，再次需要时找出来就是了。

【基本步骤】

    ①   找出最优解性质，并刻画其结构特征

    ②   递归的定义最优值

    ③   以自底向上的方式计算最优值

    ④   根据计算最优值得到的信息，构造最优解

    【注】步骤1~3是动态规划算法的基本步骤，在只需要求出最优值的情形，步骤4可省略

    【两个基本要素】这是使用动态规划的象征

    ①   最优子结构：通过最优的子问题得到的父问题的解仍然是最优的即称具有最优子结构。因为最优分为局部最优和全局最优，而局部最优不一定引导出全局最优。

    ②   重叠子问题：解问题时，每次产生的子问题并不总是新问题，动态规划利用这种重叠性质，对每个算法只解一次，而后将其解保存在一张表里，之后需要就查看。

            【注1】证明具有最优子结构的方法：假设由问题的最优解导出的其子问题的解不是最优的，然后再去设法说明在这个假设下可构造出比原问题最优解更好的解，导致矛盾。

            【注2】重叠子问题性质是动态规划和分治法相比最大的区别

    【保存答案两种方法】

    ①   使用单独一种数据结构来保存解，即显示表达

    ②   使用备忘录：使用哈希表保存已解决的子问题答案，但和一般动态规划不同的是。备忘录的递归方法是自顶向下的，而动态规划是自底向上的。即隐式表达。

     【最优化原理】假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。此即最优化

     【小结】动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。

c)      贪心

【基本思想】当一个问题具有最优子结构时，可考虑动态规划。但有时有更简单有效的方法。即贪心，其思想是：并不从全局最优上考虑，而是每次都做当前的局部最优选择。虽然贪心不是对所有问题都能够得到全局最优解，但事实上很多问题都能够得到。

【两个基本要素】

    ①   贪心选择性质：该性质是说所求问题的整体最优解可以通过一系列局部最优的选择来达到。而要确定一个问题是否具有这种性质，必须证明每一步所做的贪心选择最终会导致全局最优解。

    ②   最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。这种性质是问题可用动态规划或贪心解决的重要特征。

d)     回溯

【基本思想】回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。若肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按照深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。      

e)     分支限界

【基本思想】类似于回溯法，这也是一种在问题的解空间上搜索问题解的算法。然而与回溯法不同的是，分支限界一般用广度优先或最小耗费方法来搜索。相对而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

 【搜索策略】在扩展结点（当前结点）处，先生成其所有的儿子结点，然后再从当前的活结点(当前结点的子结点)表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值。并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上最优解的分支推进。以便尽快地找出一个最优解。

 【常用两种选择扩展结点的方法】

    ①   队列式分支限界：即从活结点表中取出结点的顺序与加入的顺序相同。

    ②   优先队列式分支限界：将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

  【基本步骤】

    ①   针对所给问题定义问题解空间

    ②   确定易于搜索的解空间结构

    ③   以广度优先或最小耗费优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

f)       随机化算法

【特点】允许算法在执行过程中随机的选择下一个计算步骤，因此随机化算法可较大的降低算法复杂度。并且，对所解的问题的同一实例用同一随机化算法求解两次可能得到完全不同的效果。

【几个典型】

    ①   数值随机化：用于数值问题的求解，往往得到的是近似解。且精度随时间的增加会不断提高

    ②   蒙特卡洛：一定有解。但这个解未必是正确的，其正确率随时间增加而提高。

    ③   拉斯维加斯：不会得到不正确的解，只要找到，一定正确，但有时会找不到解。对于所解问题的任一实例，用统一拉斯维加斯算法反复对该实例求解多次，可使求解失效的概率任意小。

    ④   舍伍德：总能求得问题的一个解，且所得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将其改造成一个舍伍德算法，消除或减少问题的好坏实例间带来的差别。

4.   几种算法之间的比较

a)     动态规划和分治比较

【相同点】都是将待求解的问题分解成若干子问题，先求解子问题，然后从这些子问题的解来得到原问题的解。

【不同点】适合于动态规划求解问题经分解得到的子问题往往不是互相独立，而分治常常为互相独立的。

b)     动态规划和贪心比较

【相同点】都需要最优子结构性质，都用来求最优化问题

【不同点】

    ①   动态规划的条件有子问题的重叠性质，而贪心的条件有贪心选择性质。

    ②   动态规划是自底向上求解，而贪心是自顶向下求解

    ③   动态规划每一步做选择要依赖于子问题的解，而贪心不依赖。

c)      回溯和分支限界比较

【相同点】都是在问题的解空间树中搜索问题解的算法

【不同点】

    ①   求解目标不同：回溯目标是找出解空间中满足约束条件的所有解，而分支限界是找出一个，即某种意义下的最优解

    ②   搜索方式不同：回溯法以深度优先，而分支限界以广度优先或最小耗费优先

    ③   结点储存特性不同：回溯法中，活结点的所有可行子结点被遍历后才从栈中弹出；分支限界中，每个结点只有一次成为活结点的机会。

    ④   存储空间的要求不同：回溯一般使用堆栈，而分支限界使用队列或优先队列

 

5.   子集树排列树相关概念

a)      解空间

解空间就是所有解的可能取值构成的空间，一个解往往包含了得到这个解的每一步，往往就是对应解空间树中一条从根节点到叶节点的路径。子集树和排列树都是一种解空间。

b)      约束条件

约束条件Constraint是问题中就限定好的条件，比如在装载问题中装入第i个物体后不能超过背包总容量时才考虑装入它，即搜索左子树的情况。

c)      限界条件

限界条件Bound是需要自己挖掘的一个界，可能是上界或者下界，当问题中的某个值在走向某棵子树时会超出这个界限时，就可以放弃这棵子树了。

用这两个条件可以对解空间树进行剪枝，这样回溯法才有别于枚举。

d)      子集树

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2^n个叶结点(完全二叉树)。遍历子集树需O(2^n)计算时间

e)      排列树

当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树

称为排列树。排列树通常有n!个叶节点。也就是说n个元素的每一个排列

都是解空间中的一个元素。遍历排列树需O(n！)计算时间

 

6.   O()，Ω( )，θ( )的定义

a)      O( ):若存在常数C和自然数N0，使当N>=N0时有f(N)<C*g(N),则称f(N)有上界，记为f(N) =O(g(N))

b)      Ω( ):若存在常数C和自然数N0，使当N>=N0时有f(N)>=C*g(N),则称f(N)有下界，记为f(N) = Ω(g(N))

c)       θ( ):定义f(N) = θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))时成立，此时称f(N)和g(N)同阶

     【注意】N! = O(N^n)

7.   主定理

8.   算法相关概念

a)      计算机求解问题步骤：

问题分析，数学模型建立，算法设计与选择，算法指标，算法分析，算法实现，程序调整，结果整理文档编制。

b)      算法定义：

算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

c)      算法三要素：

操作，控制结构，数据结构

d)      算法五属性：

    有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

    确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口

    可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

    输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

    输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

e)      衡量算法时间效率的两种方法：

分事前分析法和事后分析法两种。事后分析法先将算法用程序设计语言实现，然后度量程序的运行时间。事前分析法算法的时间效率是问题规模的函数，假如，随着问题规模n的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=○(f(n))    称T(n)为算法的渐进时间复杂度。简称时间复杂度。

 

9.   哈夫曼树相关题目

【例1】某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码

【例】考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。这些字符出现在文件中

的频数之比为 20:10:6:4:44:16。

（1）简述使用哈夫曼算法构造最优编码的基本步骤；

（2）构造对应的哈夫曼树，并据此给出a,b,c,d,e,f 的一种最优编码。

         【解】

1） 哈夫曼算法是构造最优编码树的贪心算法。其基本思想是：

“两个对应+一个重复”

所有字符对应n 棵树构成的森林，每棵树只有一个结点，权值为对应字符的频率。重复下列过程n-1 次： 将森林中的权值最小的两棵树进行合并产生一个新树，该新树根的两个子树分别是参与合并的两棵子树，权值为两个子树根权之和。

2） 根据题中数据构造哈夫曼树如下图所示。

由此可以得出 a,b,c,d,e,f 的一组最优的编码：01,0000,00010,00011, 1,001。

10.  算法题汇总

a)     排列问题（分治）

template<classType>

voidPerm(Type list[ ],  int k, int m )

{ //产生[list[k:m]的所有排列

    if(k==m)

     {  //只剩下一个元素

         for (int i=0;i<=m;i++)cout<<list[i];

         cout<<endl;

    }

    else //还有多个元素待排列，递归产生排列

       for (int i=k; i<=m; i++)

        {

           swap(list[k],list[i]);

           Perm(list,k+1,m);  

           swap(list[k],list[i]);        

         }

}

template<classType>

inline voidSwap(Type &a, Type &b){

       Type tmp = a;

       a = b;

       b = tmp;

}

       

b)     合并排序（分治）

1.     递归(合并排序是利用分治策略实现对n个元素进行排序的算法。基本思想是：将待排元素分成大小大致相同的两个子集合，并分别进行排序，最终将两个合并成最终结果)

template<class T>

voidmerge_sort(T a[], int left, int right)   //归并排序主函数，left和right分别为起始和终止的下标

{

   if(left < right){      //如果start=end直接返回，因为单个元素天然有序

        int i = (left+right)/2);    //求中点

        merge_sort(a, left, i);       //归并左半部分

        merge_sort(a, i+1, right);       //归并右半部份

        merge(a,b, left, i, right);     //合并两部分

              copy(a, b, left, right);      //复制回数组a

    }

}

 

2.     非递归(第一步，将待排序的元素序列一分为二，得到两个长度基本相同的子序列；第二步，对两个子序列分别排序，若子序列较长则继续细分重复以上一分为二的步骤，直至子序列的长度不大于1为止，此为关键步骤，需要将数列二分到每个子数列的长度不超过一为止，因为只有不大于一的数列可直接求解，这一点在之后过程会演示；第三步将排好序的子序列合并成一个有序数列，实现函数即为以上的merge函数)

template<classType>

void MergeSort(Type a[ ], int n){

       Type*b = new Type[n];

       int s = 1;

       while(s < n){

              MergePass(a,b, s, n);  //合并到数组b

              s+= s;

              MergePass(b,a, s, n);  //合并到数组a

              s+= s;

       }

}

//MergePass用于合并排好序的相邻数组段，具体合并算法有Merge实现

void Mergepass(Type x[], Type y[], int s, int n)

{

       int i=0;

       while(i<=n-2*s){

              Merge(x,y, i, i+s-1, i+2*s-1);

              i= i + 2*s;

       }

       if(i+s<n)

              Merge(x,y, i, i+s-1, n-1);

       else

              for(intj=i;j<=n-1;j++)

                     y[j]= x[j];

}

 

 

void Merge(Type c[], Type d[], int l, int m, int r)

{

       int i=1,j=m+1,k=1;

       while((i<=m)&&(j<=r)){

              if(c[i] <= c[j])

                     d[k++]= c[i++];  //注意这里k++ i++是先用再加，这

              else

                     d[k++]= c[j++];

       if(i>m)

              for(intq=j;q<=r;q++)

                     d[k++]= c[q];

       else

              for(intq=i;q<=m;q++)

                     d[k++]= c[q];

       }

}

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);

       }

}

       

d)     二分搜索技术（分治）

a)      【引】问题是给定一个排好序的n个元素，要求寻找x。首先可想到顺序搜索，但是这种方法没有利用排好序这个条件，其最坏情况下时间复杂度为O(n)。而二分搜索可以做好最坏情况下O(logn)。二分搜索就是将n个元素分成两半，比较中间元素a[n/2]和x，相等就结束了，如果x小，则去左边找，如果x大，去右边找。

【代码】

template<classT>

intBinarySearch(T a[ ], const T &x, int n){

       int lef = 0; int rig = n-1;

       while(lef <= rig){

              int mid = (lef + rig)/2;

              if(x == a[mid])

                     return mid; //找到了

              if(x > a[mid])

                     lef = mid + 1;

              else

                     rig = mid - 1;

       }

       return -1; //未找到

}

           

e)     最大子段和（动态规划）

【引】令b[j]表示以位置 j 为终点的所有子区间中和最大的一个子问题。假设j为终点的最大子区间包含了位置j-1，则以j-1为终点的最大子区间必然包括在其中。如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可。而如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大

【代码】

int MaxSum(int n, int *a){

       int sum =0,b = 0;

       for(int i=1;i<=n;i++){

              if(b>0)

                     b += a[i];

              else

                     b = a[i];

              if(b>sum)

                     sum = b;

       }

       returnsum;

}

 

f)       最大子矩阵和（动态规划）

【引】这是最大子段和推广到高维的情况。问题可描述为：给定一个m行n列的整数矩阵A，试求A的一个子矩阵，使其各项元素之和最大

【代码】

int MaxSum2(intm, int n, int**a)

{

       int sum = 0;

       int *b = new int[n+1];

       for(int i =1;i<=m;i++){

              for(intk=1;k<=n;k++) b[k] = 0;

              for(intj=i;j<=m;j++){

                     for(intk=1;k<=n;k++) b[k] += a[j][k];

                     int max = MaxSum(n, b);

                     if(max>sum) sum = max;

              }

       }

       return sum;

}

 

g)     子集树（回溯）

【引】如果一个问题的解的长度不是固定的，并且解和元素顺序无关，即可以从中选择0个或多个，那么解空间的个数将是指数级别的，为2^n,可以用下面的子集树来表示所有的解

【代码】

void backtrack(intt) {//表示访问到第t层,t从开始

       if (t > n)

              output(x);

       else

              for (int i = 0; i<= 1; i++) { //表示选或不选a[t]

                     x[t]= i;

                     if (constraint(t) && bound(t))

                            backtrack(t+ 1);

                }

}

 

h)     排列树（回溯）

【定义】如果解空间是由n个元素的排列形成，也就是说n个元素的每一个排列都是解空间中的一个元素，那么，最后解空间的组织形式是排列树

【代码】

void backtrack(intt)

{

   if (t > n)

        output(x);

   else

        for (int i = t; i <= n; i++)

        {

            swap(x[t], x[i]);

            if(constraint(t) && bound(t))

                        backtrack(t+ 1);

                   swap(x[t], x[i]);

     }

}

 

 

i)       N皇后（回溯）

【原理】一张图说明一切

我们在试探的过程中，皇后的放置需要检查他的位置是否和已经放置好的皇后发生冲突，为此需要以及检查函数来检查当前要放置皇后的位置，是不是和其他已经放置的皇后发生冲突

【代码】

#include<stdio.h>

#include<stdlib.h>

#define max 9

//sum用于描述解的可能的个数，每当输出一次复合要求的位置sum的数量就会被+1

int queen[max],sum=0; /* max为棋盘最大坐标*/

 

 

//此函数用于判断皇后当前皇后是否可以放在此位置

int PLACE(int n) /* 检查当前列能否放置皇后*/

{

    //queen[i] ==queen[n]用于保证元素不能在同一列

    //abs(queen[i] -queen[n]) == abs(n - i)用于约束元素不能在同一行且不能在同一条斜线上

    for(int i =0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后*/

          if(queen[i]== queen[n] || abs(queen[i] - queen[n]) == abs(n - i))

                 return0;

    return 1;

}

 

//核心函数，包含回溯法的思想

void NQUEENS(int n) /* 回溯尝试皇后位置,n为横坐标*/

{

    for(int i =0; i < max; i++)

    {

        //首先将皇后放在第列的位置，对于第一次来说是肯定成立的

        //所以第一次将皇后放在第行列的位置

        queen[n] = i; /*将皇后摆到当前循环到的位置*/

        if(PLACE(n))

        {

            if(n== max - 1)

                        sum++; /* 如果全部摆好，结果+1*/

            else

                NQUEENS(n + 1); /* 否则继续摆放下一个皇后*/

        }

    }

}

 

 

int main()

{

    NQUEENS(0); /* 从横坐标为开始依次尝试*/

    printf("\n");

    printf("总共的解法有%d种\n",sum);

    return 0;

}      

11.           小知识点

a)      递归概念：直接或间接的调用自身的算法称为递归算法，用函数自身给出定义的函数成为递归函数。

b)      怎么分治：最好让子问题的规模大致相同，将一个问题分成大小相等的k个子问题的处理方法是非常有效的。

c)       请说明动态规划为什么需要最优子结构性质：最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构.