如何在迷宫中找到最短路径？

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 * m 矩阵，尽管仅 4 * 4 的情况就足够了。并且我想知道起点和终点是否可以位于顶点以外的任意位置，尽管顶点的情况已经足够了。

- kmee

---

我不确定这是一个编程问题 - 在你开始考虑如何编写代码之前，你需要先有搜索算法。 - stas g

我不确定矩阵是表示这个问题的适当数据结构。图表会更好。然后，您将面临一个ILP / QP问题，其中您的目标是找到两点之间距离相等的每个顶点之间的最短距离。 - alexwhitworth

这不是一个只有一个正确答案的问题。有很多方法可以找到路径。请查看：https://qiao.github.io/PathFinding.js/visual/ 您需要决定哪种方法最适合您的数据。 - MrFlick

我觉得你可能在寻找Dijkstra算法的实现。虽然我从未见过那些图形的输出结果像那样。 - erasmortg

@stasg，有一个专门针对编程问题中使用哪种算法的高容量算法标签。算法问题不一定是离题的。我也不明白为什么会有“过于宽泛”的关闭投票——这很可能可以在5行或更少的代码中使用igraph实现... - josliber

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

- josliber

---

感谢您的友善回答。根据您的建议，我想问一下是否有可能将代码操纵成形如“f=function(m){.....}”的代码，其中m是给定的迷宫矩阵，以便在给定任意4x4大小的矩阵m时，函数f会给出结果作为向量。此外，我想问一下是否有可能不使用任何包来使用代码，以便我可以完成一个自给自足的代码，不需要任何包的帮助。 - kmee

@kmee 你可以通过在我的所有代码前添加f <- function(m) {，并在后面添加}来获取你的函数。至于你的第二个问题，当然你可以实现一个最短路径算法而不使用库（谷歌“Dijkstra算法”），但我不会在这里做这件事，因为这实际上是重新发明轮子。请注意，如果您对要使用或不能使用的软件包有要求，这些要求应该在问题中提出，而不应该作为事后提及。 - josliber

谢谢您的回答。我感到在发布问题之前必须考虑所有因素非常困难，可能是由于我经验不足。我会记住这点。而且我认为在发布问题之前应该花些时间，以免遗漏任何必要的条件。我可以再次发布有关此问题的问题并添加条件吗？谢谢。 - kmee

@kmee，此时您确实面临一个新的编码问题——您想要实现一种最短路径算法，而不是使用库中的算法。请注意，仅仅向他人询问是否为您实现此算法可能是一个过于宽泛的问题，并且很可能会被投票降低和关闭。最好尝试自己实现一种最短路径算法，如果在实现过程中遇到问题，请发帖提出问题。 - josliber

好的，我会自己尝试。但是我现在感觉R中的一切都很模糊，对几乎所有示例都不知所措，就像一个学生第一次在大学学习数学分析时感到困扰一样。这只是一个幼稚的抱怨，请忽略它。谢谢。 - kmee

Answer 2

我可能会使用gdistance包中的函数，另一个场景下展示了这些函数的使用方法，详见此处：

library(gdistance) ## A package to "calculate distances and routes on geographic grids"

## Convert sample matrix to a spatial raster
m = matrix(c(2, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 3), nrow=4)
R <- raster(m)

## Convert start & end points to SpatialPoints objects
startPt <- SpatialPoints(xyFromCell(R, Which(R==2, cells=TRUE)))
endPt   <- SpatialPoints(xyFromCell(R, Which(R==3, cells=TRUE)))

## Find the shortest path between them
## (Note: gdistance requires that you 1st prepare a sparse "transition matrix"
##  whose values give the "conductance" of movement between pairs of cells)
tr1 <- transition(R, transitionFunction=mean, directions=4)
SPath <- shortestPath(tr1, startPt, endPt, output="SpatialLines")

## Extract your direction codes from the steps taken in getting from 
## one point to the other. 
## (Obfuscated, but it works. Use some other method if you prefer.)
steps <- sign(diff(coordinates(SPath)[[1]][[1]]))
(t(-steps)+c(2,3))[t(steps!=0)]
## [1] 4 1 4 4 1 1

## Graphical check that this works
plot(R>0)
plot(rBind(startPt, endPt), col=c("yellow", "orange"), pch=16, cex=2, add=TRUE)
plot(SPath, col="red", lwd=2, add=TRUE)

- Josh O'Brien

Answer 3

一种可能的方法是建立一个矩阵，在目标位置上赋值1，在每个方格的曼哈顿距离从目标位置开始递减0.9，障碍物的值为零，起点任意。

定义这样一个矩阵后，最短路径是通过迭代地去到增值最大的相邻方格来获得的。

例如，这种方法在M. Sugiyama的书籍“统计强化学习”第一章中有描述。

因此，您的矩阵可能看起来像这样：

     [,1]  [,2]  [,3] [,4]
[1,] 0.53  0.00  0.0  0.00
[2,] 0.59  0.66  0.0  0.81
[3,] 0.00  0.73  0.0  0.00
[4,] 0.73  0.81  0.9  1.00

算法如下：

• 选择一个非零值的起始方块。
• 移动到距离你最近的方块中值最高的那一个方块。
• 重复上一步，直到到达数值为1的方块。

请注意，数值[2, 4]实际上是不可访问的，因此应该将其排除为可能的起始点。目的地不必在角落处。

- RHertel

---

算法的第二步是“移动到距离您一步的那些方格中价值最高的方格。”当面临相同价值的相邻单元格时，您如何进行选择？ - Robert Hijmans

@RobertH 在这种情况下没有必要进行选择，只要选择一个任意的，只要它是最高值即可。如果两个单元格具有相同的值，则结果路径的长度将相同（例如，先向左转再向上，与先向上移动再向左转不同）。 - RHertel