C++で実装する4色問題|バックトラッキング法によるグラフ彩色プログラム

本記事では、有名な4色問題(Four Color Problem)をC++で実装する方法を解説します。4色問題とは、平面上の任意の地図を塗り分ける際に、隣接する領域同士が同じ色にならないようにするために必要な色は最大4色である、という有名な定理(四色定理)に基づく問題です。この問題はグラフ理論における「グラフ彩色問題」として定式化でき、ここではバックトラッキング法を用いて解きます。

アルゴリズム

Begin
    関数issafe()を作成し、現在の色の割り当てが頂点vにとって安全かどうか、
    すなわち辺が存在するかどうかを確認する。
    辺が存在する場合は、
        新しい頂点に塗ろうとする色が、隣接する頂点で既に使用されていないかを確認する。
End
Begin
    関数graphColoringtil(bool graph[V][V], int m, int col[], int v)
    4色問題を解く:
    ここで、
    g[V][V] = 頂点数Vのグラフを表す2次元配列
    m = 使用できる色の最大数
    col[] = 1からmまでの数字を格納する色配列
    if v == V
        return true
    For c = 1 to m
        if (isSafe(v, g, col, c))
            col[v] = c
            if (graphColoringtil(g, k, col, v+1) == true)
                return true
            col[v] = 0
    return false
End

Begin
    関数graphColor():
        主にgraphColoringUtil()を使用して問題を解く。
        m色を割り当てられない場合はfalseを返し、
        そうでなければtrueを返す。
End

アルゴリズムのポイント

この実装の核となるのはバックトラッキング(探索の巻き戻し)です。各頂点に対して候補となる色を1つずつ試し、隣接頂点との色の重複といった矛盾が発生した場合は、直前の選択を取り消して別の色を試します。すべての頂点に矛盾なく色を割り当てられた時点で、解が見つかったことになります。

• isSafe():頂点vに色cを割り当てても安全か(隣接頂点が同じ色を使っていないか)を判定します。
• graphColoringtil():再帰的に各頂点へ色を割り当てていく本体関数です。
• graphColor():色配列の初期化や解の有無の判定など、処理全体の流れを制御します。

C++による実装例

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;
bool isSafe (int v, bool graph[V][V], int col[], int C) {
    for (int i = 0; i < V; i++)
    if (graph[v][i] && C == col[i])
    return false;
    return true;
}
bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
    if (v == V) //すべての頂点に色が割り当てられた場合
    return true;
    for (int c = 1; c <= k; c++) { //頂点vに対して異なる色を試す
        if (isSafe(v, g, col, c)) { //頂点vへの色cの割り当てが有効か確認
            col[v] = c;
            if (graphColoringtil (g, k, col, v+1) == true) //残りの頂点にも再帰的に色を割り当てる
                return true;
            col[v] = 0; //色cでは解に至らない場合は取り消す(バックトラック)
        }
    }
    return false;
}
void solution(int color[]) {
    cout<<"The assigned colors are: \n";
    for (int i = 0; i < V; i++)
        cout<<color[i];
    cout<<"\n";
}
bool graphColor(bool graph[V][V], int k) {
    int *color = new int[V];
    //すべての色の値を0で初期化
    for (int i = 0; i < V; i++)
    color[i] = 0;
    if (graphColoringtil(graph, k, color, 0) == false) {
        cout<<"Solution does not exist";
        return false;
    }
    solution(color);
    return true;
}
int main() {
    bool g[V][V] = {
        {0, 0, 1, 0,1},
        {1, 1, 1, 0,0},
        {1, 1, 0, 0,1},
        {0, 1, 1, 0,0}
    };
    int k= 4;
    graphColor(g, k);
    return 0;
}

出力結果

The assigned colors are:
1 2 3 1 1

まとめ

このプログラムでは、5つの頂点を持つグラフに対して4色での塗り分けを実行し、「1 2 3 1 1」という色の割り当てを得ています。バックトラッキング法はシンプルながら強力な手法で、Nクイーン問題や数独ソルバーなど、他の多くの組合せ問題にも応用できます。ただし、最悪の場合の計算量は指数オーダーに増加するため、大規模なグラフを扱う場合は貪欲法などのヒューリスティック手法と組み合わせることが推奨されます。