【算法分析与设计】期末总结

给大家推荐一个《算法分析设计》的视频，我觉得老师讲的很清晰：算法设计与分析MOOC-青岛大学-张公敬教授

算法概述

算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。

算法的特征：

• 有限性：算法必须在有限时间内终止；
• 正确性：算法必须正确描述问题的求解过程；
• 可行性：算法必须是可实施的；
• 算法可以有0个或0个以上的输入；
• 算法必须有1个或1个以上的输出。

算法与程序的关系：

区别：

• 程序可以不一定满足可终止性。但算法必须在有限时间内结束；
• 程序可以没有输出,而算法则必须有输出；
• 算法是面向问题求解的过程描述，程序则是算法的实现。

联系：

• 程序是算法用某种程序设计语言的具体实现；
• 程序可以不满足算法的有限性性质。

算法复杂性度量：

期望反映算法本身性能，与环境无关。
理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。
一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。

分治法

为什么使用分治法：求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法基本思想：

将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。
分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。
使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决；
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
3. 利用该问题分解出的子问题的解可以合并为该问题的解；
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。）

递归式求时间复杂度(看不懂证明 直接背公式结论)

$T(n)=aT(\frac{n}{b})+O(n^k)$，其中a>0，b>1。
$$T(n)=?\begin{array}{ll}O(n^k)& a<b^k\\ O(n^{k}lo{g}_{b}n)& a=b^k\\ O(n^{lo{g}_{b}a})& a>b^k\end{array}$$

算法实例

归并排序

private static void mSort(int[] arr, int left, int right) {
    if (left == right){
        return;
    }
    // 递归算法 主要负责切片 即把大的数组切成一个小数组
    int mid = left + ((right-left) >> 1);
    mSort(arr, left, mid);
    mSort(arr, mid+1, right);
    merger(arr, left, mid, right);
}
private static void merger(int[] arr, int left, int mid, int right){
    int[] temp = new int[right-left+1];
    int i = 0;
    int p1 = left; // 指针1从左数组开始遍历
    int p2 = mid + 1; // 指针2从右数组开始遍历
    while (p1 <= mid && p2 <= right){
        temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 左边还没遍历完
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    // 右边没遍历完
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }
    for (i = 0; i < temp.length; i++) {
        arr[left+i] = temp[i];
    }
}

快速排序

private void quickSort(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int left = L;
    int right = R;
    // 基准
    int temp = arr[left];
    while (left < right) {
        // 找到右侧第一个比基准小的元素
        while (left < right && arr[right] >= temp) {
            right--;
        }
        arr[left] = arr[right];
        // 找到左侧第一个比基准大的元素
        while (left < right && arr[left] <= temp) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = temp;
    // 最后left和right会收缩到基准点的正确位置处
    quickSort(arr, L, left - 1);
    quickSort(arr, left + 1, R);
}

动态规划

动态规划基本思想：

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

• 动态规划和分治的共同点在于，它们都是将一个大问题分解为了若干个子问题，然后求解子问题。而它们的区别，在于如何由子问题结果构造出最终结果。
• 从表面上看，分治使用的是递归，是一个自顶向下的过程；动态规划使用的是迭代。是一个自底向上的过程。

动态规划适用条件：

动态规划法解所能解决的问题一般具有以下两个基本因素：
一、最优子结构性质
当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。
二、重叠子问题性质
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

动态规划问题的特征：

1. 求解的问题是组合优化问题；
2. 求解过程需要多步判断，从小到大依次求解；
3. 子问题目标函数最优解之间存在依赖关系；

算法设计的基本步骤：

基本步骤：
（1）找出最优解的性质，并刻画其结构特征。（考察是否适合采用动态规划法。）
（2）递归地定义最优值。(建立递归式或动态规划方程)
（3）以自底向上的方式（或以自顶向下的备忘录方法）计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。

算法实例

矩阵连乘问题

问题描述：给定n个矩阵｛A1, A2, …, An｝，Ai的维数为pi-1×pi，Ai与Ai+1是可乘的，$i=1,2,\dots ,n?1$。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。设有5个矩阵A1A2A3A4A5连乘，找出最优计算次序以使得矩阵连乘所需要的计算次数最少。

public static String matrixChain(int p[]) {
    int n = p.length - 1;  //为p的实际最大下标
    int m[][] = new int[n + 1][n + 1];  // 存储每个子问题的最优解
    int s[][] = new int[n + 1][n + 1];  // 记录每个子问题的最优解对应的分割点
    for (int r = 2; r <= n; r++) {  // 从2开始，因为m[i][j]表示A[i:j]的乘法次数
        for (int i = 1; i <= n - r + 1; i++) {   // i表示起始位置
            int j = i + r - 1;   // j表示结束位置

            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];    // m[i][j]表示A[i:j]的乘法次数
            s[i][j] = i;    // s[i][j]记录分割点
            // 遍历所有可能的分割点k，计算将子问题划分为(A[i:k])*(A[k+1:j])的最优解，并更新m和s
            for (int k = i + 1; k < j; k++) { // 从分割点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]和s[i][j]
                    m[i][j] =  t ;
                    s[i][j] =  k ;
                }
            }
        }
    }
    String answer = "\n此矩阵连乘所需的最小次数为：" + m[1][n] + "\n";
    return answer;
}

0-1背包问题

问题描述：有n个物品，其中物品i的重量是 ，价值为 ，有一容量为C的背包，要求选择若干物品装入背包，使装入背包的物品总价值达到最大。

public static void knapsackDP(int[] w, int[] val, int m) {
    int n = w.length;   //物品的个数
    int[][] v = new int[n + 1][m + 1];  // v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
    int[][] records = new int[n + 1][m + 1];    // 记录放入物品的情况

    for (int i = 1; i < v.length; i++) {
        for (int j = 1; j < v[0].length; j++) {
            //当w[i]>j时,数组下标从1开始，所以-1
            if (w[i - 1] > j) {
                v[i][j] = v[i - 1][j];
            } else {//当j>=w[i]时,数组下标从1开始，所以-1
                if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                    v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                    records[i][j] = 1; //记录
                } else {
                    v[i][j] = v[i - 1][j];
                }
            }
        }
    }
    int i = records.length - 1; //行的最大下标
    int j = records[0].length - 1; //列的最大下标
    while (i > 0 && j > 0) { //从records的最后开始找
        if (records[i][j] == 1) {
            System.out.printf("第%d个物品放入到背包\n", i);
            j -= w[i - 1]; //w[i-1]
        }
        i--;
    }
}

电路布线问题

问题描述：在一块电路板的上、下两端分别有n个接线柱，用导线(i,π(i))将上端接线柱与下端接线柱相连，其中π(i)是{1,2,?,n}的一个排列。要求将这n条导线分布到若干绝缘层上，当且仅当两条导线之间无交叉才可以设在同一层。电路布线问题要求确定一个能够布设在同一层的导线集"Nets"={(i,π(i)),1≤i≤n}的最大不相交子集。设π(i)={8,7,4,2,5,1,9,3,10,6}。

电路布线问题最优值递归定义：

//下标从1开始,第一个数，0不算,总共10个数
int[] c = new int[]{0, 8, 7, 4, 2, 5, 1, 9, 3, 10, 6};
public static void MNS(int[] c,int[][] size){
    int n = c.length-1;
    for(int j=0;j<c[1];j++){//i=1时，分了两种情况，分别等于0,1
        size[1][j]=0;
    }
    for(int j =c[1];j<=n;j++){
        size[1][j]=1;
    }
    for(int i =2;i<n;i++){//i大于1时，同样分了两种情况(当i=n时单独计算，即此方法最后一行)
        for(int j=0;j<c[i];j++){//第一种
            size[i][j]=size[i-1][j];
        }
        for(int j=c[i];j<=n;j++){//第二种
            size[i][j]=Math.max(size[i-1][j], size[i-1][c[i]-1]+1);
        }
    }
    size[n][n]=Math.max(size[n-1][n], size[n-1][c[n]-1]+1);
}
//构造最优解
public static int traceback(int[] c,int[][] size,int[] net){
    int n=c.length-1;
    int j=n;
    int m=0;
    for(int i=n;i>1;i--){
        if(size[i][j]!=size[i-1][j]){
            net[m++]=i;
            j=c[i]-1;
        }
    }
    if(j>=c[1])
        net[m++]=1;
    System.out.println("最大不相交连线分别为：");
    for (int t = m - 1; t >= 0; t--) {
        System.out.println(net[t]+"  "+c[net[t]]);
    }
    return m;
}

贪心算法

贪心算法基本思想：

当一个问题具有最优子结构性质时，可用动态规划方法求解，但有时会有更简单有效的方法。顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法中，较大子问题的解恰好包含了较小子问题的解作为子集，这与动态规划算法设计中的优化原则本质上是一致的。
动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑到它的所有子问题的优化函数值，然后从中选出最优的结果；贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当时情况采取“只顾眼前”的贪心策略决定取舍。

1. 贪心选择性质
   所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。

2. 最优子结构性质
   当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。在活动安排问题中，其最优子结构性质表现为：若A是对于E的活动安排问题包含活动1的一个最优解。则相容活动A’=A-{1}是活动安排问题E’={i∈E: si>=f1}的一个最优解。

算法实例

活动安排问题

问题描述：设在活动安排中，每个活动i都有一个开始时间s_i和一个结束时间f_i，且s_i<f_i，即每个活动在一个半闭区间[s_(i ),f_i)占用资源，如表1和图1所示。求最优活动安排方案，使得安排的活动个数达到最多。

证明活动安排问题的贪心选择性质。

1. 假设有一个最优解A，其活动是以结束时间非递减序进行排列的。再假设A中的第一个活动是K。
2. 我们通过贪心选择选择到的第一个活动记为活动1。若K=1，则A是以活动1开始的；若K≠1，则用活动1替换掉A中的活动K，因为结束时间end[1]≤end[K]，活动1能与A中其他活动相容。
3. 现在，我们将A划分为两个集合：B和C。
   ? 集合B包含了活动1和与活动1相容的活动，即B={i∈A|start[i]≥end[1]}。
   ? 集合C包含了A中剩余的活动，即C=A-B。
4. 我们可以发现，集合B中的任意两个活动之间都是相容的，因为它们在A中是以结束时间非递减序进行排列的。如果我们将活动1替换回A中的活动K，同样可以保证A中的活动是以结束时间非递减序进行排列的。所以，我们可以得出结论：集合B中的活动是一个最优解。
5. 根据贪心选择性质，我们总是选择结束时间最早的活动作为活动1，因此我们可以得到一个贪心选择开始的最优活动安排方案。这证明了活动安排问题具有贪心选择性质。

证明活动安排问题的最优子结构性质。

1. 假设我们有一个活动安排问题的最优解A，并且A中的活动是按照结束时间的非减序排列的。现在，我们选择一个活动K作为贪心选择的对象。然后，我们将K从A中删除，得到一个新的活动安排集合A’。
2. 现在，我们已经通过贪心选择从A中删除了活动K。那么，我们可以观察到，A’中的活动与K是相容的，也就是说，它们可以在同一时间内进行。这意味着，K可以添加到A’中，并且不会破坏A’的相容性。
3. 因此，我们可以得出结论：通过贪心选择做出的每一次选择都会将问题化简为一个更小的与原问题具有相同形式的子问题。也就是说，我们可以每次选择一个活动，然后将问题化简为一个新的活动安排问题，直到所有的活动都被安排好为止。这就是活动安排问题的最优子结构性质。

public static int greedySelector(int[] s, int[] f, boolean[] a){
    int n = s.length-1;
    a[1] = true;
    int j = 1, count=1;
    for (int i = 2; i <=n ; i++) {
        if(s[i]>=f[j]){
            a[i] = true;
            j = i;
            count++;
        }else {
            a[i] = false;
        }
    }
    return count;
}

最小生成树问题

问题描述：设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

Prim算法

Kruskal算法

回溯法

回溯法基本思想：

回溯法实际上是一个类似穷举的搜索尝试过程，主要就是在搜索尝试过程中寻找问题的解，当发现已不满足解条件时，就回退，尝试别的路径。回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在当前节点（扩展节点）处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。

两类典型的解空间树:

1. 子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶结点
2. 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。

回溯算法()
	如果到达叶子结点：
		输出最优解
	如果没有到达叶子结点：
		如果当前顶点与当前团每点有边连接：//对左子树的判断
			进入左子树，x[i]=1
			进行处理
			进行下一层的递归求解(i+1)//进入回溯算法(i+1)
			将处理回退到处理之前
		如果右子树中可能含有最优解cn+n-i>bestn：//对右子树的判断
			进入右子树；进行下一层(i+1)//进入回溯算法(i+1)

算法实例

批作业调度问题

问题描述：设有 n个作业{J1,J2,……Jn}需要处理，每个作业Ji（1≤ i ≤ n）都有两项任务组成。两项任务需要分别在2台机器即机器1和机器2上处理。要求每个作业Ji 的第一项任务在机器1上处理，第二项任务在机器2上 处理，并且第一项任务在机器1上处理完后，第二项任务才能在机器2上开始处理。规定每个作业Ji用 f(1,i)记录其在机器1上的处理时间（该时间是指从机器1启动到该作业完成的时间）。每个作业Ji用f(2,i)记录其在机器2上的处理时间（该时间是指从机器2启动到该作业完成的时间）。不同的作业调度方案处理完成所有作业所需的时间显然不同。批处理作业调度要求制定最佳作业调度方案，使其完成的时间和最小。有3个作业{J1,J2,J3}需要处理，作业Ji在机器1和机器2上的处理时间如下图。找出最优调度方案。

public void backtrack(int i){
   //搜索第i个结点
   if(i>n){ //i>n说明已到达叶结点
      for(int j=1;j<=n;j++) {
         bestx[j]=x[j];//获取当前的最优调度方案
      }
      bestf=f;//获取当前的最优值
   }
   else{
      for(int j=i;j<=n;j++){//调度每个作业
         //作业x[j]在第一台机器的时间
         f1+=m[x[j]][1];
         //f2[i]等于f2[i-1]和f1中较大者加上作业x[j]在第2台机器的时间
         f2[i]=( (f2[i-1]>f1) ? f2[i-1] : f1 ) + m[x[j]][2];
         f+=f2[i];                
         if(f<bestf){//如果搜索结果小于当前最优解，则继续向下搜索
            swap(x,i,j);
            backtrack(i+1);
            swap(x,i,j);
         }
         //往回走时，还原数值
         f1-=m[x[j]][1];
         f-=f2[i];
      }
   }
}

最大团问题

问题描述：一个无向图中，满足两两之间都有边连接的顶点的集合，被称为该无向图的团

public void backtrack(int i) {
    if (i > n) {
        for (int j = 1; j <= n; j++) {
            bestx[j] = x[j];
            System.out.print(x[j] + " ");
        }
        System.out.println();
        bestn = cn;
        count++;
        return;
    } else {
        boolean ok = true;
        for (int j = 1; j < i; j++) {//检查顶点i是否与当前团全部连接
            if (x[j] == 1 && a[i][j] == 0) {
                ok = false;
                break;
            }
        }
        if (ok) {//从顶点i到已选入的顶点集中每一个顶点都有边相连
            //进入左子树
            x[i] = 1;
            cn++;
            backtrack(i + 1);
            x[i] = 0;
            cn--;
        }
        if (cn + n - i >= bestn) {//当前顶点数加上未遍历的课选择顶点>=当前最优顶点数目时才进入右子树;如果不需要找到所有的解，则不需要等于
            //进入右子树
            x[i] = 0;
            backtrack(i + 1);
        }
    }
}

分支界限法

分支限界法基本思想：

分支限界法类似于回溯法，也是一种在解空间树上搜索解的算法。但在一般情况下，二者的求解目标不同。回溯法求解目标是找出解空间树中满足约束条件的所有解，分支限界法的求解目标是找出满足约束条件的一个解。

1. 从解空间的搜索方式看，回溯法使用DFS，分支限界法使用BFS。
2. 从存储结点的数据结构上看，回溯法使用栈，分支限界法使用队列或优先队列。
3. 从结点存储特性上看，对于回溯法，活结点的所有子结点被遍历后才能出栈，对于分支限界法，每个结点只有一次成为活结点的机会。
4. 从应用场景上看，回溯法通常用于找出满足条件的所有解，分支限界法通常用于找出满足条件的一个解或者特定意义的最优解。

常见的两种分支界限法：

队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

算法实例

转载问题

问题描述：有一批共n个集装箱要装上2艘载重量分别为C_1和C_2的轮船，其中集装箱i的重量为w_i，且∑?w_i ≤C_1+C_2。问是否有一个合理的装载方案能将这n个集装箱装上这两艘轮船。该问题形式化描述为：

设n=5, C_1=120, C_2=80, w={60,40,10,30,50}。采用队列式分支限界算法解决该问题。

private void EnQueue(int i, Node parent, int weight, Boolean leftChild) {
    if (i == n) {   //达到叶子结点
        if (weight == bestW) {  //重量和==bestW
            bestE = parent; //  叶子结点的父节点
            bestx[n] = (bestE.isLeftChild) ? 1 : 0;//更新最优决策数组的最后一项
        }
    } else {
        Node b = new Node(parent, weight, leftChild);   // 创建新的结点
        queue.add(b);   //添加结点到队列中
    }
}
private void maxLoding() {
    int i = 1;    //当前层数
    Node A = new Node(null, 0, true);   //创建根结点A
    Node e = A;   //e记录即将放入队列的结点
    bestE = A;
    queue.add(null);
    int residue = 0;  //剩余集装箱重量
    for (int j = 2; j <= n; j++) {
        residue += w[j];
    }
    int ew = 0;   //当前拓展结点的重量
    while (true) {
        wt = ew + w[i]; //w[i]为将扩展结点所相应的载重量
        if (wt <= c) {  //检查左子结点 可行则装入队列
            if (wt > bestW) {
                bestW = wt;   //更新最优重量
            }
            EnQueue(i, e, wt, true);   //以左子节点身份进入
        }
        if (ew + residue >= bestW) {  // 检测右结点
            EnQueue(i, e, ew, false);
        }
        e = queue.poll();   //取队列的第一个结点
        if (e == null) {    //e=null表示同层结点尾部
            if (queue.isEmpty()) {
                break;
            }
            queue.add(null);
            e = queue.remove(); //更新当前结点
            i++;
            residue -= w[i];
        }
        ew = e.weight;  //更新扩展结点所相应的载重量
    }
    //构造当前最优解
    for (int j = n - 1; j > 0; j--) {
        bestx[j] = (bestE.isLeftChild) ? 1 : 0;
        bestE = bestE.parent;
    }
}