クソコード製造機

数理最適化とかPythonとか

線形順序付け問題と貪欲法

組合せ最適化

線形順序付け問題は、行列 A \in \mathbb{R}^{n \times n}_{\geq 0}が与えられたときに、置換 \sigma \in S_nについて、目的関数


\displaystyle f(\sigma) = \sum_{i < j} A_{\sigma(i)\sigma(j)}
を最大化する問題として表される。もし i > jについて、 A_{\sigma(i)\sigma(j)} = 0となるような \sigmaが取れる場合は、DAG上のトポロジカルソートになる。

線形順序付け問題はNP困難であるため、厳密解を求めたければ、整数計画として定式化してソルバーに投げることになるだろう。

厳密解がいらない場合では、ヒューリスティクスも数多く提案されている。ここでは単純な解法として、貪欲法に基づく1/2-近似アルゴリズムを述べておく。

  1. S = \{1, 2, ..., n\}, \sigma(i) = 0\, (i = 1, 2, ..., n)と初期化しておく。
  2. i = 1, 2, ..., nに対して以下を繰り返す。
    1. \sum_{j \in S \setminus \{k\}} \left( A_{kj} - A_{jk} \right)が最大となるような kをとる。
    2. \sigma(i) = k, S = S \setminus \{k\}とする。
  3. \sigmaを出力して終了。

各ステップにおいて、 \sum_{j \in S \setminus \{k\}} \left( A_{kj} - A_{jk} \right) \geq 0なる kが少なくとも1つは存在することが背理法によって示せる。(左辺を k \in Sに渡って和を取ると0になる。)

よって、任意の iについて、


\displaystyle \sum_{j = i + 1}^{n} A_{\sigma(i)\sigma(j)} \geq \sum_{j = i + 1}^{n} A_{\sigma(j)\sigma(i)}
が成立し、 iについて両辺和をとると、

\displaystyle f(\sigma) = \sum_{i < j} A_{\sigma(i)\sigma(j)} \geq \sum_{j < i} A_{\sigma(i)\sigma(j)}
が成立することがわかる。

明らかな最適値の上界として、


\displaystyle \sum_{i \neq j} A_{ij} = \sum_{i < j} A_{\sigma(i)\sigma(j)} + \sum_{j < i} A_{\sigma(i)\sigma(j)}
が与えられることから、1/2-近似アルゴリズムであることがわかる。

計算量は \mathcal{O}(n^2)になる。

より精度がよいアルゴリズムやヒューリスティクスなどはちゃんとしたサーベイを見てほしい。