Waylon Wang
Home Archives Friends
Home Archives Friends

算法分析设计

奇怪的笔记
有 N 人看过

Lecture 1 绪论

  1. 算法的五大特性：

    输入、输出、有穷性、确定性（无歧义）、可行性

  2. 算法设计的一般过程

    理解问题→预测所有可能地输入→在精确解和近似解中做选择→确定适当的数据结构→算法设计技术→描述算法→跟踪算法→分析算法的效率→根据算法编写代码

  1. 算法的描述方法
    • 用自然语言描述（粗线条描述算法思想）
    • 程序设计语言（能由计算机执行，但抽象性差）
    • 流程图（描述简单算法）
    • 伪代码（表达能力强，抽象性强，容易理解）
  2. 重要的问题类型
    • 查找问题
    • 排序问题
    • 图问题
    • 组合问题
    • 几何问题

Lecture 2 时间复杂度

  1. 运行时间=操作时间x操作次数

  2. 语句的频度：语句重复执行的次数

  3. 渐进时间复杂度

  4. 大O复杂度

  5. 指数时间算法→多项式时间算法

  6. 大O、大Ω、大Θ复杂度：

Lecture 3 蛮力法

  1. 应用：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配

  2. 蛮力法→扫描技术→遍历

  3. 蛮力法可以作为其类问题时间性能的底限，来衡量同问题的更高效算法

  4. 对于一个具有n个元素的集合，其子集数量是2^n，所以必然会导致一个Ω(2^n)的算法

  5. 组合问题：0/1背包，任务分配

    图问题： 哈密顿回路、TSP问题

    哈密顿回路：一个无向图，对所有顶点排列组合，哈密顿回路满足以下两个条件：（1）相邻顶点存在边 （2）首尾之间有边，复杂度为O(n!)

    TSP问题：从出发点走最后回到出发点，可能的解为(n-1)!/2个

Lecture 4 问题的解空间

  1. 搜索的空间就是解的空间，而搜索就是在解空间里找出需要的一个，对于大部分问题来说，解空间的规模为输入规模的指数函数。
  2. 寻找更有效的 搜索手段 是算法不断推进的源动力（PPT里出现了无数次……那就记下来吧）
  3. 解空间树（Solution Space Trees，也称为状态空间树），将搜索空间组织成一棵树，从根结点到叶子结点的路径构成解空间的一个可能解，提高搜索效率。
  4. 解空间树是虚拟的，不需要构造一棵真正的树，只要存储从根结点到当前结点的路径。
  5. 现实问题难以求解的原因：
    • 解空间规模太大
    • 实际问题随时间而改变
    • 实际问题存在很多约束条件（PPT上有分析约束条件的例题）

Lecture 5 回溯法

  1. 回溯法属于智能穷举搜索。

  2. 回溯法用 深度优先遍历 解空间树搜索解，在搜索到任意结点时先判断是否满足约束条件/是否超出函数的界（就是看这个东西符不符合条件，如果不符合就不再往下搜索）称为 剪枝(Pruning)

  3. 避免无效搜索的两种策略：

    • 用约束条件减去得不到可行解的子树

    • 用评估函数减去得不到最优解的子树

      这两类函数称为 剪枝函数(Pruning Function)

  4. 组合问题：八皇后问题（n x n的棋盘上，n个皇后不能出现在同一行同一列同一斜线上）第i个皇后在第i行第x_i列上则：

     bool Place(int k) //返回皇后k放在x[k]列会不会冲突
 {
     for(i=1;i<k;i++)
         if(x[k]==x[i]||abs(k-i)==abs(x[k]-x[i])
             return false;
         return true;
 }
 
 void Queue(int n)
 {
     for(i=1;i<n;i++)
             x[i]=0; //初始化
     k=1;
     while(k>=1)
     {
         x[k]=x[k]+1; //在下一列放置第k个皇后
         while(x[k]<=n&&!Place(k))
             x[k]=x[k]+1; //搜索下一列
         if(x[k]<=n&&k==n){
             for(i=1;i<n;i++)
                 cout<<x[i];
             return;
         }
         else if(x[k]<=n&&k<n)
             k=k+1; //放置下一个皇后
         else{
             x[k]=0; //重置x[k],回溯
             k=k-1;
         }
     }
 }

    图问题：四色问题→何连通图可以用不多于4中颜色对每一区域着色，使相邻区域着不同颜色

    图着色问题的应用：物资存储问题&会场安排问题、交通🚥问题、亚瑟王骑士宴会问题

    物资存储问题：（会场安排问题同理）

    有n种物资，其中两种不能放在同一间里，就把这两个点之间连一条线，连线的用不同的颜色涂色，最后顶点颜色数就是最少房间数

  5. 回溯法求解图着色问题：

     /*伪代码描述
     将数组color[n]初始化为0
     k=1
     while(k>=1)
         考察顶点k的着色和其他顶点是否冲突
             1.如果冲突->搜索下一颜色
             2.如果不冲突->如果顶点全部着色->返回数组color[n]
                             2.1->如果没有全部着色->2.1.1 如果k是一个合法着色
                                                                                 ->k=k+1，退回while
                                                                 ->2.1.2 如果不是
                                                                                 ->重置k的颜色，k=k-1
 */
 
 /*c++描述*/
 bool Ok(int k)
 {
     for(i=1;i<k;i++)
         if(c[k][i]==1&&color[i]==color[k])//连通且颜色一致
             return false;
     return true;
 }
 
 void GraphColor(int n,int c[][],int m)
 {
     for(i=1;i<=n;i++)
         color[i]=0;
     k=1;
     while(k>=1)
     {
         color[k]=color[k]+1;
         while(color[k]<=m)
             if Ok(k) break;
             else color[k]=color[k]+1; //搜索下一个颜色
         if(color[k]<=m && k==n) //成了之后输出
         {
             for(i=1;i<=n;i++) cout<<color[i];
             return;
         }
         else if(color[k]<=m && k<n)
             k=k+1; //处理下一个顶点
         else{
             color[k]=0;
             k=k-1; //回溯
         }
     }
 }

Lecture 6 分支限界法

  1. 分支限界法：去掉我们明知道不可能在其中找到最优解的搜索空间（根据计算出的特定解的代价减去部分分支）
  2. 文字描述：
    • 确定一个合理的 限界函数及界[down,up]
    • 根据 广度优先 遍历问题的解空间树，估算子结点的 评估函数的可能取值
    • 如果评估函数的可能取值 超出评估函数的界，就将其丢弃；否则将其加入 待处理结点 表（PT表）中
    • 依次从表中选取评估函数的值取得极值的结点成为当前 扩展结点
    • 重复上述过程
  3. 分支限界法对结点的处理是跳跃式的，所以求得最优解时无法求得最优解的各个分量，有两种方法解决这个问题：
    • 对每个扩展结点保存该结点到root的路径
    • 求得最优解时不断回溯到根结点，以确定最优解的分量
  4. 常见问题的限界函数：

  • 0-1背包(v当前价值，w当前重量，W背包总容量，后面的比值为现在放入的物品的价值/重量比)

  • TSP问题：

  • 任务分配问题：

  • 八数码问题：(g为深度，h为不正确的数字个数)

Lecture 7 分治法（Divide-and-Conuqer）

  1. 分治法就是把一个问题划分为k个更小规模的子问题（分→治→合）

  2. **递归( Recursion )**的两个基本要素

    • 边界条件：确定何时终止

    • 递归模式：大问题时如何分解为小问题的

      递归的经典问题：汉诺塔问题

      分治是一种思想，递归是一种手段

  3. 划分策略分为：-黑盒划分（根据问题的规模而不考虑划分对象的属性）-白盒划分（根据划分对象的特定属性值划分）

  4. 排序问题中的分治法：

    • 归并排序 Merge Sort（黑盒划分）时间复杂度O(nlog n)
    • 快速排序 Quick Sort （白盒划分）时间复杂度O(nlog_2n)~O(n^2)

  5. 组合问题中的分治法：

    • 最大子段和问题

        int MaxSum(int a[],int left,int right)
  {
      sum=0;
      if(left==right) //序列长为1
      {
          if(a[left]>0) sum=a[left];
          else sum=0;
      }
      else{
          center=(left+right)/2; //划分
          leftsum=MaxSum(a,left,center);
          rightsum=MaxSum(a,center+1,right);
          s1=0;lefts=0;
          for(i=center;i>=left;i--)
          {
              lefts+=a[i];
              if(lefts>s1) s1=lefts;
          }
          s2=0;rights=0;
          for(j=center+1;j<=right;j++)
          {
              rights+=a[j];
              if(rights>s2) s2=rights;
          }
          sum=s1+s2; //计算情况3的最大子段和
          if(sum<leftsum) sum=leftsum;
          if(sum<rightsum) sum=rightsum;//合并
      }
      return sum;
  }

    • 棋盘覆盖问题

    • 循环赛日程安排问题

Lecture 8 贪心法

  1. 贪婪算法：一步一步地构建问题的最优解决方案，其中每一步只需要考虑眼前的最优选择（通过局部最优达到全剧最优），大多数情况能达到近似最优解。

  2. 贪心算法要获得最优解的 条件：

    • 最优子结构性质（一个问题的最优解包含其子问题的最优解）
    • 贪心选择性质（问题的整体最优解可通过局部最优的选择得到）

  3. TSP问题的贪心策略：

    策略(1)： 从一个顶点出发每次都选择此点出发的最近的点

    时间复杂度O(n^2)

    策略(2)：在整个图中选择剩下的最短边，最终形成哈密顿回路

    时间复杂度O(nlog_2n)

  4. 图着色问题的贪心策略

    先从顶点开始，用颜色1着色，然后在图中找还能用颜色1着色的点上色，没有了之后再用颜色2从未着色的第一个点开始着色，♻️，以此类推。

     伪代码：
 1. color[1]=1; //把第一个点上1色
 2. for(i=2;i<=n;i++) //把其他顶点都初始化
 3. k=0;
 4. 循环(所有顶点都上色时退出循环)
         4.1 k++; //取下一个颜色
         4.2 for(i=2;i<=n;i++) //用k色为所有可以的点着色
                 4.2.1 如果vertice i已经着色,跳转4.2,看下一顶点
                 4.2.2 如果不冲突可以着色 则color[i]=k;
 5. 输出k;

  5. 最小生成树问题 Minimal Spanning Trees

    （计算机互相连线组网问题）

    两种贪心策略：

    （1） 最近顶点策略 ：任选一个顶点，把最近的顶点添加到生成树中，即Prim算法

    （2） 最短边策略：在所有边中找最短的边加入🌲中，即Kruskal算法

  6. 组合问题中的贪心算法：

    • 背包问题（三种策略：价值最大、重量最轻、单位重量价值最大）
    • 多机调度问题：最长处理时间作业优先

Lecture 9 动态规划法

  1. 斐波那契数列 1 1 2 3 5 8 13 21 …… 其中的任意一个数都叫斐波那契数。
  2. 动态规划=贪婪策略+递推（降阶）+存储递推结果
  3. 动态规划法求解的问题的具体特征：
    • 能够分解为相互重叠的若干子问题
    • 满足最优性原理（同最优子结构性质）（见上面的算法）