すべての場合
- 重み付き割り付けの話をしている(こちらやこちらやこちらやこちら)
- 最適解も求めたいが、「あらゆる割り付け」の場合について合算もしたい
- 今、割り付けをして、コスト行列の要素の和を最適にしたいとすると、割り付けの仕方ごとに決まる、要素の和は
、ただし、
がコスト行列で、ある順列
についてのコストのこと
- すべての順列について足し合わせると
]となるが、この式には
が等回数登場する
の延べ数は
であり、
の要素数は
であるから
が個々の要素の登場回数である
- したがって、
が、全ての割り付けについてコストを足し合わせたものとなる
N<-5 M<-matrix(log(runif(N^2)),N,N) library(gtools) pm<-permutations(N,N) a<-0 for(i in 1:length(pm[,1])){ for(j in 1:length(pm[i,])){ a<-a+M[j,pm[i,j]] } } a sum(M)*factorial(N-1)