如何在迷宫中获得最短路径? [英] How do I get the shortest route in a labyrinth?
问题描述
我想编写一个以迷宫为矩阵时给出最短路径的代码。
I want to make a code giving the shortest route when given a labyrinth as a matrix.
在这种情况下,此迷宫的矩阵表示如下。
In this case, the matrix representation of this labyrinth is as follows.
## [,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表示南方。
And, the desired result is this : c(4,1,4,4,1,1)
, where 1 denotes East, 2 denotes North, 3 denotes West, and 4 denotes South.
一个可能的代码可能是当给出迷宫的矩阵表示形式时以最短路径作为向量的函数。
I guess that one possible code might be a function giving the shortest route as a vector when it is given the matrix representation of a labyrinth.
除了这种情况,我想知道覆盖范围是否可以扩展到一般情况,尽管这似乎很多余。
我想知道是否可以制作一个理想的代码,使其覆盖任意n×m大小的矩阵,尽管4×4大小写就足够了。
我想知道起点和目的地是否可以位于顶点以外的任意点,尽管顶点的大小写就足够了。
In addition to this case, I want to know if the coverage could be extended to general cases, though it seems rather redundant. I would like to know whether a desirable code can be made so that it covers arbitrary n by m size matrix, although just 4 by 4 case suffices. And I wonder if the start point and the destination could be located at arbitrary points other than vertices, though vertices case is sufficient.
推荐答案
您可以构建一个图形来表示矩阵位置之间的有效移动:
You could construct a graph to represent the valid moves between positions in the matrix:
# 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)))
然后,您可以解决指定起点和终点之间的最短路径问题:
Then you could solve the shortest path problem between the specified start and end location:
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:向南)作为对所选最终节点集的简单操作:
Finally, you could determine the direction (1: east; 2: north; 3: west; 4: south) as a simple manipulation of the final set of nodes selected:
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
此代码适用于任意大小的输入矩阵。
This code will work for arbitrarily sized input matrices.
数据:
(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
这篇关于如何在迷宫中获得最短路径?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!