16.4 グリーディ彩色アルゴリズム 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム



  • 点彩色問題の位置
    • 集合があり、その部分集合の作る集合の集合(べき集合)があるときに、与えられた条件のもとでの最適な(ある指標を最小化する)べき集合の組み合わせを求める問題の1つ
      • 最小集合カバー問題と呼ばれる
      • べき集合数は、元の集合の要素数nに対して2^n。これの最適組み合わせは容易に大きくなる
    • NP-困難問題のひとつ
    • NP-困難問題は、性能保証された近似アルゴリズムで解くのが現実的
    • 近似アルゴリズム
      • 近似アルゴリズムでは、厳密解に近い解を与えることが知られていることでその近似のよしあしが評価される
      • 近似アルゴリズムの解と厳密解との差が定数内に収まるとき、絶対的近似アルゴリズムであると呼ばれる
      • 近似アルゴリズムの解と厳密解との比が一定定数k内に収まるとき、k-近似アルゴリズムと予備、kを性能比・性能保証・近似比などと呼ぶ
    • 彩色問題は上述の最小集合カバー問題の特殊ケースで絶対的近似アルゴリズムの存在する数少ないもののひとつである
  • 点彩色問題および辺彩色問題に関係する定理
    • 問題の難しさを与える定理
      • 与えられた単純グラフの辺彩色数が3であるか決定する決定問題はNP-完全である
      • 与えられた平面的グラフの(点)彩色数が3であるか決定する決定問題はNP-完全である
    • 問題の容易さを与える情報
      • 上述のNP-完全性をのべた定理から次のことが言える
        • 与えられたグラフの(点)彩色数・辺彩色数が3未満であるかどうかを判定して、3未満であるときに、実際に最適な彩色をすることは、線形時間で可能である
    • 特殊なグラフにおける定理
      • 2部グラフ(Mathematicaの記事はこちら)
        • 2部グラフGにおける辺彩色数はGの点の最大次数に等しい
        • 2部グラフの点彩色数は2(2点彩色グラフを2部グラフの定義としてもよいことから明らか)
        • 多変量組み合わせ関連解析における考え方はこちら
      • パーフェクトグラフ(Mathematicaの記事はこちら)
        • パーフェクトグラフに対しては、点彩色問題・最大重み安定集合問題・最大重みクリーク問題が強多項式時間で解ける(これら3問題は一般グラフに対してNP-困難である)
      • 平面的グラフ(Mathematicaの記事はこちら)
        • 平面的グラフは高々5色で点彩色でき、そのような点彩色は多項式時間で得られる
        • 平面的グラフは本当は高々4色で点彩色できる(そのような点彩色が多項式時間で得られるか、筆者には(まだ)不明)
    • 彩色数と彩色のためのアルゴリズム
      • 最大次数kの無向単純グラフGは高々k+1色を用いて辺彩色できる。その彩色のしかた(辺彩色)は多項式時間で得られる
      • 最大次数kの単純グラフGは高々k+1色を用いて点彩色できる。その彩色のしかた(点彩色)は多項式時間で得られる
        • グリーディ彩色アルゴリズムはこれを与える
        • グリーディ彩色アルゴリズムは、彩色数の小さいグラフに対して、大きい彩色数を与えてしまうが、一般のグラフの点彩色問題に大して、良い性能保証をもつアルゴリズムは知られていない
    • 具体的には
      • 与えられたグラフが2部か否か、パーフェクトか否か、平面的か否かを判定し、いずれかの判定が是であったら、それぞれの教える彩色数の最小のものが、最小近似解であり、いずれでもなければ、グラフの最大次数kについてk+1を最小近似解とすればよさそうだ
    • グリーディ彩色アルゴリズムのソース(ここで用いているGraph classはこちら)

public static int[] GreedyColoring(Graph g){
int[] ret = new int[g.numV];

for(int i=0;i<ret.length;i++){
ret[i]=g.numV-1;

}

for(int i=0;i<ret.length;i++){
int[] tmp = new int[i];
for(int j=0;j<i;j++){

if(g.adjMatrix[i][j]==1){
tmp[j]=ret[j];
}else{
tmp[j]=g.numV-1;
}
}
int[] checker= new int[g.numV];
for(int j=0;j<checker.length;j++){
checker[j]=j;
}
for(int j=0;j<tmp.length;j++){
if(tmp[j]<g.numV){
checker[tmp[j]]=g.numV-1;
}

}

int tmpmin=checker[0];
for(int j=1;j<checker.length;j++){
if(tmpmin>checker[j]){
tmpmin=checker[j];
}
}
ret[i]=tmpmin;
}

return ret;
}