miniyuan

解线性方程组的直接法

题 2.1

增广矩阵为：

[021511032320]\left[\begin{array}{ccc|c} 0 & 2 & 1 & 5 \\ 1 & 1 & 0 & 3 \\ 2 & 3 & 2 & 0 \end{array}\right]

在第 1 列的主元在第 3 行，交换第 1 行和第 3 行：

[232011030215]\left[\begin{array}{ccc|c} 2 & 3 & 2 & 0 \\ 1 & 1 & 0 & 3 \\ 0 & 2 & 1 & 5 \end{array}\right]

消元得：

[23200−12−130215]\left[\begin{array}{ccc|c} 2 & 3 & 2 & 0 \\ 0 & -\frac{1}{2} & -1 & 3 \\ 0 & 2 & 1 & 5 \end{array}\right]

在第 2 列的主元在第 3 行，交换第 2 行和第 3 行：

[232002150−12−13]\left[\begin{array}{ccc|c} 2 & 3 & 2 & 0 \\ 0 & 2 & 1 & 5 \\ 0 & -\frac{1}{2} & -1 & 3 \end{array}\right]

消元得：

[2320021500−34174]\left[\begin{array}{ccc|c} 2 & 3 & 2 & 0 \\ 0 & 2 & 1 & 5 \\ 0 & 0 & -\frac{3}{4} & \frac{17}{4} \end{array}\right]

回代求解得：

x1=−73,x2=163,x3=−173x_1 = -\frac{7}{3},\quad x_2 = \frac{16}{3},\quad x_3 = -\frac{17}{3}

题 2.2

证明：

由对称正定阵的 Cholesky 分解知：

A=LTL\mathbf{A} = \mathbf{L}^\mathrm{T} \mathbf{L}

其中 L\mathbf{L} 为下三角矩阵，对角元为正。

从而有：

∥x∥A=xTLTLx=∥Lx∥2\|\mathbf{x}\|_{\mathbf{A}} = \sqrt{\mathbf{x}^\mathrm{T} \mathbf{L}^\mathrm{T} \mathbf{L} \mathbf{x}} = \|\mathbf{L} \mathbf{x}\|_2

于是根据向量 2-范数的性质知：

  1. 正定性：

    ∥x∥A≥0\|\mathbf{x}\|_{\mathbf{A}} \ge 0 显然。

    且：

    ∥x∥A=0⇔∥Lx∥2=0⇔Lx=0⇔x=0\|\mathbf{x}\|_{\mathbf{A}} = 0 \Leftrightarrow \|\mathbf{L} \mathbf{x}\|_2 = 0 \Leftrightarrow \mathbf{L} \mathbf{x} = 0 \Leftrightarrow \mathbf{x} = 0

  2. 齐次性：

    ∀α∈R\forall \alpha \in \mathbb{R}，有：

    ∥αx∥A=∥αLx∥2=∣α∣∥Lx∥2=∣α∣∥x∥A\|\alpha \mathbf{x}\|_{\mathbf{A}} = \|\alpha \mathbf{L} \mathbf{x}\|_2 = |\alpha| \|\mathbf{L} \mathbf{x}\|_2 = |\alpha|\|\mathbf{x}\|_{\mathbf{A}}

  3. 三角不等式：

    ∀x,y∈Rn\forall \mathbf{x}, \mathbf{y} \in \mathbb{R}^n，有：

    ∥x+y∥A=∥L(x+y)∥2≤∥Lx∥2+∥Ly∥2=∥x∥A+∥y∥A\|\mathbf{x} + \mathbf{y}\|_{\mathbf{A}} = \|\mathbf{L} (\mathbf{x} + \mathbf{y})\|_2 \le \|\mathbf{L} \mathbf{x}\|_2 + \|\mathbf{L} \mathbf{y}\|_2 = \|\mathbf{x} \|_{\mathbf{A}} + \|\mathbf{y}\|_{\mathbf{A}}

综上，原范数是一个向量范数。

题 2.3

记 B−1=A=[a1a2⋯an]\mathbf{B}^{-1} = \mathbf{A} = \begin{bmatrix} a^1 \\ a^2 \\ \cdots \\ a^n \end{bmatrix}， 其中 aia^i 为 A\mathbf{A} 的第 ii 行。

则利用矩阵乘法的按行展开得：

(BA)i=ai−∑k=i+1nak=ei.i=1,⋯ ,n(\mathbf{B} \mathbf{A})^i = a^i - \sum_{k = i+1}^{n} a^k = e^i. \qquad i = 1, \cdots, n

其中 ei=(0,⋯ ,1,⋯ ,0)e^i = \begin{pmatrix} 0, \cdots, 1, \cdots, 0\end{pmatrix} 为第 ii 位为 1 的单位行向量。

从下往上回代求解得：

an=(0,⋯ ,0,1)an−1=(0,⋯ ,0,1,1)ak=(0,⋯ ,0,1,1,2,4,⋯ ,2n−k−1),k≤n−2\begin{aligned} a^n &= \begin{pmatrix} 0, \cdots, 0, 1\end{pmatrix} \\ a^{n-1} &= \begin{pmatrix} 0, \cdots, 0, 1, 1\end{pmatrix} \\ a^{k} &= \begin{pmatrix} 0, \cdots, 0, 1, 1, 2, 4, \cdots, 2^{n-k-1} \end{pmatrix}, \quad k \le n-2 \end{aligned}

也即：

∥ai∥1=∑j=1n∣aij∣=2n−i∥bi∥1=∑j=1n∣bij∣=n−i+1\begin{aligned} \|a^i\|_1 &= \sum_{j = 1}^{n} \vert a_{ij} \vert = 2^{n - i} \\ \|b^i\|_1 &= \sum_{j = 1}^{n} \vert b_{ij} \vert = n - i + 1 \end{aligned}

从而有：

Cond(B)=∥A∥∞⋅∥B∥∞=max⁡i∥ai∥1⋅max⁡i∥bi∥1=n2n−1\text{Cond}(\mathbf{B}) = \|\mathbf{A}\|_{\infty} \cdot \|\mathbf{B}\|_{\infty} = \max_{i} \|a^i\|_1 \cdot \max_{i} \|b^i\|_1 = n 2^{n-1}

题 2.4

证明 1

  1. 证明 Hn=HnT\mathbf{H}_n = \mathbf{H}_n^{\mathrm{T}}

    归纳法。

    n=0n=0 时，H0=[1]\mathbf{H}_0 = [1] 显然对称。 假设 Hn−1=Hn−1T\mathbf{H}_{n-1} = \mathbf{H}_{n-1}^{\mathrm{T}} 成立，下证对 Hn\mathbf{H}_n 也成立。这是因为：

    HnT=[Hn−1THn−1THn−1T−Hn−1T]=[Hn−1Hn−1Hn−1−Hn−1]=Hn\mathbf{H}_n^{\mathrm{T}} = \begin{bmatrix} \mathbf{H}_{n-1}^{\mathrm{T}} & \mathbf{H}_{n-1}^{\mathrm{T}} \\ \mathbf{H}_{n-1}^{\mathrm{T}} & -\mathbf{H}_{n-1}^{\mathrm{T}} \end{bmatrix} = \begin{bmatrix} \mathbf{H}_{n-1} & \mathbf{H}_{n-1} \\ \mathbf{H}_{n-1} & -\mathbf{H}_{n-1} \end{bmatrix} = \mathbf{H}_n

    成立！

  2. 证明 HnHnT=2nI2n\mathbf{H}_n\mathbf{H}_n^{\mathrm{T}} = 2^n \mathbf{I}_{2^n}

    归纳法。

    n=0n=0 时，H0H0T=[1][1]=[1]=20⋅I1\mathbf{H}_0\mathbf{H}_0^{\mathrm{T}} = [1][1] = [1] = 2^0 \cdot \mathbf{I}_1 成立。

    假设 Hn−1Hn−1T=2n−1I2n−1\mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} = 2^{n-1}\mathbf{I}_{2^{n-1}} 成立，下证对 Hn\mathbf{H}_n 也成立。这是因为：

    HnHnT=[Hn−1Hn−1Hn−1−Hn−1][Hn−1THn−1THn−1T−Hn−1T]=[Hn−1Hn−1T+Hn−1Hn−1THn−1Hn−1T−Hn−1Hn−1THn−1Hn−1T−Hn−1Hn−1THn−1Hn−1T+Hn−1Hn−1T]=[2nI2n−1002nI2n−1]=2nI2n\begin{aligned} \mathbf{H}_n\mathbf{H}_n^{\mathrm{T}} &= \begin{bmatrix} \mathbf{H}_{n-1} & \mathbf{H}_{n-1} \\ \mathbf{H}_{n-1} & -\mathbf{H}_{n-1} \end{bmatrix} \begin{bmatrix} \mathbf{H}_{n-1}^{\mathrm{T}} & \mathbf{H}_{n-1}^{\mathrm{T}} \\ \mathbf{H}_{n-1}^{\mathrm{T}} & -\mathbf{H}_{n-1}^{\mathrm{T}} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} + \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} & \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} - \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} \\ \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} - \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} & \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} + \mathbf{H}_{n-1}\mathbf{H}_{n-1}^{\mathrm{T}} \end{bmatrix} \\ &= \begin{bmatrix} 2^n \mathbf{I}_{2^{n-1}} & \mathbf{0} \\ \mathbf{0} & 2^n \mathbf{I}_{2^{n-1}} \end{bmatrix} \\ &= 2^n \mathbf{I}_{2^n} \end{aligned}

    成立！

证明 2

由于 Hn\mathbf{H}_n 对称正定，故其 LDL^T 分解存在且唯一。下归纳证明其 LDL^T 分解满足题示形式。

n=0n=0 时，取 D0=[1]\mathbf{D}_0 = [1]，则 L0D0L0T=[1]=H0\mathbf{L}_0 \mathbf{D}_0 \mathbf{L}_0^\mathrm{T} = [1] = \mathbf{H}_0 满足题目形式。

假设对于分解 Hn−1=Ln−1Dn−1Ln−1T\mathbf{H}_{n-1} = \mathbf{L}_{n-1} \mathbf{D}_{n-1} \mathbf{L}_{n-1}^\mathrm{T} 满足题目形式， 下证对 Hn=[Hn−1Hn−1Hn−1−Hn−1]\mathbf{H}_n = \begin{bmatrix} \mathbf{H}_{n-1} & \mathbf{H}_{n-1} \\ \mathbf{H}_{n-1} & -\mathbf{H}_{n-1} \end{bmatrix} 也有同样的分解形式。也即验证以下关于对角阵 An−1,Bn−1\mathbf{A}_{n-1}, \mathbf{B}_{n-1} 的方程有解：

[Ln−10Ln−1Ln−1][An−100Bn−1][Ln−1TLn−1T0Ln−1T]=[Hn−1Hn−1Hn−1−Hn−1]\begin{bmatrix} \mathbf{L}_{n-1} & \mathbf{0} \\ \mathbf{L}_{n-1} & \mathbf{L}_{n-1} \end{bmatrix} \begin{bmatrix} \mathbf{A}_{n-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{B}_{n-1} \end{bmatrix} \begin{bmatrix} \mathbf{L}_{n-1}^{\mathrm{T}} & \mathbf{L}_{n-1}^{\mathrm{T}} \\ \mathbf{0} & \mathbf{L}_{n-1}^{\mathrm{T}} \end{bmatrix} = \begin{bmatrix} \mathbf{H}_{n-1} & \mathbf{H}_{n-1} \\ \mathbf{H}_{n-1} & -\mathbf{H}_{n-1} \end{bmatrix}

等价于以下方程有解：

[Ln−1An−1Ln−1TLn−1An−1Ln−1TLn−1An−1Ln−1TLn−1(An−1+Bn−1)Ln−1T]=[Hn−1Hn−1Hn−1−Hn−1]\begin{bmatrix} \mathbf{L}_{n-1}\mathbf{A}_{n-1}\mathbf{L}_{n-1}^{\mathrm{T}} & \mathbf{L}_{n-1}\mathbf{A}_{n-1}\mathbf{L}_{n-1}^{\mathrm{T}} \\ \mathbf{L}_{n-1}\mathbf{A}_{n-1}\mathbf{L}_{n-1}^{\mathrm{T}} & \mathbf{L}_{n-1}(\mathbf{A}_{n-1} + \mathbf{B}_{n-1})\mathbf{L}_{n-1}^{\mathrm{T}} \end{bmatrix} = \begin{bmatrix} \mathbf{H}_{n-1} & \mathbf{H}_{n-1} \\ \mathbf{H}_{n-1} & -\mathbf{H}_{n-1} \end{bmatrix}

也即：

{Ln−1An−1Ln−1T=Hn−1Ln−1(An−1+Bn−1)Ln−1T=−Hn−1\begin{cases} \mathbf{L}_{n-1}\mathbf{A}_{n-1}\mathbf{L}_{n-1}^{\mathrm{T}} = \mathbf{H}_{n-1} \\ \mathbf{L}_{n-1}(\mathbf{A}_{n-1} + \mathbf{B}_{n-1})\mathbf{L}_{n-1}^{\mathrm{T}} = -\mathbf{H}_{n-1} \end{cases}

利用归纳，构造对角阵：

{An−1=Dn−1Bn−1=−2Dn−1\begin{cases} \mathbf{A}_{n-1} = \mathbf{D}_{n-1} \\ \mathbf{B}_{n-1} = -2\mathbf{D}_{n-1} \end{cases}

满足上述方程，从而满足题目要求的分解对 Hn\mathbf{H}_n 存在。同时得到 Dn\mathbf{D}_n 的递推公式为：

Dn=[Dn−100−2Dn−1],D0=[1]\mathbf{D}_n = \begin{bmatrix} \mathbf{D}_{n-1} & \mathbf{0} \\ \mathbf{0} & -2\mathbf{D}_{n-1} \end{bmatrix}, \quad \mathbf{D}_0 = [1]

题 2.6

算法设计

本质上系数矩阵是上三角的，可以直接回代求解。但是直接回代求解的复杂度为 O(n3)\mathcal{O}(n^3)，我们需要想点办法改进一下。

先展开原方程，对第 ii 行可得：

∑j=in(∑k=ijSi,kTk,j)xj−λxi=bi\sum_{j=i}^n (\sum_{k=i}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j - \lambda \mathbf{x}_i = \mathbf{b}_i

也即：

(Si,iTi,i−λ)xi+∑j=i+1n(∑k=ijSi,kTk,j)xj=bi(\mathbf{S}_{i, i} \mathbf{T}_{i, i} - \lambda) \mathbf{x}_i + \sum_{j=i+1}^n (\sum_{k=i}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j = \mathbf{b}_i

从而原始的回代求解即为：

xi=bi−∑j=i+1n(∑k=ijSi,kTk,j)xjSi,iTi,i−λ,i=n,n−1,⋯ ,1\mathbf{x}_i = \frac{\mathbf{b}_i - \sum_{j=i+1}^n (\sum_{k=i}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j} {\mathbf{S}_{i, i} \mathbf{T}_{i, i} - \lambda}, \quad i = n, n-1, \cdots, 1

可以看到复杂度主要花在了计算双重求和 ∑j=i+1n(∑k=ijSi,kTk,j)xj\sum_{j=i+1}^n (\sum_{k=i}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j 上，考虑优化这一部分。

利用恒等式：

∑j=i+1n(∑k=ijSi,kTk,j)xj=∑j=i+1n(∑k=i+1jSi,kTk,j)xj+∑j=i+1nSi,iTi,jxj=∑k=i+1n∑j=knSi,k(Tk,jxj)+∑j=i+1nSi,i(Ti,jxj)=∑k=i+1nSi,kwk+Si,ivi\begin{aligned} \sum_{j=i+1}^n (\sum_{k=i}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j &= \sum_{j=i+1}^n (\sum_{k=i+1}^j \mathbf{S}_{i, k} \mathbf{T}_{k, j}) \mathbf{x}_j + \sum_{j=i+1}^n \mathbf{S}_{i, i} \mathbf{T}_{i, j} \mathbf{x}_j \\ &= \sum_{k=i+1}^n \sum_{j=k}^n \mathbf{S}_{i, k} (\mathbf{T}_{k, j} \mathbf{x}_j) + \sum_{j=i+1}^n \mathbf{S}_{i, i} (\mathbf{T}_{i, j} \mathbf{x}_j) \\ &= \sum_{k=i+1}^n \mathbf{S}_{i, k} \mathbf{w}_k + \mathbf{S}_{i, i} \mathbf{v}_i \end{aligned}

其中 wk=∑j=knTk,jxj\mathbf{w}_k = \sum_{j=k}^n \mathbf{T}_{k, j} \mathbf{x}_j，vk=∑j=k+1nTk,jxj\mathbf{v}_k = \sum_{j=k+1}^n \mathbf{T}_{k, j} \mathbf{x}_j。

于是我们得到改进的回代求解：

wi+1=vi+1+Ti+1,i+1xi+1vi=∑j=i+1nTi,jxjxi=bi−Si,ivi−∑j=i+1nSi,jwjSi,iTi,i−λ\begin{aligned} \mathbf{w}_{i+1} &= \mathbf{v}_{i+1} + \mathbf{T}_{i+1, i+1} \mathbf{x}_{i+1} \\ \mathbf{v}_i &= \sum_{j=i+1}^n \mathbf{T}_{i, j} \mathbf{x}_j \\ \mathbf{x}_i &= \frac{\mathbf{b}_i - \mathbf{S}_{i, i} \mathbf{v}_i - \sum_{j=i+1}^n \mathbf{S}_{i, j} \mathbf{w}_j} {\mathbf{S}_{i, i} \mathbf{T}_{i, i} - \lambda} \end{aligned}

其中 wk\mathbf{w}_k 与 vk\mathbf{v}_k 均只需求解一次，后续重复利用。在回代求解 xi\mathbf{x}_i 之前，已经计算好了 wk\mathbf{w}_k（k≥i+1k \ge i+1）和 vi\mathbf{v}_i。 并且由于 wk\mathbf{w}_k 和 vk\mathbf{v}_k 的相关关系，我们可以只使用一个 w\mathbf{w} 数组。

复杂度分析

核心代码如下：

// 求解
x(n - 1) = b(n - 1) / (S(n - 1, n - 1) * T(n - 1, n - 1) - lambda);
for (int i = n - 2; i >= 0; i--) {
    // 预处理 w(i + 1), v(i)
    w(i + 1) += T(i + 1, i + 1) * x(i + 1); // w(i + 1)
    for (int j = i + 1; j < n; j++) {
        w(i) += T(i, j) * x(j); // v(i)
    }

    // 求解 x(i)
    x(i) = b(i);
    for (int j = i; j < n; j++) {
        x(i) -= S(i, j) * w(j);
    }
    x(i) /= (S(i, i) * T(i, i) - lambda);
}

只考虑求解过程和浮点数运算，外层循环有 n−1n-1 次，每次内层循环有 O(2n−2i)\mathcal{O}(2n-2i) 次。 故时间复杂度：

T=∑i=0n−2O(2n−2i)=O(∑k=2n2k)=O(2n2)\mathcal{T} = \sum_{i=0}^{n-2} \mathcal{O}(2n-2i) = \mathcal{O}(\sum_{k=2}^n 2k) = \mathcal{O}(2n^2)

空间复杂度上需要 O(n)\mathcal{O}(n) 的额外空间。

题 2.7

问题 1

在不重复操作（模 2）意义下，解不一定存在，也不一定唯一，但是要么存在且唯一，要么可能不存在且可能不唯一。注意以下的计算都在域 F2\mathbb{F}_2 上进行。

考虑一个 m×nm \times n 的网格，用状态向量 v∈F2mn\mathbf{v} \in \mathbb{F}_2^{mn} 表示所有灯的亮灭情况。 其中 v(i−1)⋅n+j=1\mathbf{v}_{(i-1)\cdot n + j} = 1 表示 (i,j)(i, j) 灯亮，反之则灭。初始状态向量记为 v(0)\mathbf{v}^{(0)}。

所有的操作对应操作向量 x∈F2mn\mathbf{x} \in \mathbb{F}_2^{mn}。 其中 x(i−1)⋅n+j=1\mathbf{x}_{(i-1)\cdot n + j} = 1 表示操作了 (i,j)(i, j) 灯，反之不操作。此处不考虑重复操作。

操作 (i,j)(i, j) 灯带来的影响是使自己及周围灯改变亮灭，也即使状态向量中对应自己及周围灯的元素加 1。 从而定义如下状态转移矩阵，其第 ((i−1)⋅n+j,(s−1)⋅n+t)((i - 1) \cdot n + j, (s - 1) \cdot n + t) 元素为 1 则表示操作 (i,j)(i, j) 灯时会对 (s,t)(s, t) 灯产生影响：

A=[KnInOn⋯OnInKnIn⋯OnOnInKn⋯On⋮⋱⋮On⋯InKnInOn⋯OnInKn]mn×mnA = \begin{bmatrix} \mathbf{K}_n & \mathbf{I}_n & \mathbf{O}_n & \cdots & \mathbf{O}_n \\ \mathbf{I}_n & \mathbf{K}_n & \mathbf{I}_n & \cdots & \mathbf{O}_n \\ \mathbf{O}_n & \mathbf{I}_n & \mathbf{K}_n & \cdots & \mathbf{O}_n \\ \vdots & & \ddots & & \vdots \\ \mathbf{O}_n & \cdots & \mathbf{I}_n & \mathbf{K}_n & \mathbf{I}_n \\ \mathbf{O}_n & \cdots & \mathbf{O}_n & \mathbf{I}_n & \mathbf{K}_n \end{bmatrix}_{mn \times mn}

这是一个分块三对角矩阵。其中：

Kn=[110⋯0111⋯0011⋯0⋮⋱⋮0⋯1110⋯011]n×n\mathbf{K}_n = \begin{bmatrix} 1 & 1 & 0 & \cdots & 0 \\ 1 & 1 & 1 & \cdots & 0 \\ 0 & 1 & 1 & \cdots & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & \cdots & 1 & 1 & 1 \\ 0 & \cdots & 0 & 1 & 1 \end{bmatrix}_{n \times n}

In\mathbf{I}_n 为单位阵，On\mathbf{O}_n 为零矩阵。

则经过所有操作后得到的终止状态向量即为：

v=v(0)+Ax\mathbf{v} = \mathbf{v}^{(0)} + \mathbf{A} \mathbf{x}

游戏有解等价于以下方程组有解：

Ax=v(0)\mathbf{A} \mathbf{x} = \mathbf{v}^{(0)}

也即：

  • 解存在 ⇔\Leftrightarrow ∀v(0)∈F2mn,v(0)∈Col(A)\forall \mathbf{v}^{(0)} \in \mathbb{F}_2^{mn}, \quad \mathbf{v}^{(0)} \in \text{Col}(\mathbf{A}) ⇔\Leftrightarrow dim⁡(Col(A))=rank(A)=mn\dim(\text{Col}(\mathbf{A})) = \text{rank}(\mathbf{A}) = mn
  • 解唯一 ⇔\Leftrightarrow det⁡(A)≠0\det(\mathbf{A}) \ne 0 ⇔\Leftrightarrow rank(A)=mn\text{rank}(\mathbf{A}) = mn

从而若 A\mathbf{A} 满秩则解存在且唯一，否则解可能不存在且可能不唯一。

对于经典的 5×55 \times 5 关灯游戏，状态转移矩阵 A\mathbf{A} 的秩为 2323，不满秩，所以解可能不存在也可能不唯一。 实际枚举发现存在下述两种不改变任何灯的操作，说明了解确实不唯一。

图 1：不改变任何灯的操作 1（红色为操作，蓝色为不操作）
图 1：不改变任何灯的操作 1（红色为操作，蓝色为不操作）
图 2：不改变任何灯的操作 2（红色为操作，蓝色为不操作）
图 2：不改变任何灯的操作 2（红色为操作，蓝色为不操作）

问题 2

精确代数求解

可以通过求解线性方程组：

Ax=v(0)\mathbf{A} \mathbf{x} = \mathbf{v}^{(0)}

完成任务。

如果 A\mathbf{A} 满秩则可以直接求解，否则可以使用最小二乘法求最优解。

DQN 强化学习

除了直接求解线性方程组外，我们可以基于 DQN（Deep Q-Network）训练一个人工智能近似求出最优解。

  1. 马尔可夫决策过程

    首先将游戏形式化为马尔可夫决策过程 M=(S,A,T,R,γ)\mathcal{M} = (\mathcal{S}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma)：

    • 状态空间 S\mathcal{S}：所有可能的灯阵状态，每个状态 s∈{0,1}m×ns \in \{0,1\}^{m \times n} 表示当前各灯的亮灭情况
    • 动作空间 A\mathcal{A}：选择操作 (i,j)(i, j) 灯，共 ∣A∣=m×n|\mathcal{A}| = m \times n 个离散动作
    • 状态转移 T\mathcal{T}：确定性转移，执行动作后目标格子及其周围状态取反
    • 奖励函数 R\mathcal{R}：每步给予 −1-1 的步数惩罚，当所有灯熄灭时给予 +100+100 的目标奖励
    • 折扣因子 γ\gamma：取 0.990.99 以平衡步数与目标

  2. 神经网络架构

    采用卷积神经网络结构，以利用灯阵的空间局部性：

    层类型配置描述
    输入层1×m×n1 \times m \times n 张量0/1 亮灭表示
    卷积层 132 filters, 3×33\times3, ReLU捕获局部十字形
    卷积层 264 filters, 3×33\times3, ReLU学习复合特征
    全连接层128 单元, ReLU全局信息整合
    输出层m×nm \times n 个 Q 值每个动作对应的状态-动作值

  3. 训练机制与优化策略

    训练过程采用标准 DQN 流程：

    • 探索策略：采用 ε-greedy\varepsilon \text{-greedy} 策略，初始时 ε=1.0\varepsilon=1.0，随训练指数衰减至 0.010.01。前期充分探索避免局部最优，后期利用已学策略精细化。

    • 经验回放：设置容量为 10510^5 的回放缓冲区，随机采样小批量经验以打破时间相关性。

    • 稠密奖励：在稀疏奖励（每步 −1-1，胜利 +100+100）基础上，增加亮灯数减少的稠密奖励（减少 +5+5），以引导早期学习。待策略稳定后逐步移除，避免次优解。

  4. 评估

    每 500 个 episode 进行一次评估，记录：

    • 成功率：在限定步数内（如 3mn3mn 步）完成游戏的比例
    • 平均步数：成功 episode 的实际步数均值，衡量解的质量
    • Q 值收敛性：检查目标状态下的最大 Q 值是否稳定收敛

方法对比

对比代数求解以及 DQN 强化学习方法：

维度精确代数求解DQN 强化学习
解的质量理论保证全局最优（最少步数）启发式近似，可能陷入局部最优
计算复杂度训练无开销；推理 O(mn3)O(mn^3)，因为带状矩阵训练 O(E⋅mn)O(E \cdot mn)（EE为 episode数）；推理 O(mn)O(mn)
可扩展性受限于矩阵求逆，大规模困难训练后推理时间与网格线性相关，可扩展至更大规模
适应性要求状态观测精确，对噪声敏感可通过数据增强学习鲁棒策略，容忍观测误差
在线调整需重新求解方程组支持增量学习，适应动态变化的初始配置

参考文献

  1. Anderson, M., & Feil, T. (1998). Turning Lights Out with Linear Algebra. Mathematics Magazine, 71(4), 300–303.

  2. Drissa D. C. (2023). Lights Out: An Application of Linear Algebra over a Finite Field.