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

2011-06-12

重み付き割り当て問題から置換多面体へ

Permutohedron

書きかけ
昨日の記事で、「重み付き割り当て」を扱った。
置換のうちの最適解を求める問題
それに関連して、「置換多面体」
Wikiの記事
$k$ 次元立方格子がある。１辺が $1,2,...,t$ という
この立方格子の点の数は $t^k$ 個
では、1,2,...,kの順列が作る点(1,2,3,...,k),(2,1,3,...,k),...,(k,1,2,...,k-1),...,(k,k-1,k-2,...,3,2,1)はいくつあるか、というと $k!$ 個
順列 $S_j=(s_1,s_2,...,s_k);j=1,2,...,k!$ とする
では、この $k!$ 個の点は $S_j$ どのように並んでいるか？
一つのヒントは $\sum_{i=1}^k s_i=\frac{k(k+1)}{2}$ であること
これは「平面」の式なので、「平面上の点」であることがわかる
$k$ 次元正方格子の中の、ある平面が通過する点のうち、 $k!$ 個が $S_j$ となっている
もう一つのヒントは、「すぐ隣の点」がいくつあるかである
すぐ隣の点とは、 $k$ 個のうち２個を取り出して $i_1,i_2$ とすると、それを取り換えた $S=(s_1,s_2,...,s_i,...,s_j,...,s_k$ が $S=(s_1,s_2,...,s_j,...,s_i,...,s_k$ となったもの
このような隣の点は、 $\frac{k(k-1)}{2}$ 個ある
別のやり方もある、合い並んでいる２要素を取りかえる、 $S=(s_1,s_2,...,s_i,s_{i+1},...,s_k$ が $S=(s_1,s_2,...,s_{i+1},s_i,...,s_k$ 。これを隣とする方法もある
これを図にした様子はWiki記事で見られる。一番、イメージが湧きやすいのは、 $k=3$ の場合
関連記事はこちら