重み付きマッチングで最適解
- 重み付きマッチングとは→こちら参照
- ついでにハンガリー法の説明にもなっている
- RでHungarian methodは、パッケージ clueの関数 solve_LSAP()
- 昨日の記事のlpSolveパッケージのlp.assign()関数も同じことだけれど、このハンガリー法はこの教科書のp271に「現在知られている最速」とあるだけに、すごく、速い！
- 作者: B.コルテ,J.フィーゲン,浅野孝夫,平田富夫,小野孝男,浅野泰仁
- 出版社/メーカー: シュプリンガー・フェアラーク東京
- 発売日: 2005/11/15
- メディア: 大型本
- クリック: 20回
- この商品を含むブログ (15件) を見る
k<-100 library(lpSolve) library(clue) # 適当に行列を作ってやる M<-matrix(abs(rnorm(k^2)),k,k) # "max":最大になるように割り付け out2<-lp.assign(M,direction="max") out<-as.vector(solve_LSAP(M,maximum=TRUE)) # 結果を出力 print(out) out2 # ここから、「最大値」を計算してみる VAL2<-sum(out2$solution*M) VAL<-sum(diag(M[1:k,out])) # print(out)と同じ値 print(VAL) print(VAL2)
