Iterated greedyでグラフの彩色問題

Courseraで離散最適化を勉強していたら、フォーラムにIG(iterated greedy) というアルゴリズムが出てきたので紹介します。

元の論文はこちら。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.7721

グラフ彩色の練習問題で使ってみたところ、非決定性もなく、むつかしい操作もなく、そこそこの計算量でそれなりの解が得られました。メモリの使用量や計算時間も、エッジのソート分を見ておけばOKなので組込みなどの厳しい環境でも使えます。

グラフ彩色問題

https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
今回はエッジに対する色分け問題です。実装と評価が簡単なので、他の問題でもとりあえずやってみる価値はあると思います。

アルゴリズム

通常のgreedy algorithmは一回で近似解を求めに行きますが、IGではgreedy algorithmを繰り返すことでより良い近似解を求めます。

f:id:natsutan:20190821171450p:plain — graph

このグラフに対して、abc順にgreedy algorithmを使うと、a=1, b=1, c=2, d=2, e=3, f=4なり4色使う結果になります。次に、この色順でgreedyを適用します。順番がfecdabとなり、greedy algorithmでも2色の最適解を得ることができます。

本質的にはこれだけです。これでうまくいく理由は、一般的に制約プログラミングでは、制約の厳しい所から値を設定していくのが有効と言われています。一回目のgreedy algorithmで彩色した結果、彩色が厳しかったところから再度greedy algorithmを使うことで、うまく精度を上げています。これにヒューリスティックな方法を組み合わせることで、さらに良い解が見つかる可能性があります。

もっと厳密な話は上の論文を読んでみてください。