r - 如何在迷宫中找到最短路线？

Question

当给定一个迷宫作为矩阵时，我想编写一个给出最短路线的代码。

在这种情况下，这个迷宫的矩阵表示如下。

## [,1] [,2] [,3] [,4]
## [1,] 2 0 0 0
## [2,] 1 1 0 1
## [3,] 0 1 0 0
## [4,] 1 1 1 3
 , where  0 denotes inaccessible points, 1 denotes accessible points.
          2 denotes the starting point, and 3 denotes the destination.

并且，期望的结果是这样的:c(4,1,4,4,1,1)，其中 1 表示东，2 表示北，3 表示西，4 表示南.

我猜一个可能的代码可能是一个函数，当它被赋予迷宫的矩阵表示时，将最短路径作为向量给出。

除了这种情况，我想知道是否可以将覆盖范围扩展到一般情况，尽管这似乎是多余的。 我想知道是否可以制作一个理想的代码，以便它覆盖任意 n x m 大小的矩阵，尽管只有 4 x 4 的情况就足够了。 我想知道起点和终点是否可以位于顶点以外的任意点，尽管顶点情况就足够了。

Answer 1

您可以构建一个图表来表示矩阵中各位置之间的有效移动:

# Construct nodes and edges from matrix
(nodes <- which(m == 1 | m == 2 | m == 3, arr.ind=TRUE))
#       row col
#  [1,]   1   1
#  [2,]   2   1
#  [3,]   4   1
#  [4,]   2   2
#  [5,]   3   2
#  [6,]   4   2
#  [7,]   4   3
#  [8,]   2   4
#  [9,]   4   4
edges <- which(outer(seq_len(nrow(nodes)),seq_len(nrow(nodes)), function(x, y) abs(nodes[x,"row"] - nodes[y,"row"]) + abs(nodes[x,"col"] - nodes[y,"col"]) == 1), arr.ind=T)
(edges <- edges[edges[,"col"] > edges[,"row"],])
#      row col
# [1,]   1   2
# [2,]   2   4
# [3,]   4   5
# [4,]   3   6
# [5,]   5   6
# [6,]   6   7
# [7,]   7   9

library(igraph)
g <- graph.data.frame(edges, directed=FALSE, vertices=seq_len(nrow(nodes)))

然后你可以解决指定起点和终点之间的最短路径问题:

start.pos <- which(m == 2, arr.ind=TRUE)
start.node <- which(paste(nodes[,"row"], nodes[,"col"]) == paste(start.pos[,"row"], start.pos[,"col"]))
end.pos <- which(m == 3, arr.ind=TRUE)
end.node <- which(paste(nodes[,"row"], nodes[,"col"]) == paste(end.pos[,"row"], end.pos[,"col"]))
(sp <- nodes[get.shortest.paths(g, start.node, end.node)$vpath[[1]],])
#      row col
# [1,]   1   1
# [2,]   2   1
# [3,]   2   2
# [4,]   3   2
# [5,]   4   2
# [6,]   4   3
# [7,]   4   4

最后，您可以通过对最终选定节点集的简单操作来确定方向(1:东；2:北；3:西；4:南):

dx <- diff(sp[,"col"])
dy <- -diff(sp[,"row"])
(dirs <- ifelse(dx == 1, 1, ifelse(dy == 1, 2, ifelse(dx == -1, 3, 4))))
# [1] 4 1 4 4 1 1

此代码适用于任意大小的输入矩阵。

数据:

(m <- matrix(c(2, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 3), nrow=4))
#      [,1] [,2] [,3] [,4]
# [1,]    2    0    0    0
# [2,]    1    1    0    1
# [3,]    0    1    0    0
# [4,]    1    1    1    3