解题报告 —— 从水题开一个头

昨天有人跟我讨论一道水题,勾起了解题的念头。题目不难,但也有值得讨论之处。姑且以它的解题报告,开个写解题报告的头。

源起

在前公司四年,有两年半担任兼职讲师。一开始给非软件专业(一般是通信专业)的同事介绍Java,后来变成了主要讲解算法和数据结构题,以应对本社的软件能力等级考试。我和其他几个被选拔出来的讲师,工作时间里有一部分变成了光明正大地刷算法题。很多同事把做题视作洪水猛兽,我们却AC之后继续研究优化,相当享受。当然还得做课件和上课又是一回事。

因为安保,所有资料都在公司内网。现在离开老东家,想把无关保密部分整理出来作为自己的积累,突然发现凭回忆非常零碎。老实说,多数题在ACM玩家来看,就算不是水题,也就中等难度;但钻研其中,算法的取舍,各种因素的权衡,也是一种修炼。自己资质一般,如果不这些所得用文字留下来,一不小心就会原地踏步。水题也好,重新开个头吧。

题目

题目来自口头转述,只有大意和约束:

  • 有一个 N * N 的矩阵图,上面有 M 个顺序编号的点(1 ~ M)和 一些无法通过的区域(9),余下区域为0。

  • 求从 1 到 M 顺序经过全部点的 最短路径有多少条

  • 从描述的例子看,还没轮到的点允许通过,只是后面轮到时还是得走一次。

    譬如说从 1 走到 5,先走 1 -> 2 这段,到达 2 之前, 3、4、5 都相当于普通的点,也就是0,可以经过。而就算你经过了这三个点,譬如说 4 在 1-> 2 的最短路径上,走到 3 时还是得往 4 走。

  • 因为是水题,数据量极小, 3 ≤ N ≤ 7,3 ≤ M ≤ 5。也就是穷举型的思路都可以做。如果进一步想验证效率,可以人为调大数据量看看。(我以前跟毅跞经常这么干)

输入输出示例

  • 输入
5 4
1 0 0 0 0
0 0 0 0 0
0 2 0 4 0
0 0 0 9 0
0 0 0 3 0
  • 输出
18

思路

数学推导

有些问题经数学推导之后,是可以有直接的公式解,而不需要一步步模拟的(典型的如 约瑟夫环)。退一步,如果问题本身无法直接推导,但是某种简化情况可以推导,也能为找思路提供方向。

乘法原理

首先,题目里的点必须按顺序通过,那么根据 乘法原理 ,最终答案等于 次序上相邻的点的最短路径数的乘积。假定 \( C_{a, b} \) 是 a 点 到 b 点之间的最短路径数,那么写成数学式就是:

$$ \prod \ {i=1} ^{M - 1} {C \{i, i + 1}} $$

这就把问题简化成了两点之间的最短路径数了。不过似乎原题为了减低难度,在题目里就有提醒这点。

排列组合

假定我们不考虑禁行区(9)的存在,那么两点之间的最短路径,距离显然为他们之间的 曼哈顿距离

假设 横向的步数为W,纵向的步数为H ,同时横向移动一步标记为0,纵向标记为1,那么长度为 曼哈顿距离 的路径数,就相当于W个0和H个1的全排列:\( A(W+H) = (W+H)! \) 。但因为0 和 1都有大量重复,这并不是一个真正的全排列,所以还要把 0 和 1内部的组合数排除掉,最终得到: \( \frac{(W+H)!}{W! H!} \) 。

在 W+H不是特别大(换言之 (W+H)! 没有超出表示范围,以这题为例,W+H不超过7,那么最大的数不过5040)的情况下,这样就可以提前缓存好 N!,那么在W 和 H 确定之后只要做两次除法就得到答案了。

当然,这只是顺便延伸一下,实际上这道题因为 9 的存在,不能这么算。

代码参考

Brute-force (dfs)

注1:这里开始会贴代码。一般我用 C/C++ 完成算法题,可以比较好地选择底层的数据结构实现。不过这里为了节省空间,用了Python来展示代码,而且只贴关键函数,输入输出部分就略过了。Python的代码非常接近 伪代码,相信没有写过Python的朋友也能很好理解。

注2:为了简便,这里的队列我直接用了list。但实际上list 的 pop(0) 会修改后面全部元素的位置,复杂度是O(n)。Python里更好的选择是deque,C/C++可以使用STL或者自己实现一个循环队列。

如果没能直接找到数学关系直接计算,也没能一眼看出合适的算法,那么暴力不失为一个好的开始。具体到这里,暴力的做法一般就是用DFS穷举所有可能的路径,找出中间最短那几条。

当然,直接暴力,内存和时间复杂度都会很夸张(这里如果不限制长度,先穷举所有路径,再计算其中最短的数量,操作是很庞大的),所以哪怕是第一份代码,我也加入了一些直接能想到的剪枝:一旦发现了dis大小的路径,那么所有大于dis的路径都不必再尝试了。

示例代码一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def dfs(sp, ep, dis):
global MinDis, CntWay, Vis
dis += 1
if dis > MinDis:
# prunning
return
if sp[0] == ep[0] and sp[1] == ep[1]:
if dis == MinDis:
CntWay += 1
else:
# dis < MinDis
MinDis = dis
CntWay = 1
return
# up
row, col = sp
row -= 1
if row >= 0 and not Vis[row][col] and Map[row][col] != 9:
Vis[row][col] = True
dfs((row, col), ep, dis)
Vis[row][col] = False
# down
row += 2
if row < N and not Vis[row][col] and Map[row][col] != 9:
Vis[row][col] = True
dfs((row, col), ep, dis)
Vis[row][col] = False
# left
row -= 1
col -= 1
if col >= 0 and not Vis[row][col] and Map[row][col] != 9:
Vis[row][col] = True
dfs((row, col), ep, dis)
Vis[row][col] = False
# right
col += 2
if col < N and not Vis[row][col] and Map[row][col] != 9:
Vis[row][col] = True
dfs((row, col), ep, dis)
Vis[row][col] = False
def findWay(sp, ep):
global MinDis, Vis
MinDis = MAX
Vis[sp[0]][sp[1]] = True
dfs(sp, ep, 0)
Vis[sp[0]][sp[1]] = False
return CntWay

以上的代码是基于来问我的人的代码,把里面的错误改掉之后得到的。主函数调用findWay() 即可。关键部分在于到达目标时的判断:如果当前这条路的距离跟最短距离相等,那么计数器加一;否则就是发现了更短的路(不存在更长的情况,因为剪枝处理掉了),更新最短距离,并把计数器置一(注意不是置零)。

如果调整一下代码,还能把公共部分的检查提取出来。示例代码二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def dfs(sp, ep, dis):
global MinDis, CntWay, Vis
row, col = sp
# log(sp, dis, MinDis, Vis[row][col])
dis += 1
# legal check and prunning
if dis > MinDis or Vis[row][col] or Map[row][col] == 9:
return
if row == ep[0] and col == ep[1]:
if dis == MinDis:
CntWay += 1
else:
# dis < MinDis
MinDis = dis
CntWay = 1
return
Vis[row][col] = True
# up
row -= 1
if row >= 0:
dfs((row, col), ep, dis)
# down
row += 2
if row < N:
dfs((row, col), ep, dis)
# left
row -= 1
col -= 1
if col >= 0:
dfs((row, col), ep, dis)
# right
col += 2
if col < N:
dfs((row, col), ep, dis)
Vis[sp[0]][sp[1]] = False

BFS

DFS冗余运算比较多,就会很自然地想,BFS能不能有所改善呢?

能不能改善先不管,我们先用BFS做出来。示例代码三:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def bfs(sp, ep):
cnt_way = 0
# None as step flag
queue = [sp, None]
arrive = False
while len(queue) > 1:
point = queue.pop(0)
if not point:
if arrive:
return cnt_way
queue.append(None)
continue
row, col = point
# legal check
if Map[row][col] == 9:
continue
if row == ep[0] and col == ep[1]:
cnt_way += 1
arrive = True
continue
# up
row -= 1
if row >= 0:
queue.append((row, col))
# down
row += 2
if row < N:
queue.append((row, col))
# left
row -= 1
col -= 1
if col >= 0:
queue.append((row, col))
# right
col += 2
if col < N:
queue.append((row, col))
return 0

基本原理跟之前的暴力法差不多,都是穷举所有可能的路径并且计数。

改善的地方在于,DFS是一条路走到底再去试别的路,你没办法预知先试的路是长还是短;BFS可以看作多条路同时往外挪步,后面的路肯定是比当前路要长(或者相当,起码不可能更短) ,一旦到达目标,后面更长的路可以不用直接尝试了。这里我用了一个None作为层次标记,一旦到达,只把同距离的计数完就退出。

但这也有代价:因为同时挪步,为了不互相影响,BFS不能像DFS标记走过的点,所以队列里其实有大量 来回步 !如果地图比较大(这样DFS有些路就要走很远才到头),而实际点与点之间比较近(BFS很快就能结束),那么这份代码是比DFS效率高一些的; 但如果反过来(譬如有些相邻点分布在对角线上两头),大量来回步造成的浪费更多,那么这种做法实际得不偿失。

BFS + DP

能不能像DFS那样也记录已走过的点,然后不重复走?

TODO: 此处最好有图,mark一个,有空补

不行。因为可能有多条最短路径会通过同一个点,如果一个点只能走一次,会漏算大量的路径。DFS之所以可以这么做,是因为回溯时会恢复状态,记录只是为了不走回头路,别的路径还是能通过这个点。

那如果我们做更详细的标记呢?譬如引入:OPEN(没走过),CLOSE(已离开) 以及 ONGOING(进行中) 三个状态。对应队列的状态,分别就是 从未进队已入队并出队正在队列中 三种状态。

我们知道,BFS的特性会让 从起点起同样距离的点 一起访问完,然后才会继续尝试 + 1 距离的点,一层层往外走。那么假定从X点往外一步访问到一个Y点,并且Y的状态为:(下面的dis(X)指起点到X点的最短距离)

  1. OPEN,Y点从未被访问,直接进队并且改为ONGOING
  2. CLOSE,Y点被其它点访问过,并且 Y已经在X之前 出队了,dis(Y) ≤ dis(X), 经X再到Y这种走法,至少比之前到Y的走法要额外多一步(假定dis(Y) = dis(X)的话,至少还要加上一步;如果是 < ,那就不止了),这种走法无论如何不能再产生最短路径了 (划重点,请仔细体会这句话),所以Y不用再进队了
  3. ONGOING,Y点被其它点访问过,并且还没出队,而X现在作为起点,说明刚刚出队,dis(Y) ≥ dis(X),那么经X到Y这种走法,起码还是有可能存在一条最短路径的,Y点再次入队

这种做法把CLOSE状态下的冗余给去掉了。因为一个点的前置节点一个是已经CLOSE掉的,所以回头路也不会存在了。

不过这种改进仍然是有限的,从目前的推导看,ONGOING里还是可能存在 dis(Y) = dis(X) 的情况的浪费,而且其实同一个点多次进队也是没有必要的。这种改进改动的代码不多,我就不再贴示例了。

DP

如果不是为了引导问我的人一步一步考虑到这里,这种水题真想一开始直接写DP

讨论DP之前,还要引入这道题具有的一个性质:以任意点为起点,相邻的点的dis值都不会相等。

首先我们来看一下没有障碍物的情况,下图以0处为起点,标出起点到各点的最短距离:

3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
5 4 3 4 5

很容易得出,无论以哪里为起点,相邻的点的dis值一定是相差1。

而如果我们往上放一个障碍物呢,这时 障碍物在不在从起点到终点 唯一的最短路径上 有两种情况(注意,是唯一):

  • 不在(可能根本不在任何一条最短路径上毫无影响,也可能影响其中一条,剩下的还能走),那么依然存在这个dis值的最短路径,不改变该终点的dis值。
  • 在,那么又有两种情况:
    • 绕路:由于绕路而造成的dis值增大,必然是偶数的。由于只能上下左右移动,不能对角移动,绕路产生的额外移动,都是关于障碍物对称的。
    • 从旁边没有被障碍物影响的点走一步过来。由于唯一的最短路径已经被障碍物影响,剩下没被影响的点,都是dis+1,再往回走一步,就变成了dis+2。

无论是哪种情况,变动的值都是偶数。而且这个性质在连续增加障碍物的过程中依然有效。所以相邻的点dis值不可能相等,依然保持相差1。(只是说变动都是偶数而已,相差不应该是2k+1吗,为什么一定是1?这里可以思考一下why)

接下来说DP:

动态规划的做法是,定义子问题,并且找到子问题之间的状态转移方程。如果中间有子问题的解是能被多次引用,那么对子问题解的缓存就能改善运算效率。这里不打算详细说DP,直接给转移方程:(提醒一下,题目是要求最短路径的数量)

假设 cw(x, y) (Count Way 缩写)是 起点 到 (x, y) 这个点的最短路径的数量,那么

$$ cw(x, y) = \sum{ cw(x-1, y), cw(x+1, y), cw(x, y-1), cw(x, y+1)} $$

计算过程中,我们需要一个表,用来记录cw值(dis值由BFS特性保证)。需要额外开辟一个表吗?其实不需要,我们把上面的状态再扩展一下,变成cw值就好:cw > 0 时,对应ONGOING;那么为了避免冲突,我把OPEN定义为0,CLOSE定义为-1。

OPEN 和 CLOSE 状态的处理都不用变,而ONGOING的处理变成对cw值大小的判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def bfs(sp, ep):
cnt_way = [([OPEN] * N) for i in range(N)]
cnt_way[sp[0]][sp[1]] = 1
queue = [sp]
while len(queue) > 0:
row, col = queue.pop(0)
# legal check
if Map[row][col] == 9:
continue
if row == ep[0] and col == ep[1]:
return cnt_way[ep[0]][ep[1]]
# up
r = row - 1
if r >= 0 and cnt_way[r][col] != CLOSED:
if cnt_way[r][col] == OPEN:
queue.append((r, col))
cnt_way[r][col] += cnt_way[row][col]
# down
r = row + 1
if r < N and cnt_way[r][col] != CLOSED:
if cnt_way[r][col] == OPEN:
queue.append((r, col))
cnt_way[r][col] += cnt_way[row][col]
# left
c = col - 1
if c >= 0 and cnt_way[row][c] != CLOSED:
if cnt_way[row][c] == OPEN:
queue.append((row, c))
cnt_way[row][c] += cnt_way[row][col]
# right
c = col + 1
if c < N and cnt_way[row][c] != CLOSED:
if cnt_way[row][c] == OPEN:
queue.append((row, c))
cnt_way[row][c] += cnt_way[row][col]
cnt_way[row][col] = CLOSED
return 0

知识共享 “署名-非商业性使用-相同方式共享” 4.0 (CC BY-NC-SA 4.0)”许可协议
本文为本人原创,采用知识共享 “署名-非商业性使用-相同方式共享” 4.0 (CC BY-NC-SA 4.0)”许可协议进行许可。
本作品可自由复制、传播及基于本作品进行演绎创作。如有以上需要,请留言告知,在文章开头明显位置加上署名(Jayce Chant)、原链接及许可协议信息,并明确指出修改(如有),不得用于商业用途。谢谢合作。
详情请点击查看协议具体内容。