算法分析与设计：实验1-3实验报告

所有的三次实验的源码由博主使用 Java/Kotlin 写成，已经开源：
项目首页： https://dev.azure.com/Pure-Asahi/2020_Spring_In_Class_Job
仓库地址： https://dev.azure.com/Pure-Asahi/_git/2020_Spring_In_Class_Job
代码正确性不做绝对保证，使用需谨慎；有问题欢迎指出。

Front-matter

去网上找成品代码太难了，写错的还有一大堆。最后还是得自己写……

对于每一个实验，只需要执行项目下的Main.main(String[] args)就可以全自动的解出题目所要求的数据。因为项目使用IDEA写的，使用了一些Jetbrains自己的特性。所以请使用IDEA打开项目。

因为有很多的基础算法，它们的原理这里就不再赘述了，要是不知道的自己去看书。

实验一：排序算法

实验要求如下：

实验一：排序算法
一、实验目的
掌握算法科学解决问题的基本模式
了解确定性算法和随机性算法区别
分析同一问题不同解决算法之间的效率差
二、实验条件
硬件：计算机
软件：计算机程序语言开发平台，如 C、C++、Java、Matlab。
学生：至少掌握一门计算机程序设计语言，如 C、C++、Java、Matlab
三、实验内容及要求
利用计算机程序设计语言，实现教材第 2 章介绍的“插入排序算法”，自主拟定一组输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 2 章介绍的“合并排序算法”，自主拟定长度分别为偶数和奇数的输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 7 章介绍的“快速排序算法”，自主拟定一组输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 7 章介绍的“随机快速排序算法”，采用实验内容 3的输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 8 章介绍的“计数排序算法”，自主拟定一组适合“计数排序”问题特征的输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 8 章介绍的“基数排序算法”，自主拟定一组适合“基数排序”问题特征的输入数据，输出相应的算法结果。
利用计算机程序设计语言，实现教材第 8 章介绍的“桶排序算法”，自主拟定一组适合“桶排序”问题特征的输入数据，输出相应的算法结果。
分析上述 7 种排序算法的效率，并用直观的形式表达出效率随输入规模的变化趋势
四、思考题
算法科学解决问题的一般模式是什么？
确定性算法和随即性算法的差异在那里？随机化对于算法效率的影响如何？
如何理解算法效率分析的渐近特征和相对性？

实现算法

算法的原理参考《算法导论》，使用Java实现了整数排序机IntegerSorter类，包含任务要求的所有排序算法。

源代码可以看仓库，代码的具体内容这里不再赘述。

测试函数使用Java虚拟机提供的计时器计时，计算整个函数运行的时间消耗并输出到控制台上。根据用户的输入多次连续的测试某种算法的时间消耗，并且验证正确性后输出到控制台。

查看核心代码

实验结果

算法正确性

控制台的输出如下：

可见算法的正确性是可以保障的。

算法效率

执行源代码的Main.main方法，输入不同的数据大小，可以得到这样的测试结果（控制台文件）：

小于1000的数据集规模因为时间过短，统计时间为0ms；大于1e7的数据集规模因为Java内部原因，运行常数过大导致虚拟机中断，未能输出结果。合并排序速度较慢的一大原因是因为Java内部数据拷贝以及内存分配释放速度较慢导致。

因为算法实现以及Java的一些原因，所有的非原位排序算法都将面临一个很大的常数。这是由于内存分配和释放带来的额外开销。也许可以在更加优雅的实现方式中使用一些方法来降低这方面的开销。

算法分析

以下是包含本次实验的七个排序算法在内的算法分析表：

排序方法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n)$	$O(n+k)$	稳定
基数排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+k)$	稳定

上述表格只提供了对算法的简单分析。诸如基数排序等部分排序算法的复杂度还受到了一些其他可控因素的影响，这里不再讨论。

这些算法的运行时间/空间将会随着输入规模的变化大致按照上表所示的趋势变化。但是因为并不能收集到数量级跨较大范围的数据变化趋势，所以无法绘图。

思考题

算法科学解决问题的一般模式

简单地说，算法就是解决问题的方法和步骤。这些步骤可以简要的概括为：

分析问题：对问题进行思考分析
设计算法编写程序：设计出合理的算法并将其改写为计算机程序
运行程序并验证结果：运行所得的程序验证是否能够解决问题，如果不能，重新设计算法或改写程序
解决问题：使用所得程序解决问题

确定性算法和随机性算法的差异

随机化算法是一种在算法中使用了随机函数，且随机函数的返回值直接或间接的影响了算法的执行流程或执行结果的算法。而确定性算法是与随机化算法相对的：算法本身执行的过程是相对确定的。具体地说，随机化算法，即指的是在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件的一类算法；而相对应地，确定性算法不具有此特征。通常而言，对于确定的输入，确定性算法能输出稳定一致的结果，而随机化算法不一定能。

随机化对于算法效率的影响

在许多情况下，当算法在执行过程中面临一个选择时，随机化选择常比最优选择省事。
因此，大多数情况下，随机化算法都可以在很大程度上降低算法的复杂度。
例如对于快排而言，快排的排序速度取决于数组的无序程度，数组越乱，快排的效率越高；所以，对快排算法加入随机化十分重要。
一个简单的应用，例如：数据读入时将数据排放在随机位置，这样就可以将快排的的时间复杂度维持在较好状态。

如何理解算法效率分析的渐近特征和相对性

渐进性：在算法效率度量中，常常采用渐进表达式；因为常数间的差异较小，而渐进表达式的核心就是忽略常数。
相对性：算法的效率是相对的，我们选取的参照不同，数值的意义就不同；我们需要为自己的算法效率评估确定一个基准，然后相对于这个基准我们来做算法效率评估。
例如希望测试快排的效率，不能直接对大量数据进行快排计算时间；而应选取参照，例如与冒泡，桶排序等方案进行比较，从而分析出快排的效率的优越性

实验二：Strassen’s 矩阵乘法和最近点对算法

实验要求如下：

实验二：Strassen’s 矩阵乘法和最近点对算法
一、实验目的
理解“分治法”算法设计思想及其实现步骤
掌握分治算法效率递归分析方法
掌握主方式求解递归式方法
二、实验条件
硬件：计算机
软件：计算机程序语言开发平台，如 C、C++、Java、Matlab。
学生：至少掌握一门计算机程序设计语言，如 C、C++、Java、Matlab
三、实验内容及要求
利用计算机程序设计语言，实现教材第 28.2 章介绍的“Strassen’s 矩阵乘法算法”，自主生成两个 8×8 的矩阵，检验算法的正确性并输出算法结果。
比较 Strassen’s 矩阵乘法算法和数学定义的矩阵乘法算法效率之间的区别，并用直观的表达方式把两种不同矩阵乘法的效率随矩阵维数的变化趋势。
利用计算机程序设计语言，实现教材第 33.4 章介绍的“最近点对算法”，在拟定的二维空间点集上检验算法的正确性并输出算法结果。
四、思考题
分治法算法设计思想的三个基本步骤是什么？如何证明分治算法的正确性？
利用主方式求解 Strassen’s 矩阵乘法和最近点对算法效率的递归分析结果。
解释怎样修改 Strassen’s 矩阵乘法算法，使得它也可以用于大小不必为 2 的幂的矩阵

任务一： Stressen 方法

关于 Stressen 矩阵乘法方法的描述，详见算法导论：

就这样，先把矩阵分块，然后根据书上的做法敲一遍。只要不敲错就不会有什么问题。验证请看实验结果。

下面是我实现的Stressen方法的核心部分。具体内容请参见源代码中的Matrix类下的一些方法的实现。

private static int[][] stressen(int[][] ma, int[][] mb) {
    final int n = ma.length, half = n / 2;
    int[][] ret = new int[n][n];
    if(n == 1) {
        ret[0][0] = ma[0][0] * mb[0][0];
    }
    else {
        int a11[][] = new int[half][half];
        int a12[][] = new int[half][half];
        int a21[][] = new int[half][half];
        int a22[][] = new int[half][half];
        int b11[][] = new int[half][half];
        int b12[][] = new int[half][half];
        int b21[][] = new int[half][half];
        int b22[][] = new int[half][half];
        for(int i = 0; i < half; ++i) {
            for(int j = 0; j < half; ++j) {
                a11[i][j] = ma[i][j];
                a12[i][j] = ma[i][j+half];
                a21[i][j] = ma[i+half][j];
                a22[i][j] = ma[i+half][j+half];
                b11[i][j] = mb[i][j];
                b12[i][j] = mb[i][j+half];
                b21[i][j] = mb[i+half][j];
                b22[i][j] = mb[i+half][j+half];
            }
        }

        int[][] s1 = sub(b12,b22);
        int[][] s2 = add(a11,a12);
        int[][] s3 = add(a21,a22);
        int[][] s4 = sub(b21,b11);
        int[][] s5 = add(a11,a22);
        int[][] s6 = add(b11,b22);
        int[][] s7 = sub(a12,a22);
        int[][] s8 = add(b21,b22);
        int[][] s9 = sub(a11,a21);
        int[][] s10 = add(b11,b12);

        int[][] p1 = stressen(a11,s1);
        int[][] p2 = stressen(s2,b22);
        int[][] p3 = stressen(s3,b11);
        int[][] p4 = stressen(a22,s4);
        int[][] p5 = stressen(s5,s6);
        int[][] p6 = stressen(s7,s8);
        int[][] p7 = stressen(s9,s10);

        int c11[][] = sub(add(p5,p4),sub(p2,p6));
        int c12[][] = add(p1,p2);
        int c21[][] = add(p3,p4);
        int c22[][] = sub(add(p5,p1),add(p3,p7));

        for(int i = 0; i < half; ++i) {
            for (int j = 0; j < half; ++j) {
                ret[i][j] = c11[i][j];
                ret[i][j+half] = c12[i][j];
                ret[i+half][j] = c21[i][j];
                ret[i+half][j+half] = c22[i][j];
            }
        }
    }
    return ret;
}

任务二：最近点对问题

问题简述

在一个二维空间内有一些点，求出所有点对中距离最小的点对以及距离值。这里的距离指的是欧几里得距离即直线距离。

问题分析

这个问题可以分解成一些互不相干的子问题，并且小规模求解更加简单，同时还具有最优的子结构。满足使用分治思想求解的问题的特点，故可以使用分治思想求解。参考《算法导论》上的相关内容，分治的步骤可以是下面这样：

分治

对所有的点按照x坐标（或者y）从小到大排序。（排序方法时间复杂度 $O(nlogn)$ ）
根据下标进行分割，使得点集较平均地分为两个集合。

求解

递归的寻找两个集合中的最近点对。
取两个集合最近点对中的最小值 $d=min(d_{L},d_{R})$ 。

合并

最近距离不一定存在于两个集合中，可能在分解的两侧。
若一个点在集合A，一个点在集合B，那么这两点间距离小于d。

前面的部分还都比较好理解，关键就在于合并步骤。根据上面的分析：当最近点对在分割线两侧的时候，它们的距离一定会小于d；因此，我们可以在分割线m的周围取以下区间 $[m-d,m+d]$ ；显然，若最小点对跨过了分界线，那么一定会出现在这个条状区域内。那么只需要遍历一端在 $[m-d,m]$ 另一端在 $[m,m+d]$ 内的所有点对并计算距离就可以了。

但是这里有一个显而易见的最坏情况：若两侧所有的点都出现在这一个带状区域之内，那么我们做的分治只是白白地增加了整个算法的常数而已。所以要在这个的基础之上进行优化。这里，算法导论上还给出了一个方法——把带状区域中的点按照另一个坐标排序；则在该数组中，对于任何一个点，最多只需要检查紧随其后的7个点，就可以确保找到存在的最小点对或确保它不存在。我们着重讨论这种做法的正确性所在：

首先先给出一个结论：若（p,q）是Q的最近点对，且p在带域左半部分，则q点必在下图所示的δ∗2δ长方形上；而在该长方形上，最多只能有边点集的6个点；每个点对之间的距离不小于δ。

可以使用反证法来证明它的正确性：我们现在将上面的这个δ∗2δ的长方形划分成6个2δ/3∗δ/2的小长方形。如果存在第七个符合条件的点，那么一定有一个长方形拥有了两个点——然而这个长方形内最长的距离，也就是对角线，也不过长5δ/6；然后我们将这个打长方形对折到p同侧：根据同样的考虑，同侧最多也只能再有额外的两个点的距离大于δ；在考虑扫描的顺序，即可说明仅扫描随后7个点的正确性。

经过这种简化，扫描带状区域的复杂度被压缩到了常数级别，大大提升了算法的效率。

此外，还有如下的更进一步的优化：

1998年，由周玉林、熊鹏荣、朱洪教授提出了平面最近点对的一个改进算法，针对Preparata-Shamos算法提出的6个点，又证明其实只需要4个点就可以确定最近点对距离，该证明提出2个定理，利用更加准确的半径画圈，证明了只要对左半域上的每个点p，检验右半域y坐标与p最近的至多4个点即可（上下个两个）。具体明可以参考《求平面点集最近点对的一个改进算法》。
根据以上的优化，可以在合并时，通过检测与左半域点p的y坐标相邻的2个或者3个，即使用4点或者6点来检测，一般为了省事，只求与p点y坐标上界或者下界右半域连续的6个、4个点即可。
版权声明：本文为CSDN博主「码到sucess」的原创文章，遵循 CC 4.0 BY-SA 版权协议。
原文链接：https://blog.csdn.net/sinat_35678407/article/details/82874216

经过上述的优化之后，我们就可以确实地使用分治策略来优化这个问题了。上面说到的按照另一坐标轴排序的部分，还可以使用预排序的方法，再额外优化掉每次排序的一个 $log n$ 的复杂度。排序的预处理消耗 $O(nlogn)$ ，处理阶段消耗 $\Theta (n)$ ；最终的时间复杂度的递推公式如下：

$$ T(n) = \begin{cases} 1 ,& n \leq 3 \\ 2T(\frac{n}{2}) + O(n) ,& n > 3 \end{cases} $$

也就是说，整体的复杂度是 O(nlog n)。

代码实现

分治分为三个模块：分治模块，合并模块和暴力模块；当区间较小时直接由暴力模块求解，否则则先递归的分治，之后再使用合并模块合并两区间的答案求解。

private Point[] mergeDivisor(double m, double d, Point[] set) {
    ArrayList<Point> list = new ArrayList<>();
    final double l = m-d, r = m+d;
    for (Point pii : set)
        if (pii.x >= l && pii.x <= r)
            list.add(pii);
    Point[] ret = new Point[2];

    final int length = list.size();
    if (length <= 1) {
        ret[0] = new Point(-inf);
        ret[1] = new Point(inf);
        return ret;
    }
    ret[0] = list.get(0);ret[1] = list.get(1);
    double now = ret[0].distance(ret[1]), tmp;

    for (int i = 0; i < length; ++ i) {
        final int lim = Math.min(length, i + 7);
        for (int j = i+1; j < lim; ++ j) {
            tmp = list.get(i).distance(list.get(j));
            if (tmp < now) {
                now = tmp;
                ret[0] = list.get(i);
                ret[1] = list.get(j);
            }
        }
    }
    return ret;
}

private Point[] solveDivisor(int l, int r, Point[] arr) {
    final int m = arr.length / 2, ml = m + l;
    if (arr.length == 2) return new Point[]{arr[0],arr[1]};
    else if (arr.length == 3) return bruteDivisor(arr);
    double mid = (arr.length % 2 == 1) ? this.set[l+m].x : (double)(this.set[l+m].x + this.set[l+m-1].x) / 2.0;
    int lcredit = 0, rcredit = 0, cur = l + m;
    while (cur < r && this.set[cur++].x == mid) ++rcredit; cur = l + m - 1;
    while (cur >= l && this.set[cur--].x == mid) ++lcredit;

    int ca = 0, cb = 0, mm = arr.length - m;
    Point[] left = new Point[m], right = new Point[mm];
    for (int i = 0; i < arr.length; ++ i) {
        if (arr[i].x < mid) left[ca++] = arr[i];
        else if (arr[i].x > mid) right[cb++] = arr[i];
        else {
            if (rcredit > 0) {
                right[cb++] = arr[i];
                -- rcredit;
            }
            else if (lcredit > 0) {
                left[ca++] = arr[i];
                -- lcredit;
            }
        }
    }

    Point[] ans1 = solveDivisor(l,ml,left), ans2 = solveDivisor(ml,r,right);
    final double d1 = ans1[0].distance(ans1[1]);
    final double d2 = ans2[0].distance(ans2[1]);
    Point[] ans3 = mergeDivisor(mid,Math.min(d1,d2),arr);
    final double d3 = ans3[0].distance(ans3[1]);
    if (d3 < Math.min(d1,d2)) return ans3;
    else return d1 > d2 ? ans2 : ans1;
}

private Point[] bruteDivisor(Point[] set) {
    Point[] ret = new Point[2];
    double now = set[0].distance(set[1]), tmp;
    ret[0] = set[0]; ret[1] = set[1];
    for (int i = 0; i < set.length; ++ i) {
        for (int j = i+1; j < set.length; ++ j) {
            tmp = set[i].distance(set[j]);
            if (tmp < now) {
                now = tmp;
                ret[0] = set[i]; ret[1] = set[j];
            }
        }
    }
    return ret;
}

实现的不够优雅…… 虽然说预排序确实减少了每次排序的一个 log n 的复杂度，但是每次分治都要复制数组还是不够优雅；若是像Java这种分配空间开销极大，并且面临不定时的垃圾回收的语言来说，想必常数是极大的吧。

实验结果

Stressen 正确性验证

随机生成 8x8 矩阵，分别使用定义和Stressen方法计算矩阵乘法；将答案对比并输出结果到控制台，运行结果如下：

可以证明实现是正确的。

效率对比

随机生成矩阵，使用两种方法进行多次重复计算；每次改变方阵规模，并计时输出到控制台；运行结果如下：

因为Stressen方法实现过程中有大量的矩阵新建/销毁的操作，反复的分配/释放内存，导致了常数大幅提高；在实验中的表现甚至不如一般的矩阵乘法。

最小点对测试

进行随机测试，运行结果如下：

关于自动测试程序的正确性，可以参照源代码中的Main.main方法的调用。下面的运行结果是输出暴力和分治求解结果的一些测试结果：

这些测试结果足以证明了算法实现的正确性。

思考题

分治算法的步骤和正确性

分治算法包括三个基本步骤：

Step1：Devide——将要解决的问题划分成若干规模较小的同类问题

Step2：Conquer——当子问题划分得足够小时，用较简单的方法解决 (一般都是递归)

Step3：Combine——将子问题的解逐层合并构成原问题的解

正确性可用数学归纳法证明。

使用主方法分析 Stressen 方法和点对分治

Strassen’s 矩阵乘法的递归式为 $T(n) = 7T(\frac n 2) + Θ(n^2)$ ，可以由主定理的公式

得到： $T(n) = n^{lg7}$ 。

修改 Stressen 方法增广使用范围

首先，先梳理一下 Stressen 方法要求方阵的规模是二次幂的原因： Stressen 方法将子矩阵的乘法变成了加法，而加法对于两个“加数”矩阵的规模要求十分严格——即满足相同规模；因此，为了保证每次分治二分的矩阵都可以进行矩阵加法，才要求矩阵的规模必须是2的幂。基于这一点，我们有两种思路：

将矩阵补成二次幂形式：因为矩阵乘法性质规定了，以补0的方式扩大现有方阵，乘法的结果依然不变；也就是说可以先将矩阵扩大到二次幂形式，相乘之后再取出特定部分的值还原矩阵即可。但是这样做将面临可能的很大的空间开销，并不是很好的方案。
规定一个小方阵规模：小方阵直接使用定义求解；令这个最小规模为m，那么我们要求的方阵规模就从二次幂转化为了 $n*2^a$ ，其中 n < m。这样扩充矩阵造成的空间浪费就得以控制，且较小范围内，由于常数原因并不会损失太多的性能。

因为基本的思路都是扩充矩阵，还有一种可行的方案是：每次进行分治的时候检测方阵的规模，若方阵的规模为奇数且不为1时（或者大于最小方阵规模时）将它扩充为+1的偶数。这样下次再遇到扩充的数值就缩小了一半，也不会造成过多的空间浪费。

实验三：作业排程和最长共同子序列算法

实验要求如下：

实验三：作业排程和最长共同子序列算法
一、实验目的
理解动态规划算法设计思想，利用动态规划算法设计方法解决作业排程和最长共同子序列问题。
二、实验条件
计算机及程序语言开发平台（如 C、C++、Java、Matlab 等）。
三、实验内容及要求
描述并实现动态规划的作业排程算法，并显示下图的排程结果。

描述并实现最长共同子序列动态规划算法，并显示 S1 = ACCGGTCGAGATGCAG，S2 = GTCGTTCGGAATGCAT 的最长共同子序列。
四、思考题
动态规划算法范式是什么？
利用动态规划算法设计方法解决矩阵链相乘问题？

任务一：作业排程问题

问题简述

有一个车间，有n条生产线，每条生产线有m个工序组成。每个工序可以组装一个零件，且第i条生产线的第j个工序花费的时间是a(i,j)；如果在一条生产线上加工产品，则产品在不同的工序之间流转的消费是0；否则，如果要将在第i条生产线的第j个工序处理之后的产品移动到另一条生产线的第j+1个工序，则需要额外的成本t(i,j)；此外，对于每条生产线，将零件送上生产线需要e(i)，将产品撤下生产线需要x(i)。

装载一个产品恰好需要经历一整条生产线上的所有工序，请问如果要生产一个产品，所需要的最小花费是？

问题分析

在每一个工序上花费的时间是恒定的。如果决定某工序在确定的生产线上生产，那么它的耗时仅取决于处理之前所有工序的最短时间。这说明了这个模型具有可转移性；并且这个模型具有无后效性：因为处理某工序之前，无论之前的工序在哪条生产线上完成都不会影响到该工序的处理。所以这是一个DP模型，可以使用DP解。

我们设 $dp_{i,j}$ 的含义是：产品到达第i条生产线上的第j个工序时，可能的最短耗时。那么根据上面的分析易得推导关系：

$$ dp_{i,j} = min \begin{cases} dp_{k,j-1}+a_{k,j-1} ,& k = i \\ dp_{k,j-1}+a_{k,j-1}+t_{k,j-1} ,& k \neq i \end{cases} $$

上式中有$k \in [1,n] $；特别地，在最后一道工序和第一道工序的时候，因为有上下费用，所以推导式略有不同：

$$ \begin{cases} dp_{i,1} = e_i \\ ans = min(dp_{i,m}) ,& i \in [1,n] \end{cases} $$

这样ans就是最小的时间费用了。如果要求出具体的转移方案也很简单：在转移的同时开一个数组记录转移的前缀。找到答案后再倒退回去就可以了。

核心代码

下面的这些代码可以在文首仓库的DP_Algorithm\src\com\shiroha\curriculum\algorithm\dp目录下找到。

不包含追踪，仅求出最少花费的版本：

public static int solve(Problem p) {
    final int m = p.getLines(), n = p.getStations();
    int dp[][] = new int[m][n+1];
    for (int i = 0; i < m; ++ i) {
        dp[i][0] = p.getEntry(i);
    }
    for (int j = 1; j < n; ++ j) {
        for (int i = 0; i < m; ++ i) {
            dp[i][j] = dp[i][j-1] + p.getTime(i,j-1);
            for (int k = 0; k < m; ++ k) {
                if (k == i) continue;
                dp[i][j] = Math.min(dp[i][j], dp[k][j-1] + p.getTransfer(k,j-1) + p.getTime(k, j - 1));
            }
        }
    }
    int ans = 0x7fffffff;
    for (int i = 0; i < m; ++ i) {
        dp[i][n] = dp[i][n-1] + p.getExit(i) + p.getTime(i,n-1);
        ans = Math.min(ans, dp[i][n]);
    }
    return ans;
}

包含回溯的版本：

public static String[] backtraceSolve(Problem p) {
    final int m = p.getLines(), n = p.getStations();
    String[] ret = new String[2];
    int dp[][] = new int[m][n+1], tmp, cur;
    int trace[][] = new int[m][n], f[] = new int[n];
    for (int i = 0; i < m; ++ i) {
        dp[i][0] = p.getEntry(i);
    }
    for (int j = 1; j < n; ++ j) {
        for (int i = 0; i < m; ++ i) {
            dp[i][j] = dp[i][j-1] + p.getTime(i,j-1);
            cur = i;
            for (int k = 0; k < m; ++ k) {
                if (k == i) continue;
                tmp = dp[k][j-1] + p.getTransfer(k,j-1) + p.getTime(k, j - 1);
                if (tmp < dp[i][j]) {
                    dp[i][j] = tmp;
                    cur = k;
                }
            }
            trace[i][j] = cur;
        }
    }
    int ans = 0x7fffffff, pos = -1;
    for (int i = 0; i < m; ++ i) {
        dp[i][n] = dp[i][n-1] + p.getExit(i) + p.getTime(i,n-1);
        if (dp[i][n] < ans) {
            ans = dp[i][n];
            pos = i;
        }
    }
    for(int i = n-1; i >= 0; -- i) {
        f[i] = pos;
        pos = trace[pos][i];
    }

    ret[0] = Integer.toString(ans);
    ret[1] = backtraceToString(f);
    return ret;
}

详情请参考全部源代码。

任务二：LCS问题

问题简述

子序列的定义：对于由序列 $A_{1..n}$ 中的元素构成的子序列 $A_i..A_j$ ，若对于任意 i,j 都有 i < j，那么该序列就是原序列的子序列。

现给定两个字符串，求出它们的最长子序列。

问题分析

同样是简单的递推关系：若对于两个序列 $A$ , $B$ ：设序列 $A_i$ 的意义是从串A开始到第i个字符阶段的字符串， $a_i$ 是A串位于第i位的字符；那么，设 $dp_{i,j}$ 的含义是 $lcs(A_i,B_j)$ ，易得推导关系：

$$ dp_{i,j} = \begin{cases} dp_{i-1,j-1}+1 ,& a_i = b_j \\ max(dp_{i-1,j},dp_{i,j-1}) ,& a_i \neq b_j \end{cases} $$

同理，若要求出其中一种最长子序列，只需要记录前缀信息，求出答案后回溯即可。

核心代码

无回溯版本：

public static int basicSolve(String s1, String s2) {
    int l1 = s1.length(), l2 = s2.length();
    int[][] dp = new int[l1+1][l2+1];

    Arrays.fill(dp[0],0);
    for (int i = 0; i < l1; ++ i) {
        dp[i][0] = 0;
        for (int j = 0; j < l2; ++ j) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            else {
                dp[i+1][j+1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }

    return dp[l1][l2];
}

回溯版本：

public static String backtraceSolve(String s1, String s2) {
    int l1 = s1.length(), l2 = s2.length();
    int[][] dp = new int[l1+1][l2+1];
    byte[][] backtrace = new byte[l1+1][l2+1];

    Arrays.fill(dp[0],0);
    Arrays.fill(backtrace[0], (byte) -1);
    for (int i = 0; i < l1; ++ i) {
        dp[i][0] = 0;
        backtrace[i][0] = 1;
        for (int j = 0; j < l2; ++ j) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i+1][j+1] = dp[i][j] + 1;
                backtrace[i+1][j+1] = 0;
            }
            else {
                if (dp[i][j + 1] > dp[i + 1][j]) {
                    dp[i+1][j+1] = dp[i][j + 1];
                    backtrace[i+1][j+1] = 1;
                }
                else {
                    dp[i+1][j+1] = dp[i + 1][j];
                    backtrace[i+1][j+1] = -1;
                }
            }
        }
    }
    backtrace[0][0] = 0;
    StringBuilder sb = new StringBuilder();
    int x = l1, y = l2;
    while(x != 0 && y != 0) {
        switch (backtrace[x][y]) {
            case 0:
                --x; --y;
                sb.append(s1.charAt(x));
                break;
            case 1: --x; break;
            case -1: --y; break;
            default: break;
        }
    }
    return new StringBuffer(sb.toString()).reverse().toString();
}

详情请参考全部源代码。

实验结果

任务一

样例运行结果：

自行测试结果：

任务二

样例运行结果：

自行测试结果：

上述运行结果和预想结果一致，说明了算法实现的正确性。

思考题

动态规划算法范式

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

其基本思想是将待求解问题分解成若干个子问题：先求解子问题，然后从这些子问题的解得到原问题的解。这一点和分治法类似。

适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。有些子问题会被重复计算了很多次，对于这部分子问题可以记忆化。

简单的说，适合使用动态规划求解的问题往往具有可转移性和无后效性两大特点。

利用动态规划算法设计方法解决矩阵链相乘问题

不同矩阵相乘所需要的乘法次数是不同的。而当大量矩阵以链的形式相乘的时候，因为矩阵的乘法满足结合律，所以可通过适当选择乘法计算的优先级，可以找到某种计算顺序：它所需要进行的乘法计算次数是最少的。

首先：n*m的矩阵和m*k相乘所需要进行的乘法次数是nmk。设矩阵连乘的公式是 $A_iA_{i+1}..A_j,i \leq j$ ，简写为 $A[i:j]$ 。假设对于这个连乘的最优分割位置是k，那么就有 $A[i:j]=A[i:k]A[k+1:j]$ 。设 $A[i:j]$ 的计算量是 $p[i:j]$ ，那么显然：最优的 $p[i:j]$ 是最优的 $p[i:k]$ 和最优的 $p[k+1:j]$ 之和加上 $A[i:k]A[k+1:j]$ 的消耗。

这样就可以建立起状态转移方程了。记 $p[i:j]$ 为 $dp_{i,j}$ ，矩阵 $A_i$ 是 $a_i*b_i$ 矩阵；那么显然有：

$$ dp_{i,j} = dp_{i,k}+dp_{k+1,j}+a_ib_kb_j $$

显然，当 i=j 的时候， $dp_{i,j}$ 为0；在其他情况下，只需要遍历区间内的k，找到最小的dp进行转移就可以了。最后可以得到最少的乘法数；如果需要获得一种具体的方案，也可以通过回溯前缀的方法实现。

算法分析与设计：实验1-3实验报告

Front-matter

实验一：排序算法

实验一：排序算法

实现算法

实验结果

算法正确性

算法效率

算法分析

思考题

算法科学解决问题的一般模式

确定性算法和随机性算法的差异

随机化对于算法效率的影响

如何理解算法效率分析的渐近特征和相对性

实验二：Strassen’s 矩阵乘法和最近点对算法

实验二：Strassen’s 矩阵乘法和最近点对算法

任务一： Stressen 方法

任务二： 最近点对问题

问题简述

问题分析

代码实现

实验结果

Stressen 正确性验证

效率对比

最小点对测试

思考题

分治算法的步骤和正确性

使用主方法分析 Stressen 方法和点对分治

修改 Stressen 方法增广使用范围

实验三：作业排程和最长共同子序列算法

实验三：作业排程和最长共同子序列算法

任务一：作业排程问题

问题简述

问题分析

核心代码

任务二：LCS问题

问题简述

问题分析

核心代码

实验结果

任务一

任务二

思考题

动态规划算法范式

利用动态规划算法设计方法解决矩阵链相乘问题

参考资料

任务二：最近点对问题