buq’s blog

覚えておきたいけど覚えておけなさそうなことを書きます?

最小費用ソート（ALDS1_6_D）の解法の正当性（メモ）

Minimum Cost Sort （最小費用ソート）という問題がある．

最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge

この問題を解くことができず，また正解コードをみてもその正当性がよくわからなかった． まじめに考えたら正当性の証明ができつつあるので，備忘のため記事にしておく． 頭が整理されていないところもあり， 細かい部分はしっかり書いていなかったり，記法が適当だったりという箇所もあります． 指摘・質問などを歓迎します．

なお，偉い人達がかいた正解コードは上記ページで🔍アイコンをクリックすると見ることができる． また AOJ の問題（の一部？）は

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

に解説があり，アルゴリズムはこちらでも 解説されている．

問題設定

最小費用ソート問題の設定は以下の通りである．オリジナルの問題と本質的には同じだが，説明を簡単にするために等価な別表現で書いている．

入力

n ：問題サイズ

0 \lt w_1 \lt w_2 \dots \lt w_n：非負な増加列

s \in S_n：置換（ S_n は n 次の対象群）

出力

互換 t = (a,b) の重みを W(t) = w_a + w_b と定義する． 置換 s を互換の積 t_1 t_2 \dots t_p, t_i = (a_i, b_i) に分解するとき， 分解の重みを \Sigma_i {w_{a_i}} + \Sigma_i {w_{b_i}} と定義する． s の互換の積での分解のうち，もっとも重みの小さいものの重みを求めよ．

解法

具体的な分解を与えるアルゴリズムを紹介する． 正当性の証明は次節で与える．

置換 s の軌道分解（1次以上の巡回置換での分解） s = c_1 c_2 \dots + c_C, c_j=(e_1^j, \dots, e_{D_j}^j) とその表現を考える． この分解では，任意の i \in [n ] が必ずいずれかの巡回置換の表現に登場する．

分解を適当に並べ替えて， c_1 が 1 に関するものであるようにしておく． また，ここで登場する各巡回置換 c = (e_1, e_2, \dots, e_D) は， e_1 が登場する要素のうち 最軽量のものであるものを選ぶ．つまり， e_1 = \min_{j = 1, \dots, D} e_j であるように巡回置換の表現を固定する． したがって特に e_1^1 = 1 である．

巡回置換 c = (e_1, e_2, \dots, e_D) を e_1, \dots , e_D のみを用いた互換の積に分解する場合， 最小重みの分解は (e_1, e_D) (e_1, e_{D-1}) \dots (e_1, e_2) である． （∵ このような分解の重みの式に w_{e_j}, j = 1, \dots, D が必ず1回は登場する． またこのような分解の長さが D-1以上であり，重みの式は要素を 2(D-1) 個以上含む足し算になる． したがって，最も軽く見積もっても分解の重みは (D-1)w_{e_1} + \Sigma_{j= 2, \dots, D}w_{e_j} であり， これは (e_1, e_D) (e_1, e_{D-1}) \dots (e_1, e_2) の重みと一致する．）

上記の分解を用いて（限られた操作のなかでの）巡回置換 c の重み W(c) を定義する． 軌道分解における異なる2つの巡回置換 c_1=(e_1^1, \dots, e_{D_1}^1), c_j=(e_1^j, \dots, e_{D_j}^j) の重みの和は

(D_1-1)w_{e_1^1} + \Sigma_{i= 2, \dots, D}w_{e_i^1} + (D_j-1)w_{e_1^j} + \Sigma_{i= 2, \dots, D}w_{e_i^j}

であり，したがってこの重みの互換による分解☆をもつ．一方， c_1 c_j (e_1^1, e_1^j) は巡回置換となるが，その重みは (D_1 + D_j-1)w_{e_1^1} + \Sigma_{i= 2, \dots, D}w_{e_i^1} + \Sigma_{i= 1, \dots, D}w_{e_i^j} である．したがって， c_1 c_j は重み

(D_1 + D_j)w_{e_1^1} + \Sigma_{i= 2, \dots, D}w_{e_i^1} + \Sigma_{i= 1, \dots, D}w_{e_i^j} + w_{e_1^j}

の互換による分解★をもつ． 分解☆と★の重みの差は (D_j+1) w_{e_1^1} - (D_j - 3 ) w_{e_1^j} である． したがって，これが正の場合分解は分解 ★ を採用すべきであり，そうでない場合は分解 ☆ を採用すべきである．この量を r_j, (j \neq 1) とする．

このような観察から，最適な分解を与えるアルゴリズムは次のものであると予測する．

単一のサイクル s^\prime =\Pi_{j:r_j > 0, j>1}(e_1^1, e_1^j) s の重み W(s^\prime) の 分解に対して，左から (\Pi_{j:r_j > 0, j>1})^{-1} をかけた分解を計算する．

これは頂点の数について線形時間で計算できる． とくに，最小の重みだけを計算したい場合は 「全てのサイクルについて r_jとサイクルの重みを計算する」だけで十分である．

正当性証明

この問題は計算量を度外視すれば最短路問題である．すなわち，最小費用ソートは S_n を頂点集合とし，互換でつながる頂点同士に互換の重みで重み付けした枝を張ったグラフ上での， s から 1 \in S_n への最短路を求める問題である．したがって，部分路が再び最短路になっている，という性質が証明に使えそうである．

主張1

s の互換による分解のうち， s = t_1 \dots t_p u_1 \dots u_q という形であり t_{j} \dots t_1 s の軌道の数が t_{j-1} \dots t_1 s の軌道の数より 1 小さく， u_{j} \dots u_1 t_p \dots t_1 s の軌道の数が u_{j-1} \dots u_1 t_p \dots t_1 s の 軌道の数より 1 大きいもののみを考える．この性質 ◆ を満たす互換による分解のうち最適な 分解は，アルゴリズムで求められるものである．

∵ 軌道の数を減らす互換を左からかけていくことは，軌道を統合していくことにほかならない． 2つの軌道を統合する場合，各々の最小の要素同士を交換して統合するのが最適である． これは，軌道の統合を木（全体では森）で表現したときの，ルートからの帰納法から従う．

また，軌道の統合においては 1 を含むサイクルと他のサイクルを統合していくのが最適である． （そうでないものを考えた場合，よりよい統合方法が構成できる．）（したがって，軌道の統合を 表現する森は最適に統合する場合は木になり，特にくし形（ 1 を含むサイクルと他のサイクルを統合するもの）になる）

くし形のうち，最適な統合の方法（の互換の積による表現）はアルゴリズムにあるよう \Pi_{j:r_j > 0, j>1}(e_1^1, e_1^j) であることは簡単に確認できる．

主張2

s の互換による分解のうち最適な分解は，上記アルゴリズムで求められるものである．

∵ 最適な互換による分解が主張1にある分解 s = t_1 \dots t_p u_1 \dots u_q が存在することを示せば十分である． そのためには，主張1の形でない最適な分解から矛盾を導くか，あるいは同じ重みの主張1の形の分解を構成すれば十分である．最適な分解を s = v_1 \dots v_V u_* t_1 \dots t_p u_1 \dots u_q と表す．ただし：

  • v_i ：適当な互換．
  • u_* v_V \dots v_1 s の軌道の数が v_V \dots v_1 s の軌道の数より 1 大きい
  • t_{j} \dots t_1 u_* v_V \dots v_1 s の軌道の数が t_{j-1} \dots t_1 u_* v_V \dots v_1 の軌道の数より 1 小さい
  • u_{j} \dots u_1 t_p \dots t_1 u_* v_V \dots v_1 s の軌道の数が u_{j-1} \dots u_1 t_p \dots t_1 u_* v_V \dots v_1 の軌道の数より 1 大きい

（分解の最後の互換は，軌道の数を増やすようなものでなければならないので，かならずこのように表すことができる．）ここでは特に q が最大であるようなものを採用する．

このとき， v_V \dots v_1 s = u_* t_1 \dots t_p u_1 \dots u_q は v_V \dots v_1 s の最適な分解であり， また u_* v_V \dots v_1 s = t_1 \dots t_p u_1 \dots u_q は u_* v_V \dots v_1 s の最適な分解である． u_* v_V \dots v_1 s の軌道は，もともと v_V \dots v_1 s で軌道であったものと，新しく出来た軌道（ちょうど2つ）に分類できる．新しい軌道が t_p \dots t_1 によって他と統合されないのであれば， s = v_1 \dots v_V t_1 \dots t_p u_* u_1 \dots u_q という分解が存在し， V > 0 であれば q の最大性に矛盾し， V= 0 であれば主張1の形式の最適な互換を構成できる．したがって

  • 新しく出来た軌道が 1 を含む
  • 新しく出来た軌道が 1 を含まない

の2通りの状況を考えればOKだが， u_* の後はくし形の統合と軌道ごとの分解が待っていることから， いずれの場合においても v_V \dots v_1 s = u_* t_1 \dots t_p u_1 \dots u_q が v_V \dots v_1 s の最適な分解でないことがわかり，仮定と矛盾．

ひとこと

途中で面倒になって適当な記事になってしまった．本人の備忘のための記事だけれど，人の役に少しでも立てば幸いです． 細かい部分は省略しているが，お絵かきをすると分かりやすい．（お絵かきをしてブログに貼るのはサボった．）

この問題を見てプログラミングコンテストの時間枠で（おおざっぱな証明付きで）正解にたどり着けるひとはそうそう居ないように思うのだけど，強い人はできちゃうんだろうか．