问题重述
该问题源自我们 Linux 课题小组选择的期末课程项目，原题来自浙江大学的陈宇璟教授。
问题分析
这个问题如果正向思考，就显得很复杂。光源从四个方向发射出去，每经过一个格子，对于该格子要记录其光源到达的时间。但问题是格子事先不好确定，而且光源不只一个，是存在很多光源的。这还要比较最短的时间。
经这样一分析，采取正向传播方案则必须选择某种算法，而下面介绍的反向查找光源就容易理解与实现很多。
思路一：反向查找光源
整体思路
题目已经限定，光源所在网格和墙所在网格的最短到达时间时间为 $0$ 和 $-1$，因此我们只需关心为 $0$ 的网格。
光源正向传播到该目标网格，知道光源的初始速度以及该方向上光源到该目标网格之间的网格数，即可累加算出到达该网格的总时间。
以 $x$ 方向为例，设光源在 $x_1$ 处，且初始速度为 $m$ ,目标网格在 $x_2$ 处，($x_2>x_1$)中间没有墙，则光源从 $x_1$ 传播到 $x_2$ 的时间 $t_x$ 为：
$$
\begin{aligned}
t_x &= (x_2-x_1)m + \sum_{i=0}^{x_2-x_1}i \\
&= (x_2-x_1)m + \frac{(x_2-x_1)(x_2-x_1-1)}{2} \\
\end{aligned}
$$令 $d_x=x_2-x_1$，则
$$
t_x=d_x(m+\frac{d_x-1}{2})
$$同理可得, $y$ 方向的计算公式，
$$
t_y = d_y(m+\frac{d_y-1}{2})
$$现在我们可以很轻松地计算光源到网格的传播时间。
一个初始值为 $0$ 的网格，寻找光源传播到该网格的最短时间，可以分为四个方向，沿着每个方向查找光源，计算途径与途径的光源的传播时间，保留最小值，直至传播终止。四个方向的传播时间再一次选取最小值。
依照这个思路，我们组设计的 $bash$ 脚本的程序流程图如下，
实现难点及解决方法
二维数组的表示
bash 中没有二维数组，只有一维数组。这样无法像 C++ 和 Python 那样直接用一个数组表示。
因此我们选择使用多个一维数组，组合成一个二维数组。
比如要表示题目输入的矩阵 $A$ , 则可以写成
1
2
3
4
5
6
7
8
9
|
# 把输入的每行暂存到一个字符变量
for (( line1 = 1; line1 <= i; line1++ )); do
eval "read trow_${line1}"
done
# 将暂存的字符变量 trow_(i) 转换为数组 row_A(i)，构建原始矩阵A
for (( line3 = 1; line3 <= i; line3++ )); do
eval "row_A${line3}=(\${trow_${line3}})"
done
|
这样就曲线救国地构建了一个“二维”数组。当想访问第($i,$j)个元素，就可以使用
1
|
eval "echo row_A${i}[\${j}]"
|
来输出其中一个元素。
要输出整个矩阵A, 则可以
1
2
3
|
for (( line = 1; line <= i; line++ )); do
eval "echo \${row_A${line}[@]}"
done
|
这样就解决了 bash 里没有二维数组的问题。
解决代码重复的问题
在这个方案中，输入矩阵A中的每一个零元素都要向四个方向进行查找遍历，直至撞墙或到达边界。对于这种重复性的工作，如果使用 $for$ 循环会使代码臃肿，不好修改。
这里我们采用定义函数的方法，将这个过程独立出来，单独编写，避免代码的重复，同时有问题的时候便于修改。
因此我们定义了函数 find_shortest()
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
function find_shortest(){
# 这里全部定义为局部变量，避免混乱
local li_input=$1
local lj_input=$2
local way=$3
local best_time=-1
local ttime=0
local d=0
local cell=0
# 转换为 0-based 下标, (用python习惯了)
local li0=$(( li_input - 1 ))
local lj0=$(( lj_input - 1 ))
if [ ${way} -eq 0 ]; then
# 向右遍历：列从 lj0+1 到 j-1
for (( col = lj0 + 1; col < j; col++ )); do
eval "cell=\${row_A$(( li0 + 1 ))[${col}]}"
# cell值只有在大于0才额外操作, 故用线性的多个if(而不是if-elif的多分枝)
if [ -z "${cell}" ]; then
continue
fi
if [ "${cell}" -eq -1 ]; then
break
fi
if [ "${cell}" -eq 0 ]; then
continue
fi
d=$(( col - lj0 ))
# 到达时间公式：T = d * s + (d*(d-1))/2，其中 s 为光源的初始速度
ttime=$(( d * cell + (d * (d - 1) / 2) ))
if [ ${best_time} -eq -1 ] || [ ${ttime} -lt ${best_time} ]; then
best_time=${ttime}
fi
done
elif [ ${way} -eq 2 ]; then
# 向左遍历
for (( col = lj0 - 1; col >= 0; col-- )); do
eval "cell=\${row_A$(( li0 + 1 ))[${col}]}"
if [ -z "${cell}" ]; then
continue
fi
if [ "${cell}" -eq -1 ]; then
break
fi
if [ "${cell}" -eq 0 ]; then
continue
fi
d=$(( lj0 - col ))
ttime=$(( d * cell + (d * (d - 1) / 2) ))
if [ ${best_time} -eq -1 ] || [ ${ttime} -lt ${best_time} ]; then
best_time=${ttime}
fi
done
elif [ ${way} -eq 1 ]; then
# 向上遍历
for (( row = li0 - 1; row >= 0; row-- )); do
eval "cell=\${row_A$(( row + 1 ))[${lj0}]}"
if [ -z "${cell}" ]; then
continue
fi
if [ "${cell}" -eq -1 ]; then
break
fi
if [ "${cell}" -eq 0 ]; then
continue
fi
d=$(( li0 - row ))
ttime=$(( d * cell + (d * (d - 1) / 2) ))
if [ ${best_time} -eq -1 ] || [ ${ttime} -lt ${best_time} ]; then
best_time=${ttime}
fi
done
else
# 向下遍历
for (( row = li0 + 1; row < i; row++ )); do
eval "cell=\${row_A$(( row + 1 ))[${lj0}]}"
if [ -z "${cell}" ]; then
continue
fi
if [ "${cell}" -eq -1 ]; then
break
fi
if [ "${cell}" -eq 0 ]; then
continue
fi
d=$(( row - li0 ))
ttime=$(( d * cell + (d * (d - 1) / 2) ))
if [ ${best_time} -eq -1 ] || [ ${ttime} -lt ${best_time} ]; then
best_time=${ttime}
fi
done
fi
echo ${best_time}
}
|
上面这个函数也是这个算法的精华部分。
思路二：Dijkstra算法
特例下的分析
之前有提到，这个题目正向做确实不太好想，而反向查找的思路是容易想到，并且实现起来也是简单的。
但方法一反向查找光源的算法，在某些情况下效率并不高，特别是当网格较大，但光源较少时，如下图：
上图是一个 $8 \times 12$ 的网格，大部分网格都是 $0$，只有中间的三个网格是光源。
如果按照反向查找光源的算法，除光源外的每一个网格都要遍历一次，一共有 $8 \times 12-3 =93$ 个格子。而每个格子又要向四个方向遍历，平均每个各自还要遍历其他 $(8-1)+(12-1) = 77$ 个格子，这样实际遍历了格子 $93 \times 77 = 7623$ 次。这个数目都远远超过了网格的数量。
这时候反向查找光源算法就展现了它的缺点：在网格多，光源少的情况下会对许多光源不可达的网格进行遍历，但这其实是不必要的，会大大增加程序的运算量与运行时间。如果我们选择从正向传播的话，从光源本身出发向四周遍历，光源传播不到的点自然就是不可达的点，该点就标记为 $-1$ 。相比思路一的反向查找，这样的正向查找在网格大，光源少的情况，效率应该是更高的。
Dijkstra算法
上个世纪50年代，荷兰科学家迪杰斯特拉（Dijkstra）在咖啡馆喝咖啡时，无意间想出了有向带权图中寻找最短路径的问题。由于该算法对编程界的突出贡献，Dijkstra获得了1972年的图灵奖。
在一个有向且带权的图中，怎么找到一点到其他各点的最短路径呢？这正是 Dijkstra 算法所要解决的问题。
该算法的核心思路是从起点开始，每次选择“当前到起点距离最小”的未处理节点，更新其邻接点的最短路径，直到所有节点都被处理。
-
- 初始化所有点的距离为 ∞，起点距离为 0
-
- 把所有点放入一个未处理的集合
-
- 当集合非空时：
- a. 从集合中取出距离最小的点 u
- b. 对 u 的每个邻居 v：
如果通过 u 到 v 更短，则更新 v 的距离
- c. 把 u 标记为已处理（从集合中移除）
例如，对于一个有向带权图，利用Dijkstra算法的流程如下：
算法应用
在知道了Dijkstra算法后，我们就可以将它应用到正向传播的方案中。
我们选择用关联数组来保存一个网格的位置(x,y)，传播方向(d)，以及到达的最短时间(t)。
即 declare -A best 这里 best 的键为 "x,y,d" 。通过光源传播到网格，不断更新网格的到达最短时间，最后得到的就是所有光源到达该网格的最短时间，光源不可达的网格就为 $-1$ 。
这个算法的程序流程图如下：
插入图片
实现难点及解决方案
定义无穷大量
在Dijkstra算法的具体实现中，是要使用无穷大来表示暂时不可达的。在 Python 里，无穷大常量可以用 float('inf') 表示。但在 bash 里没有这么高级的语法。
因此我们定义了一个尽可能大的量 INF=1000000000 。这个数字已经足够大了，一般来说输入的数字应该是不会太大的，因此这不失为一个解决方案。
实现动态更新最短时间
正向传播的特点就是要从每个光源网格出发，向四个方向传播光线，光线沿途的格子的最短时间。
代码实现如下（变量的定义详见附件中的代码）：
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
# 将光源位置的 ans 置为 0，并向四个方向生成初始状态
for ((i=0; i<m; i++)); do
for ((j=0; j<n; j++)); do
key="$i,$j"
cell=${grid["$key"]}
if (( cell > 0 )); then
# 光源位置到达时间固定为 0
ans["$key"]=0
v=$cell
# 对四个方向
for d in {0..3}; do
ni=$((i + dx[d]))
nj=$((j + dy[d]))
# 判断邻居是否在边界并且不为障碍
if (( ni < 0 || ni >= m || nj < 0 || nj >= n )); then
continue
fi
nkey="$ni,$nj"
if [[ "${grid["$nkey"]}" == "-1" ]]; then
continue
fi
# 到达第一个邻居的累计时间为 v，下一步耗时为 v+1
t_new=$v
s_new=$((v + 1))
state="$ni,$nj,$t_new,$s_new,$d"
key_state="$ni,$nj,$d"
best["$key_state"]=$t_new
states+=("$state")
# 更新 ans：取更小的累计时间
if (( t_new < ans["$nkey"] )); then
ans["$nkey"]=$t_new
fi
done
fi
done
done
# Dijkstra 过程：每次在 states 数组中选择 t 最小的状态扩展
while ((${#states[@]} > 0)); do
# 找到数组中 t 最小的状态
min_index=0
IFS=',' read x_min y_min t_min s_min d_min <<< "${states[0]}"
for idx in "${!states[@]}"; do
IFS=',' read x y t s d <<< "${states[$idx]}"
if (( t < t_min )); then
min_index=$idx
x_min=$x
y_min=$y
t_min=$t
s_min=$s
d_min=$d
fi
done
# 取出最小状态并删除
state="${states[$min_index]}"
unset 'states[min_index]'
# 重新构造 states 数组（去除中间空位置）
states=("${states[@]}")
IFS=',' read x y t s d <<< "$state"
# 继续沿 d 方向扩展
nx=$((x + dx[d]))
ny=$((y + dy[d]))
# 检查边界
if (( nx < 0 || nx >= m || ny < 0 || ny >= n )); then
continue
fi
nkey="$nx,$ny"
# 遇到障碍停止
if [[ "${grid["$nkey"]}" == "-1" ]]; then
continue
fi
new_t=$((t + s))
new_s=$((s + 1))
state_key="$nx,$ny,$d"
# 更新状态：如果未记录或更优，则更新
prev=${best["$state_key"]}
if [[ -z "$prev" || $new_t -lt $prev ]]; then
best["$state_key"]=$new_t
new_state="$nx,$ny,$new_t,$new_s,$d"
states+=("$new_state")
# 更新 ans 记录，取最小累计时间
if (( new_t < ans["$nkey"] )); then
ans["$nkey"]=$new_t
fi
fi
done
|
上面这部分是Dijkstra算法的精髓所在。
方法总结与讨论
我们组用了两个方案来完成这个题目。两个方案都有各自的优缺点及适应情景。
第一个方案就是反向查找光源的算法，光源的正向传播到一个零网格，可以反向看作这个零网格沿着传播方向的反方向查找光源。每个零网格有四个方向，只要向四个方向查找光源，取到达时间的最小值即是光线传播到该位置的最短时间。这个方案的优点是，容易想到且代码好写，没有用到复杂的算法，在光源较多时，反向查找光源的方案是最快的。但当输入的网格数变多，但光源网格很少的情况下，反向查找光源的方案会浪费在遍历很多其实是光线不可达的网格，而且每个网格还是遍历它的四个方向，这样效率就很低下。
第二个方案，也就是Dijkstra算法就适合于网格多、光源少的情况。我们只需要关注光源网格，从光源网格的四个方向出发，更新沿途经过网格的最短时间。这个方案虽然是正向的，但在具体实现上比较复杂，如这里我们就用到Dijkstra算法。但它的优点就是效率高，减少了许多无用的遍历。不过当网格数较少，但光源较多时，这个算法遍历的光源数目就多，这时候程序的运行效率是比不上方案一的。
项目收获与感悟
在参与本项目的过程中，我们实战写 bash 脚本，期间遇到了许多问题。如代码运行报错，陷入死循环，不会处理数据的输入等。在这些问题的驱使下，我们又再次翻开课本，复习学过的 LinuxShell 知识点。在这个过程中，进一步巩固了我们的 Linux 操作与应用技能。我们思考问题的解决方案，我们不仅只满足于反向查找光源的简单算法，还了解、学习并应用了Dijkstra算法。在学习算法的过程中，如同开启了一门新的课程，尝试去学习图论基础，去理解什么是有向图，去掌握大名鼎鼎的Dijkstra算法。这同时又增强了我们的编程能力和学习算法的信心。在查找资料的时候，我们阅读各大论坛的帖子、博客，观看视频网站的教学视频，这又增强了我们的资料检索能力。
编程的过程不是一帆风顺的，需要的是不断地调试与修改。编程圈一直流传着一句话：“到现在为止，所有的代码，所有的算法，都是人写出来的，别人能想到的，你也一定可以！”虽然以后生信专业用 bash 来编程的情况会很少，大多用 Python 和 R 等语言，但所有编程语言的本质无非只是我们思想表达的一个工具。我们不要过于在意编程语言的语法，重要的是，我们也没有解决问题的思路，有没有失败后再来的决心。
参考文献
[1] 蓝不过海.图-最短路径-Dijkstra(迪杰斯特拉)算法.哔哩哔哩.https://www.bilibili.com/video/BV1uT4y1p7Jy/
[2]