r - 在 R 中实现算法 X

Question

我希望实现类似 Knuth's Algorithm X 的东西在 R 中。

问题:我有一个 n x k 矩阵 A，n>=k，其中实数值项表示成本。一般来说，n 和 k 都会非常小(n<10，k<5)。我想找到行到列的映射，使矩阵的总成本最小化，但要遵守任何一行都不能使用两次的约束。

我认为这有点像算法 X，因为合理的方法似乎是:

1. 在 A 中选择一列并找到其中的最小值。
2. 删除该行和该列。现在你只剩下 Asub。
3. 转到第 1 步并重复 Asub 和新的列选择，直到 ncol(Asub)=1。

但我无法弄清楚如何在 R 中创建一个递归数据结构来存储生成的单元级成本树。到目前为止，这是我所拥有的，它只在一个分支下，所以没有找到最佳解决方案。

# This version of the algorithm always selects the first column. We need to make it 
# traverse all branches.
algorithmX <- function(A) {
  for (c in 1:ncol(A)) {
    r <- which.min(A[,c])
    memory <- data.frame(LP_Number = colnames(A)[c], 
                         Visit_Number = rownames(A)[r], 
                         cost = as.numeric(A[r,c]))
    if (length(colnames(A))>1) {
      Ared <- A[-r, -c, drop=FALSE]
      return( rbind(memory, algorithmX(Ared)) )
    }
    else {
      return(memory)
    }
  }
}

foo <- c(8.95,3.81,1.42,1.86,4.32,7.16,12.86,7.59,5.47,2.12,
         0.52,3.19,13.97,8.79,6.52,3.37,0.91,2.03)
colnames(foo) <- paste0("col",c(1:3))
rownames(foo) <- paste0("row",c(1:6))
algorithmX(foo)

我确信我遗漏了一些关于如何在 R 函数中处理递归的基本知识。如果这个算法实际上不是最合适的，我也很高兴听到其他解决这个问题的方法。

Answer 1

您没有将 foo 设置为矩阵，因此您无法设置 colnames(foo) 或 rownames(foo)。假设这只是一个拼写错误，还有一个问题是您永远不会访问 c = 1 以外的任何内容，因为内部测试的两个分支都会返回一些内容。您可能希望在循环中收集结果，选择最好的一个，然后返回。

例如，

algorithmX <- function(A) {
  bestcost <- Inf
  save <- NULL
  for (c in 1:ncol(A)) {
    r <- which.min(A[,c])
    memory <- data.frame(LP_Number = colnames(A)[c], 
                         Visit_Number = rownames(A)[r], 
                         cost = as.numeric(A[r,c]))
    if (length(colnames(A))>1) {
      Ared <- A[-r, -c, drop=FALSE]
      memory <- rbind(memory, algorithmX(Ared)) 
    }
    if (sum(memory$cost) < bestcost) {
      bestcost <- sum(memory$cost)
      save <- memory
    }
  }
  return(save)
}