如何在R中找到矩阵/网络/图的所有可能的“连续”路径

Question

我有兴趣确定R中NxN矩阵的所有可能的“连续”路径并返回其结果。 “连续”是指我们可以旅行而不会举起您的铅笔/手指。也就是说，我们可以向上，向下，向左，向右或对角线移动。

为具体起见，我们使用3x3矩阵示例：

mat_3x3 <- matrix(LETTERS[1:9], ncol = 3, byrow = TRUE)
mat_3x3
#      [,1] [,2] [,3]
# [1,] "A"  "B"  "C" 
# [2,] "D"  "E"  "F" 
# [3,] "G"  "H"  "I" 

这意味着我们具有以下有效和无效路径：

一些注意事项：

• 开始位置不必是位置A（1、1）。
• 我们不能多次“双击”或触摸同一单元格。
• 短路径是可能的（例如A -> B -> C是有效路径；同样，A -> E -> I）-也就是说，我们不需要穿过所有节点。

[如果有一个方便使用的软件包或概念，请提出建议（我见过的大多数图形遍历软件包都比“矩阵”更“图形”）。我想动态编程或递归可能在这里有用，但是我不确定如何开始。

---

我相信，对于路径为15的一个像元，以下解决方案的答案是2X2：60； 15 * 4 = 60：

但是，对于3x3、4x4，案例……情况迅速升级，不再只是角落，增加了“中心”正方形，等等...

---

如果我们将这个问题更多地看成是图形或网络，那么对于3X3情况，我们有以下内容：

为什么？我对这个问题真的很感兴趣，并觉得很有趣。我想了解如何在R中进行编程，但是如果存在其他答案，我会考虑其他答案（然后将其转换为R）。它以思考“游戏”的思想实验开始，您可以在触摸屏上滑动手指以从字符串中创建单词。而不是最低成本，我们想最大化分数-使用Z比E中的Scrabble得分更高，等等。但是我想这在社交网络，图论，交通运输中有有趣的应用优化和其他领域。

Answer 1

[不确定这对于较大序列的缩放程度如何，但是对于3x3，它运行得相当快。请注意，这仅定义了使用所有九个字母的序列（784个序列）。但是，该函数仍然可以验证任何序列，并且任何可能的较短序列将是这些结果的子字符串。我没有验证所有结果，但是我确实进行了抽查。

library(gtools)

# convert matrix to numbers to reference by position
m <- matrix(seq_along(mat_3x3), ncol = ncol(mat_3x3))

# create blank matrix that is used to see if it is a valid move
mLength <- length(m)
mValid <- matrix(rep(FALSE, mLength ^ 2), ncol = mLength)

# create index to generate validity matrix
xIndex <- seq_len(ncol(m))
yIndex <- seq_len(nrow(m))

# wrap with NA to prevent out of bounds
mBounds <- rbind(NA, cbind(NA, m, NA), NA)

# set validity matrix TRUE if returns a value that is not NA
mValid[cbind(as.vector(mBounds[yIndex + 1, xIndex + 2]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex + 2, xIndex + 2]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex + 2, xIndex + 1]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex + 2, xIndex    ]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex + 1, xIndex    ]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex    , xIndex    ]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex    , xIndex + 1]), seq_len(mLength))] <- TRUE
mValid[cbind(as.vector(mBounds[yIndex    , xIndex + 2]), seq_len(mLength))] <- TRUE

# define function to check if provided sequence is valid
validate <- function(x) {
  s <- seq_along(x)[-1]
  x[all(mValid[cbind(x[s], x[s - 1])])]
}

# generate all permutations
p1 <- permutations(mLength, mLength)
p2 <- apply(p1, 1, validate)
p2 <- p2[lengths(p2) > 0]

# one result
mat_3x3[p2[[1]]]

[1] "A" "D" "G" "E" "B" "C" "F" "H" "I"