分区法（II）电路板覆盖问题｜算法设计与分析

本文正在参加 人工智能创作者扶持计划

上一篇????分治法（一）概述 ｜ 算法设计与分析 - 掘金 (juejin.cn)

本系列分治法重点内容一览：

1. 详解当求解子问题与划分+合并子问题时间复杂度相同时，分治法的整体复杂度
2. 四色定理证明了分治法是解决棋盘覆盖问题的最优算法（至于为什么，限于笔者水平，暂无法给出证明）
3. 详解最短点对问题为什么可以做到线性的时间复杂度，包括鸽舍原理等。

【问题描述】

有一个 2^k \times 2^k(k>0) 的棋盘，恰好有一个方格与 其他方格不同，称之为特殊方格，并且称该棋盘为一特殊棋盘。

现在要用图 (b) 的4种不同形状的三格骨牌覆盖除了特珠方格外的其他全部方格，并且任何两个三格骨牌不能重叠。请给出一种覆盖方案。

【分治法求解思路】

当问题规模很小时，也即k=1时，可以直接求解。如图所示，存在四种情况，分别由1个不同形状的三格骨牌和特殊方格组成。

当问题规模比较大时，特殊方格在棋盘中可能存在4^k种情况，共需要\frac{4^k-1}{3}块三格骨牌。很难直接求解。

如果能在其余的三块区域各添加一个特殊方格，问题得解。

如图所示，添加一块三格骨牌在四个子棋盘汇合处，从而将原问题转化成了四个形式相同的子问题，问题规模变小，从而可以递归地解决四个子问题。

注意第二次覆盖，继续用三格骨牌覆盖汇合处时，特殊方格所占的2\times2棋盘已有特殊方格，该2\times2棋盘将不包括其他特殊方格。

【问题求解】

数据结构设计

• （1）棋盘 :

  • 整型二维数组board[size][size]，其中， size =2^k=2k=2^k=2k
  • 为了将递归过程中使用同一个棋盘，要将数组board视为全局变量

• （2） 子棋盘 :

  • 由棋盘左上角的下标tr,tc和棋盘大小s表示

• （3）特殊方格：

  • 用board[dr][dc]表示特殊方格，dr,dc是该特殊方格在二维数组中的下标

• （4）三格骨牌 :

  • 用全局整型变量tile表示，从1开始连续編号，board中3 个相同的整数表示一个三格骨牌。

分治算法

/*
棋盘覆盖问题的分治算法
问题描述：
给定一个大小为2^n * 2^n的棋盘，其中有一个方格已经损坏，现在要用L型骨牌覆盖整个棋盘，求最少需要多少个L型骨牌。
L型骨牌是由3个小正方形组成的，如下图所示：
  ____
 |    |
 |____|____
 |    |    |
 |____|____|
这个图示表示L型骨牌的形状，由3个小正方形组成。
 
分治算法思路：
将棋盘分成4个大小相等的棋盘，其中一个棋盘包含损坏的方格，其余三个棋盘不包含损坏的方格。
对于包含损坏方格的棋盘，用一个L型骨牌覆盖损坏的方格，然后递归地处理剩下的三个棋盘。
*/

#include <stdio.h>
#include <stdlib.h>

#define BOARD_SIZE 8

int board[BOARD_SIZE][BOARD_SIZE];
int tile = 0;

void chessboard(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) {
        return;
    }
    int t = ++tile;
    int s = size / 2;
    // 1. 覆盖左上角子棋盘
    if (dr < tr + s && dc < tc + s) {
        // 特殊方格在左上角子棋盘中
        chessboard(tr, tc, dr, dc, s);
    } else {
        // 特殊方格不在左上角子棋盘中
        board[tr + s - 1][tc + s - 1] = t;
        chessboard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    // 2. 覆盖右上角子棋盘
    if (dr < tr + s && dc >= tc + s) {
        // 特殊方格在右上角子棋盘中
        chessboard(tr, tc + s, dr, dc, s);
    } else {
        // 特殊方格不在右上角子棋盘中
        board[tr + s - 1][tc + s] = t;
        chessboard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    // 3. 覆盖左下角子棋盘
    if (dr >= tr + s && dc < tc + s) {
        // 特殊方格在左下角子棋盘中
        chessboard(tr + s, tc, dr, dc, s);
    } else {
        // 特殊方格不在左下角子棋盘中
        board[tr + s][tc + s - 1] = t;
        chessboard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 4. 覆盖右下角子棋盘
    if (dr >= tr + s && dc >= tc + s) {
        // 特殊方格在右下角子棋盘中
        chessboard(tr + s, tc + s, dr, dc, s);
    } else {
        // 特殊方格不在右下角子棋盘中
        board[tr + s][tc + s] = t;
        chessboard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

时间复杂度分析

$\begin{aligned} & T(k)=\left\{\begin{array}{cc} O(1) & k=0 \\ 4 T(k-1)+O(1) & k>0 \end{array}\right. \\ & T(K)=O\left(4^k\right) \end{aligned}$

• 由于覆盖一个 $2^k \times 2$棋盘所需的骨牌个数为 $\frac{4^k-1 }{3}$ ，与 $4^k$同阶，这意味着所需的图块数量随着棋盘的大小呈指数增长。

• 分治法对棋盘覆盖问题的最优性证明使用了四色定理，任何棋盘都可以用最多两种颜色来着色，这样就没有两个相邻的方块具有相同的颜色。这意味着任何棋盘都可以被分为两组，一组用一种颜色着色，另一组用另一种颜色着色，这样就没有两个相邻的方块具有相同的颜色。由于每张多米诺骨牌覆盖一个白色和一个黑色的方块，这意味着任何棋盘都可以用最多一半的多米诺骨牌来覆盖棋盘上的方块。

• 正如数学分析所证明的那样，这是解决该问题的任何算法的最佳增长率。这意味着没有其他算法可以比渐近意义上的分而治之算法做得更好，因为该分治法可以随着棋盘的大小任意变大。所以求解棋盘覆盖问题的分治算法是一个在渐进意义下的最优算法。

参考资料

中国大学MOOC ｜ 算法设计与分析 武汉理工大学

arxiv｜A Simple Proof for the Four-Color Theorem