組み合わせ最適化

読書

3-5章 (読み飛ばし...)

単体法・内点法・楕円体法とかその辺...、と言いつつ、内点法については記載がまったくないような気がする。


制約条件下で特定の値を最大化(あるいは最小化)するとき、制約条件のどれかがギリギリのところになるのを利用して、どの条件をギリギリにすればいいかを探索するのが単体法。探索なので、可能なパターンの数を全部調べるのと同じオーダー(指数)になるけど、平均的にはそんなに遅くないヒューリスティクスがあるよ、っていう感じの話。実際に手を動かしていないので良く分からない...。競技プログラミングだと単体法"でも"解ける問題くらいしか出ないという感触。単に自分が解けてない問題が単体法を要求しているかも知れないので、なんとも、だけど。


楕円体法は、解の存在領域を楕円体を使って制限していく方式らしい。楕円体のうち、解のある側を含む楕円体で、共通部分にして...、みたいな。最適解を求める話が、解の存在空間の話にすり変わっているような気がしてならないけれど、最終的な共通部分に対して何かするんだろうと思う。いずれにせよこれは実用的じゃないくらい重たい方法らしいので、実生活で必要になることはない理論のお話なので保留かなぁ...。


ここまでほとんど理解していないので、5章の整数性が追加されたより難しい問題についての議論はますます分からないのである...。単体法くらいは使えるようになれればいいんじゃないかなぁ、というのが3-5章を読んだ感想なので、いつかちゃんとやるという保留状態を継続。

6章(全点木)

クラスカルとプリムから。クラスカルは辺をコスト順にソートしてN点からなるN個のグループを一つにマージしていく感じ。プリムはある点から開始して、どんどん点を併合していく感じ。N個のグループの併合の過程にMFSETだかなんだかを使うので、アッカーマン関数の逆関数がどうたらという話が出てくるらしい。一方プリムはあるグループに入ってるかどうかを管理するだけなので、ノードの管理に関するデータ構造としては簡単なんだけど、関係するエッジの管理が面倒でPriorityQueueが必要になる。あと、若干重たい。コーディングとしては多分プリムの方が簡単なので、計算量に問題がないならプリムを使うといいんだろうなぁ、という感じ。(なぜかクラスカルを常に書くけど...。)

// クラスカル;
sort(edges);
for(Edge e : edges) {
  if( find(e.v1) != find(e.v2) ) {
    mincost += e.cost;
    merge(find(e.v1), find(e.v2));
  }
}
// プリム;
while( (e = pq.poll()) != null ) {
  if( !used[e.v2] ) {
    mincost += e.cost;
    used[e.v2] = true;
    for(Node n : nodes) { pq.add(edge(e.v2, n)); }
  }
}


プリムとクラスカルは無向グラフの話なので、有向グラフの場合には使えないらしい。最大重み有向森の求め方が非常に分かりにくく(意図的なのかどうかはさておき)書いてあるのだけれど、理解を超越した記述なので保留。問題に仕立て上げられそうな気もしない。


多分親が高々一つなので、入次数が1になるように(自分に入ってくる辺のうち最大重みのものを採用)すると、根があるか閉路(他の閉路とくっつくことはない)になるかなので、閉路をうまくカットしてやれば良さそうな気もする。これより良いケースってどうやって作るんだろう？