algorithm - 最先端のグラフ彩色メタヒューリスティック

Question

それぞれ 10 ～ 50 のエッジを持つ何千もの頂点を含むグラフの色付けの問題があります。多くのグラフ カラーリング ヒューリスティック (GA、タブー検索など) を調査してきましたが、それらを比較して、どれが自分に最も適しているかを判断するのは難しいと感じています。技術を推奨するため、またはこのドメインの現在の最先端のアルゴリズムについて私に知らせるために、大規模なグラフの色付けの経験がある人はいますか?

ありがとう。

Answer 1

Drools Plannerなどの最適化エンジンに実装し、そのベンチマークを実行して、どのメタヒューリスティックが最適に機能するかを判断します。

特に、純粋なグラフ彩色の問題がない場合（つまり、追加の制約がある場合）、どのメタヒューリスティックが最適に機能するかを事前に判断することは不可能です。

Answer 2

私が知っている良い解決策は、Kempe チェーンでシミュレーテッド アニーリングを使用することです。基本的に、標準のシミュレーテッド アニーリングを使用し、解をランダムに変更したい場合は、隣接する 2 つのノードを選択し、Kempe チェーン ルールに従ってそれらの色を変更します。