6M-02
DSATURアルゴリズムにおける解の改善に向けた色の選択方法に関する検討
○中山大夢,若葉陽一(木更津高専)
グラフ彩色問題は、無向グラフの頂点に色を割り当てる組み合わせ最適化問題であり、隣接する頂点が同じ色にならないようにしつつ、使用する色の数を最小化することを目的としています。この問題はさまざまな分野で応用されています。DSATURは、頂点の彩色順序を考慮するグラフ彩色問題のアルゴリズムです。これまでの研究では、DSATURにおける色の選択方法が検討されましたが、目立った改善は見られませんでした。本研究では、色の使用頻度を優先する新しい彩色順序を提案します。その結果、高頻度使用を基準にした彩色は使用色数の全体的な改善につながることが分かりました。一方で、低頻度使用を基準にした彩色は全体的な性能の悪化を招く結果となりました。