《算法竞赛入门经典》思考笔记

CodeingBoy 12月 05, 2017

P72

子集生成

增量构造法的代码解析

增量构造法的这堆代码一看就觉得不能理解:

疑问有下:

  1. 为什么每次递归要打印当前集合?
  2. 第 4 行的 s 变量有何作用?

为什么每次递归要打印当前集合?

假设我们要用上面的代码枚举 {0,1,2} 的子集好了。使用以下代码进行验证:

得到以下输出:

可以看到,第二个(0 1)子集是在第一个子集的基础上递归遍历的。由于子集(除了空集)长度最小可以为 1,因此 {0} 也算是 {0, 1, 2} 的子集。

这样来看,为什么每次递归都要输出当前子集就不难得出了:当前的子集也算子集,并且要在该子集的基础上枚举下去。

解答树如下,注意整颗解答树除了根节点都需要输出:

                         *,*,*
0,*,*                  1,*,*                            2,*,*
0,1,*…              1,0,*…                         2,0,*…
0,1,2…              1,0,2…                         2,0,1…

注意后面的说明:

(n = 10 的情况下)这颗解答树上有 1024 个节点。这不难理解:每个可能的 A 都对应一个节点,而 n 元素恰好有 2^n 个子集,2^10=1024。

s 变量有何作用

这句语句的作用到底是什么呢?

下面的循环 i 是从 s 作为初始值开始的,而 i 是用于抽取元素进行穷举,因此 s 是用于穷举 A 中元素的起始下标。

但为什么要从 s 开始而不是 0 开始呢?仍然以上面的例子,思考一下递归调用时候的情况:

cur = 0 时,s = 0,穷举范围 0 ~ 3
cur = 1 时,s = A[cur – 1] + 1 = A[ 1 – 1] + 1 = A[0] + 1 = 0 + 1 = 1
cur = 2 时,s = A[1] + 1 = 2
cur = 3 时,s = A[2] + 1 = 3

回顾传入的数组:
{0, 1, 2}

可以看出,cur 大于 0 时,A[cur – 1] + 1 就是指当前在 cur 位应该穷举的最小的值。

为什么不用 A[cur]?请注意 cur = 3 的时候,如果使用 A[cur] 将会造成数组越界。

另外,这一增量解析法只适用于 {0, 1, 2…} 的情况,若使用其它起始元素不为0,或两个元素之间的增量不为 1,或不是有序的数组,可能会不能正确工作。

位向量法的代码解析

接下来是位向量法的代码:

阅读了一下代码就有好几个问题了:

  1. 位向量法是怎么工作的?
  2. 以下这句话应该怎么理解?

     

    现在的解答树有 2047 个节点,比刚才的办法略多。这个也不难理解:所有部分解(不完整的解)也对应着解答树上的节点。

位向量法是怎么工作的?

为了搞清楚这个问题,我觉得要使用调试工具跟踪程序的重要举动才能了解明白了。

由于位向量法采用了递归的方式,因此把它的程序调用栈表现出来并且配上变量的更改应该是有益的。

cur = 0,B[0] = 1,递归调用自身

cur = 1,B[1] = 1,递归调用自身

cur = 2,B[2] = 1,递归调用自身

cur = 3,cur == n,因此打印出当前的集合(0 1 2)

B[2] = 0,递归调用自身

打印出当前的集合,由于 B[0]、B[1] 都为 1 而 B[2] 为 0,只打印出集合 0 1

B[1] = 0,递归调用自身

cur = 2,B[2] = 1,递归调用自身

cur = 3,cur == n,由于 B[0]、B[2] 都为 1 而 B[1] 为 0,因此打印出集合 0 2

B[2] = 0,递归调用自身

打印出当前的集合,由于 B[0]为 1 而 B[1]、 B[2] 为 0,只打印出集合 0

B[0] = 0,递归调用自身

cur = 1,B[1] = 1,递归调用自身

cur = 2,B[2] = 1,递归调用自身

cur = 3,cur == n,由于 B[1]、B[2] 都为 1 而 B[0] 为 0,打印出集合 1 2

B[2] = 0,递归调用自身

打印出当前的集合,由于B[1] 为 1 而 B[0]、B[2] 为 0,只打印出集合 1

B[1] = 0,递归调用自身

cur = 2,B[2] = 1,递归调用自身

cur = 3,cur == n,由于 B[2] 为 1 而 B[0]、B[1] 为 0,因此打印出集合 2

B[2] = 0,递归调用自身

打印出当前的集合,由于 B[0]、B[1]、 B[2] 都为 0,打印空集

程序结束

由上面的调用栈可以看出位向量法的工作原理:对每一分支穷举每一种选择,如果沿着一个分支到达了解答树的叶子节点端,则返回最近一个尚未穷举完毕的节点继续穷举,直到穷举结束。

个人觉得颇有种回溯法的思想在里面。

不完整的解?

现在的解答树有 2047 个节点,比刚才的办法略多。这个也不难理解:所有部分解(不完整的解)也对应着解答树上的节点。

我们把第一次穷举的解答树写出来试试:

1 * * → 1 1 * → 1 1 1 (0 1 2)
                     → 1 1 0 (0 1)
        → 1 0 * → ……

可以看到,只有解答树最下面一层的节点结果才是我们需要输出的内容,而其中的中间结点只是存储“在这个节点的穷举状态”。

因此,中间结点就是上面所说的“不完整的解”,并由此造成了解答树的节点增多。

二进制法的工作原理

二进制法的思想还是稍微明白的,重新表述一下。

二进制法的基本工作原理:

  1. 为每一个数字编一个序号,然后从右到左排列。这样子,这个集合的掩码就可以表示为一个 n 位的二进制数
  2. 穷举 0 ~ (1 << n – 1) 之间的每一个二进制数,使用得出的二进制数作为掩码打印出集合元素

掩码是什么?

尝试简单地解释一下掩码:掩码就是控制每一位开关的二进制数。

啥?不明白?上例子:

假设有一集合 {4, 3, 2, 1},从右到左编序号为 3、2、1、0

那么,我可以用一个 4 位的二进制数控制这四个数字中每一个数字的出现与否,比如 1010 表示打开(在这个例子里面则为打印) 4、2,关闭 3、1。1111 表示这四个元素全部打开(打印)。

书里面还提到了使用掩码进行集合运算,通过使用位运算符计算掩码,我们也能得到新的集合的掩码并表示出来。

为什么是 1 << n – 1 而不是 1 << n?

设 n = 4,1 << n 就是将 1 左移 4 位,也就是 10000。

哎呀,不是全 1 啊(整个集合都表示的情况下应该是全部为 1),所以我们要进行减 1,获得 10000 – 00001 = 01111。

咦,那最高位(最左边)的 0 不用管吗,请注意,集合是从 0 开始编序号的。因此只有 0 ~ n-1 位是有对应数字的,第 n 位不对应任何数字。

二进制法与位向量法的差异

然而过了一段时间,貌似发现二进制法和位向量法好像也没什么不同……位向量法是通过构造一个位向量 B={B1, B2, B3, …, Bn} 实现的,这些位向量可以用来表示元素的使用与否。而二进制法也是通过一个位向量(二进制数)来表示元素的使用与否。那么它们之间到底有什么差别?

试着写出以下代码:

通过调试器可以看到,main 中的循环将逐一给 print_subset 传入 0 ~ 1<<10 – 1(由于左移一位相当于乘以 2,因此 1<<10 = 1 * 2^10 = 1024)。

而 print_subset 接收到 n 和 s(对应main 中的 i)后,也会开始一个循环,只不过这个循环是从 0 ~ n-1 的。在循环之中,对 s 和循环得到的“掩码”进行与运算。

我们来看当 s = 13 的时候的情形:

  1. s = 13(1101), i = 0, s & (1<<i) = 1101 & 0001 = 0001,输出(从右往左数的,下同)第 1 个元素
  2. s = 13(1101), i = 1, s & (1<<i) = 1101 & 0010 = 0010,由于 s 第 1 位为0,不输出
  3. s = 13(1101), i = 2, s & (1<<i) = 1101 & 0100 = 0100,输出第 3 个元素
  4. s = 13(1101), i = 3, s & (1<<i) = 1101 & 1000 = 1000,输出第 4 个元素
  5. s = 13(1101), i = 4, s & (1<<i) = 1101 & 0000 = 0000,不输出
  6. 接下来的过程都和第 5 步类似

也就是说,print_subset 中的循环将枚举每一位二进制位,根据传入的 s 对应位上是否为 1 决定是否输出对应元素。而对应集合的枚举则由 main 中的循环进行枚举。

枚举二进制数实际上是利用了二进制的表示方式,对于 0~3 的二进制数有:000, 001, 010, 011。依靠这样子来进行集合的枚举。

从这角度看,二进制法实际上就是利用二进制数而不是布尔数组作为位向量的位向量法。

四皇后解答树的解释

192 页的解答树题目下面说到:

在 (0, 2, *, *) 中,第二行无论将皇后放到哪里,都会和第 0 行和第 1 行中已放好的皇后发生冲突……

不对啊?不是 8 列吗?我可以放在别的列上啊?后来一看解答树的图题:四皇后问题的解答树……

解答树的解释

既然都写到这里了,那就顺带对四皇后问题中上面的情况做一次模拟吧:

解答树中,第 1 位数字表示第一行中的皇后应该放在哪一列,以此类推。由于皇后不可能在同一行、同一列出现,不可能出现一行有两个皇后的情况,因此只要求出每一行中的皇后的列位置即可。

(0, *, *, *) 时,在第一行第 1 列放置一个皇后,如下所示(O 代表皇后放置位置,X 代表不可以放置皇后的地方):

O X X X
X X    
X   X  
X     X

由于第一行第 1 列位于对角线上,所以无法放置皇后,跳过。

(0, 2, * , *) 时,在第一行第 2 列放置一个皇后:

O X X X
X X O X
X X X X
X     X

可以看出,第三列已经没有位置可供放置皇后了,仅存的两个空位无法满足解的要求。

对八皇后代码的解析

对这段八皇后求解代码做一些解释:

第 2 行的 for 循环,i 代表的意义为“当前遍历的列”而不是“当前遍历的行”(cur 才是行)
第 4 行会尝试在 cur 行 i 列放置皇后,由于 i 赋值到了 C[cur],因此该皇后的坐标可以表示为(cur, C[cur])
第 5 行的 for 循环会遍历每一行,查找 j 行的皇后是否和 cur 行的皇后冲突
第 6 行的判断条件分成三部分看待:

  1. C[cur] == C[j],检测同一列上是否有皇后
  2. cur – C[cur] == j – C[j],书本上已经说了 y-x(x-y 也一样,做一下交换) 可以代表主对角线的情况,因此这一条件会检测 cur 行的皇后是否在 j 行皇后的主对角线上
  3. cur + C[cur] == j + C[j],书本上已经说了 x+y 可以代表副对角线的情况,因此这一条件会检测 cur 行的皇后是否在 j 行皇后的副对角线上
  4. 不需要检测同一行上是否有皇后吗?不需要,因为每一行只会放置一个皇后

等等,那循环是怎么获得皇后的坐标信息的?注意数组 C 仅仅是一个一维数组而不是二维数组,每一行只存在一个皇后,一维数组也就足够使用了。

关于八数码问题的思考

为什么八数码问题可以归结为图上的最短路问题?

先举一个例子好了,拿书上的举例来说:

初始状态:

2 6 4
1 3 7
  5 8

终止状态:

8 1 5
7 3 6
4   2

如果我们要手工求解从初始状态到终止状态下最少的移动步数,应该怎么做?

如果把 9 个格子看成迷宫的话。从空方格的角度看,我们可以把初始状态下的空方格看作入口,而终止状态下的空方格为出口。这样就需要我们求解到从迷宫入口到出口的最短步数。

在以前的迷宫问题中(参见 164 页),我们可以使用 BFS(Breadth-First-Search,广度优先搜索)进行求解,基本思想是从一个入口尝试所有可能的选择路径,直到找到一个最先到达了迷宫出口的路径为止。

到这里已经可以将八数码问题归结为图上的最短路问题了。只是八数码问题和迷宫问题还有一个重大的差异。

可以观察到,如果只看空方格,从初始状态的入口走到终止状态的出口仅需要一步,但是这是不正确的答案。在八数码问题里面,我们不仅需要求出最短路,还需要检验其它 8 个方格中的数字是否与给定终止状态一致。

2 6 4
1 3 7
5   8

幸运的是检验难度不难,只需要在 BFS 搜寻的过程中,模拟路径中的数字状态,到达出口时检验是否与终止状态一致即可。

代码解析

掌握了基本的求解思路,接下来看书里的代码。由于判重有3 种办法,我只使用 STL 方式判重的代码进行解析,以下代码以及其它判重方式的代码可以到这本书的 Github Repository 查看。

以下代码复制自本书的 Github Repository,我将书上对应注释补上并按照我自己的代码风格进行了格式化:

输入使用 Github Repository 中提供的输入:

先阅读了一次代码,提出以下问题:

  1. typedef int State[9] 什么鬼?
  2. 判定移动合法后是如何拓展新节点的?
  3. 为什么要尝试插入查找表?
  4. 插入查找表的逻辑是怎样的?

接下来尝试解答这几个问题。

typedef 与数组

如果你和我一样,认为 typedef 的语法是

typedef 原类型 新类型

的话,看到 typedef int State[9] 会觉得大吃一惊:难道不应该是 typedef int[9] State 吗?

然而,使用 typedef 声明数组的时候,语法是这样的:

引自 WikiPedia

为什么呢?唔……不知道啊。

判定移动合法后是如何拓展新节点的?

实践出真知,因此我们运行程序后输入上述提供的数据,使用调试器查看程序内状态。

输入数据后,初始状态为: {2, 6, 4, 1, 3, 7, 0, 5, 8}

此时,d = 0,指示空方格想要往上方向拓展。空方格的位置为 (2, 0)(3 行 1 列),移动后的位置为 (1, 0)(2 行 1 列).请注意,X 代表的是(从上到下数)的行数,Y 代表的是(从左到右数)的列数,不要与数学中的坐标系搞混。

判定后发现移动是合法的,没有越出边界,因此开始拓展节点:

先获取到队尾元素的引用,这样后面好使用。接下来第 2 行将现有的元素复制为队尾元素的状态。执行后 t 的状态为 {2, 6, 4, 1, 3, 7, 0, 5, 8}。

接下来对队尾元素的状态进行更新,需要进行两件事情:

  1. 将空方格原坐标的值赋值为空方格现坐标的值
  2. 将空方格现坐标的值赋值清除

第 3 行就是完成第二件事情,newz 是之前计算出空方格在状态数组中的实际下标(状态数组是一维数组,我们讨论的图是二维的,因此需要将二维映射到一维去)。然后将旧状态(s)中空方格的值赋予新状态(t)中空方格的值。(当然了,你可以直接赋值 0)

第 4 行完成第一件事情,在此不表。

第 6 行更新当前路径所走过的步数。当前路径所走过的步数 = 上一状态路径所走步数 + 1。

好了,这时候就会看到会尝试插入查找表,到底为什么要尝试插入查找表呢?

尝试插入查找表的逻辑是?

跟入后发现第 2 行这个循环好像在干不得了的事情,来看看到底在干嘛:
st 数组存储了当前走过的所有状态,s 则是传入的队尾元素下标。可以看到循环正试图将 v 赋值为 v * 10 + st[s][i]。
其中,st[s] 为队尾元素的状态数组,st[s][i] 则是第 i 方格的数字,而 v * 10 将之前的状态组合为 i – 1 位数字。

例如,对 st[s] = {2, 6, 4, 0, 3, 7, 1, 5, 8} 有:
i = 0, v = 0 * 10 + 2 = 2;
i = 1, v = 2 * 10 + 6 = 26;
i = 2, v = 26 * 10 + 4 = 264;
i = 3, v = 264 * 10 + 0 = 2640;

循环完毕后,我们就得到了对应一个状态的 9 位数字,这个例子中就是 264037158。

接下来使用这个 9 位状态数字到 vis (vis 是一个集合)中搜索,如果 vis 中已经有这个数字了,会返回大于 0 的值。这就表示已经存在这个状态了。否则将这个状态数插入到列表中。

为什么要判断重复状态呢?

在 BFS 问题中,我们需要判断是否已经重复访问了一个节点,因此需要使用一个值跟踪节点是否访问过。

如果在图中不进行重复访问判断的话,可能会形成回路,以至于无法求出答案。举个例子,如果不进行重复访问判断的话,以下状态将是可能的:

2 6 4
1 3 7
  5 8

(中间状态忽略)

2 6 4
3 5 7
  1 8

(中间状态忽略) 

2 6 4
5 1 7
  3 8

(中间状态忽略)

2 6 4
1 3 7
  5 8

进行重复访问判断还有一个好处,由于插入记录是先到先得的,因此到达一个状态的最短路径最先记录这个状态,而达到相同状态但路径长度大于最短路径的记录将会被拒绝,无形中起到剪枝的作用。

对于“二分查找求下界”代码的解析

为什么不会发生死循环?

棋盘覆盖问题的求解思路

循环日程表问题的递归求解思路

巨人与鬼问题的求解思路

 

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/%e3%80%8a%e7%ae%97%e6%b3%95%e7%ab%9e%e8%b5%9b%e5%85%a5%e9%97%a8%e7%bb%8f%e5%85%b8%e3%80%8b%e6%80%9d%e8%80%83%e7%ac%94%e8%ae%b0/

发表评论

电子邮件地址不会被公开。 必填项已用*标注