在矩阵中添加数字组合

Question

我发现这个 link 向您展示了如何使用随机数制作矩阵：https://www.tutorialspoint.com/how-to-create-a-matrix-with-random-values-in-r

  #random symmetric matrix with diagnoal elements as 0
 A <- matrix(runif(16), 4, 4)
A1 = A %*% t(A)

out_1 = A1 - diag(diag(A1))

         [,1]     [,2]     [,3]     [,4]
[1,]     0.00 20371.54 19136.91 18380.49
[2,] 20371.54     0.00 19392.13 19476.78
[3,] 19136.91 19392.13     0.00 16651.73
[4,] 18380.49 19476.78 16651.73     0.00

假设每个索引对应这个矩阵中的一个城市(out_1) - 有4个城市。
任意（行，列）组合对应两个城市之间的距离（例如[2][3]对应城市2和城市3之间的距离）
从逻辑上讲，同两个城市之间的距离是相同的，例如.. [2] [3] = [3] [2]
从逻辑上讲，一个城市与其自身的距离为0，例如[2] [2] = 0

使用这个矩阵 (out_1)，我想从这个矩阵计算所有具有以下结构的“路径”：

路径必须从同一个城市开始和结束，除第一个城市外，其他城市不能重复。

例如，最终目标看起来像这样：

- Path 1 : [1] [2] , [2] [3], [3] [4], [4] [1] = 20371.54 + 19392.13 + 16651.73 + 18380.49 = 74795.89  
- Path 2 : [2] [4] , [4] [3], [3] [1], [1] [2] = 19476.78 + 16651.73 + 19136.91 + 20371.54 =   75636.96
- ....
- Path n: [3] [4] , [4] [1], [1] [2], [2] [3] =  16651.73 + 18380.49 + 20371.54 + 19392.13 =   74795.89

我试图在 R 中找到一些库来执行此操作（注意：我认为我正在尝试做的称为“图的哈密尔顿循环”）：https://www.rdocumentation.org/packages/adagio/versions/0.8.4/topics/hamiltonian

但这没有用：

    c = c(out_1)
 hamiltonian(c, cycle = TRUE)

    Error in graph_vect2list(edges) : 
      Argument 'edges' is not a correct edge list.

如何获得所有此类“路径”的列表，显示城市的顺序和每条路径的总距离？

谢谢！

Answer 1

在 n 的完整图上有 factorial(n-1) 个哈密顿循环——如果排除反向循环，则数量减半，例如，如果只保留 (123) 和 (132) 中的一个) 当 n = 3。在某些情况下，从 A 到 B 的距离与从 B 到 A 的距离不同，因此包含反向循环可能很有用。

这是一种计算所有 factorial(n-1) 周期的方法，它依赖包 gtools 中的函数 permutations 来执行“path-finding”。 gtools 有 several 个替代品，您可以自由使用。

mkX <- function(n) {
    X <- abs(crossprod(matrix(rnorm(n * n), n, n)))
    diag(X) <- 0
    X
}

roundtrips <- function(X) {
    n <- nrow(X)
    if (n < 2L) {
        trips <- matrix(integer(0L), 0L, 0L)
        distances <- double(0L)
    } else {
        trips <- cbind(1L, gtools::permutations(n - 1L, n - 1L, seq.int(2L, n)))
        distances <- apply(trips, 1L, function(i) sum(X[cbind(i, c(i[-1L], 1L))]))
    }
    list(X = X, trips = trips, distances = distances)
}

set.seed(1L)
X <- mkX(4L)
roundtrips(X)

$X
          [,1]      [,2]     [,3]     [,4]
[1,] 0.0000000 0.4134306 1.058161 1.029243
[2,] 0.4134306 0.0000000 1.465003 2.127536
[3,] 1.0581611 1.4650029 0.000000 2.001777
[4,] 1.0292425 2.1275361 2.001777 0.000000

$trips
     [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    2    4    3
[3,]    1    3    2    4
[4,]    1    3    4    2
[5,]    1    4    2    3
[6,]    1    4    3    2

$distances
[1] 4.909453 5.600905 5.679943 5.600905 5.679943 4.909453

这里，X是一个距离矩阵；它不一定是对称的，但在这个例子中是对称的。 trips 是一个整数矩阵，其行定义了图的不同哈密顿循环。 distances 是一个双向量，列出了这些循环中经过的距离。当 X 是对称的时，距离成对对应于循环及其反转。

慎重选择n：factorial(n-1)长得很快。

在矩阵中添加数字组合

Adding Combinations of Numbers in a Matrix

r

matrix