ryamadaのコンピュータ・数学メモ

2011-06-16

すべての場合

重み付き割り付けの話をしている(こちらやこちらやこちらやこちら)
最適解も求めたいが、「あらゆる割り付け」の場合について合算もしたい
今、割り付けをして、コスト行列の要素の和を最適にしたいとすると、割り付けの仕方ごとに決まる、要素の和は
$\sum_{i=1}^N p_{i,s_i}$ 、ただし、 $P=(p_{i,j}$ がコスト行列で、ある順列 $S=(s_1,s_2,...,s_N)$ についてのコストのこと
すべての順列について足し合わせると $\sum_{S \in \Omega} \sum_{i=1}^N p_{i,s_i}$ ]となるが、この式には $p_{i,j}$ が等回数登場する
$p_{i,j}$ の延べ数は $N! \times N$ であり、 $p_{i,j}$ の要素数は $N^2$ であるから
$\frac{N! \times N}{N^2}=(N-1)!$ が個々の要素の登場回数である
したがって、 $(N-1)!\times \sum_{i=1}^N \sum_{j=1}^N p_{i,j}$ が、全ての割り付けについてコストを足し合わせたものとなる

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)