RQTN

Analysis Of AlgorithmInterview Questions: Analysis of Algorithms (ungraded)1. 3-SUM in quadratic time.Design an algorithm for the 3-SUM problem that takes time proportional to $n^2$ in the worst case. You may assume that you can sort the $n$ integers in time proportional to $n^2$ or better. Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution. Solution 在课程中已经给出了两个求解 3-SUM 问题的算法：暴力方法 ThreeSum 和改进算法 ThreeSumFast。 其中暴力方法 ThreeSum 的时间复杂度为 ...

使用爬山法、模拟退火和遗传算法求解八皇后问题 实验使用 C++ 语言，并在 Windows 的 Visual Studio 2017 下能够正常运行。 参考书籍：《人工智能：一种现代的方法（第三版）》 1. 准备阶段1.1 Board 类 Board 类数据成员 bool board[8][8]：表示一个 8$\times$8 棋盘的具体情况。某位值为 true 时（即 1），表示该位上为皇后，否则为 false（即 0），表示该位上没有放置任何东西。 int state[8]：表示当前棋盘的状态。使用一个 8 位数串来表示八皇后问题的一个特定的状态。比如 83742516 就表示了这样的一个状态（注意加粗部分）： 第 1 列第 8 行位置有一个皇后 第 2 列第 3 行位置有一个皇后 第 3 列第 7 行位置有一个皇后 … 第 8 列第 6 行位置有一个皇后 int h_value_board[8][8]：一个辅助数据成员，表示一个 8$\times$8 棋盘上的所有下一步状态的评估值 —— 相互攻击的皇后的对数。其对应于书本上的下图： 方格中显示的数字表示将这一列中 ...

第 19 课 行列式公式和代数余子式 上一节我们讲述了行列式的 $10$ 个性质，根据这些性质，我们能够推导出行列式的一般求解过程。本节，我们将更加深入地讲解行列式公式和代数余子式，这两者都是求解行列式的方法。 行列式公式在上一节中，我们已经提到了二阶行列式公式 $\left|\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right|=a d-b c$，但我们并没有多做任何解释。 学习了关于行列式的这么多性质，现在我们有能力推导二阶行列式公式了： \displaylines{ \begin{vmatrix}a& b\\c& d\end{vmatrix}\stackrel{3.b}{=}\begin{vmatrix}a& 0\\c& d\end{vmatrix}+\begin{vmatrix}0& b\\c& d\end{vmatrix}\stackrel{3.b}{=}\begin{vmatrix}a& 0\\c& 0\end{vmatrix}+\begin{vmatrix}a& 0\\0& d\end{vmat ...

第 18 课 行列式及其性质从这堂课开始，我们就进入了这门课的第二部分。迄今为止，我们已经学习了很多关于长方矩阵的知识，现在，把注意力转向方阵，探讨两个大的话题：行列式和特征值，我们需要行列式的重要原因是求特征值。 行列式是跟每个方阵都有关的数，每个方阵都有与其相关的行列式，我们一般记为 $\det A$，或者写作 $|A|$。 行列式最早是应用在用来判断方程组是否有解，在矩阵被发明后，行列式就拥有了更多的性质和应用。行列式是一个神奇的数，一个数很难告诉你整个矩阵是什么样子的，但行列式把矩阵的尽可能多的信息就包含在其中了。就比如，矩阵可逆等价于行列式非零，行列式为零时矩阵是奇异的。从另外一个角度来理解，行列式从某种程度上代表了这个矩阵的特征，这是学习特征分解的前置概念。 三个行列式基础性质 首先我们介绍三个行列式基础性质，这三个性质定义了行列式。 性质 $1$ ：对于单位矩阵 $I$，有 $\det I=1$。 性质 $2$ ：交换行，行列式的值的符号会相反。 由上面的两个性质我们可以得到：之前学习的置换矩阵的行列式的值为 $1$ 或 $-1$。例如：$\left|\begin{ ...

第 17 课 正交矩阵和 Gram-Schmidt 正交化 上一课最后我们简单介绍了标准正交向量组的概念，这一课中，我们将深入介绍标准正交向量组的性质和优点，以及将一组向量化为标准正交向量组的方法：Gram-Schmidt 正交化。 标准正交向量与正交矩阵上一节我们介绍过标准正交向量，我们通过一个式子进行回顾。设 $q$ 是标准正交向量组中的任意向量，则 \displaylines{ q_{i}^{T} q_{j}\left\{\begin{array}{l}{0 \ldots . .(i \neq j)} \\ {1 \ldots . .(i=j)}\end{array}\right. }这很好地表现了标准正交向量组内各向量的性质：不同向量之间相互垂直（正交），向量长度都为 1（标准）。 标准正交向量组又被称为标准正交基，显然，相互垂直的各列一定是线性无关的。 为什么我们这么执着于标准正交向量呢？在后续我们就能看到标准正交向量能够极大的简化计算，许多数值线性代数都建立在标准正交向量的基础上，因为它们容易操控，它们从不上溢或下溢。 我们再介绍另外一个概念，标准正交矩阵。所谓标准正交矩 ...

第 16 课 投影矩阵和最小二乘法 本章将深入研究投影矩阵，同时对上一课最后引出的最小二乘法做进一步地讲解。最后引出标准正交向量组等概念。 投影矩阵上一章已经介绍过投影矩阵 $P=A(A^TA)^{-1}A^T$。我们知道，投影矩阵 $P$ 与向量 $b$ 相乘将会把 $b$ 投影到 $A$ 的列空间中。那么现在我们来考虑两个极端的例子，这两个极端的例子将会加深我们对投影矩阵的理解。 如果 $b$ 在矩阵 $A$ 的列空间里， 那么 $Pb=b$ \displaylines{ 证明：如果b在矩阵A的列空间里，那么必然有Ax=b\\ Pb=A(A^TA)^{-1}A^Tb=A(A^TA)^{-1}A^TAx=AIx=Ax=b } 如果 $b$ 垂直于矩阵 $A$ 的列空间，那么 $Pb=0$ \displaylines{ 证明：b垂直于A的列空间，根据正交补的概念\\ 可知b是左零空间中的向量\\ \therefore A^Tb=0\\ \therefore Pb=A(A^TA)^{-1}A^Tb=A(A^TA)^{-1}0=0 }通过上面两个极端的例子，我们可以看出来，向量 ...

第 15 课 子空间投影 这一章我们讲投影，从向量的投影入手，延伸到高维投影，并将投影使用矩阵形式来给出。上一章中我们介绍了正交的基本概念，这一章我们将会使用到这个概念，做投影也即向另一个向量上做垂线。此外上一章我们讨论了当 $Ax=b$ 无解时的最优解求解问题，但我们并没有解释这个最优解为何“最优”，本章将会给出相应的解释。 相对简单的二维空间的投影 如上图，$p$ 也即向量 $b$ 在向量 $a$ 上的投影，$p$ 在向量 $a$ 上，是 $a$ 的倍数，故令 $p=xa$。将 $b$ 与 $p$ 的差设为 $e$， $e$ 带有误差的意思，同时 $e$ 的模在某种程度上表示了 $b$ 到 $a$ 的最短距离（而这正是最优的体现：误差最小）。$e$ 与 $a$ 正交。 \displaylines{ 已知 a \bot e，而e=b-p，p=xa\\ \therefore a\bot(b-xa)\\ \therefore a^T(b-xa)=0\\ \therefore x=\frac{a^Tb}{a^Ta}（x是一个标量）\\ \therefore p=xa=ax=a\frac{ ...

第 14 课 正交向量与子空间本章我们研究的重点还是之前提到过的子空间，但是本章我们主要从正交的角度来探讨这些子空间具有的性质，主要内容见下图。 注意，上图指出了我们之前没有关注到的子空间的一些性质：对于一个矩阵，其零空间与行空间正交，其列空间与左零空间正交。 向量正交与空间正交在线性代数中，正交就是垂直。无论我们讨论的是向量正交还是空间正交，都可以理解为垂直。 我们先研究最简单的向量正交： 如上图，其中 $x$ 与 $y$ 向量之间相互垂直（正交）。根据垂直关系，可得 $x^Ty=0$，这是初高中的内容：如果两个向量相互垂直（正交），那么这两个向量的数量积（内积）为 $0$。 这个结论很漂亮，现在我们将证明这个结论。 \displaylines{ 根据勾股定律有： |x|^2+|y|^2=|x+y|^2 \ \\ 用向量来表示上式有：x^Tx+y^Ty=(x+y)^T(x+y)=(x^T+y^T)(x+y)\\ 化简得：0=x^Ty+y^Tx\\ \because x^Ty=y^Tx，都表示两个一维向量的数量积，所以可进一步化简得：2x^Ty=0\\ \therefore x^T ...

第 13 课 复习一 本章是习题课，意在通过习题来对前十二课的内容进行回顾以作复习。 设 $u,v,w$ 是 $R^7$ 空间内的非零向量，它们生成了一个属于 $R^7$ 的向量子空间，则此空间的维数是多少？ 由 $3$ 个向量张成的向量空间，显然维数只可能是 $0,1,2,3$ 中的其中一个。题中已经写明 $u,v,w$ 这三个向量都是非零向量，所以维数会是 $1,2,3$ 中的其中一个。 有一个 $5\times 3$ 的阶梯型矩阵 $U$，秩为 $3$，求该矩阵的零空间。 由题可知该矩阵列满秩，所以不存在自由变量，于是矩阵的零空间将只有零向量。 给定 $10\times 3$ 的矩阵 $B$，$B$ 中含有矩阵 $R$ 和 $2R$ ：$B=\begin{bmatrix}R\\2R\end{bmatrix}$ （$R$ 是 RREF 型矩阵）。 该矩阵的秩是多少，其 RREF 型矩阵是怎样的？ 这两个问题的求解都需要对 $B$ 进行消元，消元可得：$B=\begin{bmatrix}R\\2R\end{bmatrix}\rightarrow \begin{bmatrix ...

第 12 课 图和网络 本章着重于线性代数的应用。和前面的章节不同的是，本章中线性代数处理的矩阵都是有出处的，它们来自于实际问题，描述了问题的拓扑结构。应用数学中最重要的模型，离散数学称之为”图“。本章，我们将探索图和矩阵之间的联系（关联矩阵），从关联矩阵中推导出欧姆定律、基尔霍夫电流定律、欧拉公式，并探究这三者之间的关系。 为探究图和矩阵之间的联系，我们先给出一个有向图（如下），$4$ 个点（$n=4$），$5$ 条边（$m=5$)。 该有向图可以来自于一个电路系统，也可以来自于一个液压系统，甚至表示一个建筑结构，但在本课中我们将其视为一个电路网络。 我们可以使用矩阵来表示一个图，矩阵中包含图中的所有信息。通过构造一个矩阵可以解析相应的图的含义，这样的矩阵叫做关联矩阵。在关联矩阵中，每一列代表一个节点，每一行代表一条边（行中的正负代表方向）。易得上（电路网络）图对应的关联矩阵 $A$ 如下： 观察关联矩阵 $A$ 的第一行，第一行代表了电路网络图中边 $1$ 的情况，在图中，边 $1$ 以 点 $1$ 作为起点，以点 $2$ 作为终点，反映到矩阵上就是 $A_{(1,1)} ...