如何获得迷宫中最短的路线?

我想编写一个以迷宫为矩阵时给出最短路径的代码。

在这种情况下,该迷宫的矩阵表示如下。

## [,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大小即可。而且我想知道起点和目的地是否可以位于顶点以外的任意点,尽管顶点的大小就足够了。

回答:

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

# 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

以上是 如何获得迷宫中最短的路线? 的全部内容, 来源链接: utcz.com/qa/400175.html

回到顶部