1

RでKnuthのアルゴリズムXのようなものを実装しようとしています.

問題: 実数値のエントリがコストを表す anxk 行列 A、n>=k があります。一般に、n と k はどちらもかなり小さくなります (n<10、k<5)。単一の行を 2 回使用できないという制約に従って、行列の総コストを最小化する列への行のマッピングを見つけたいと考えています。

これは、合理的なアプローチが次のように思われるという点で、アルゴリズム X に似ていると思います。

  1. A の列を選択し、その中で最小値を見つけます。
  2. その行とその列を削除します。これで、Asub が残ります。
  3. ステップ 1 に進み、ncol(Asub)=1 になるまで Asub と新しい列を選択して繰り返します。

しかし、セルレベルのコストの結果のツリーを格納する再帰的なデータ構造を R で作成する方法がわかりません。ここに私がこれまでに持っているものがあります.1つのブランチしか下らないため、最適な解決策が見つかりません.

# 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関数で再帰を処理する方法について、何か基本的なことが欠けていると確信しています。このアルゴリズムが実際に最適でない場合、この問題を解決する他の方法を聞いてうれしいです.

4

2 に答える 2