0

バックトラッキングを使用して無向グラフの色数 m を決定する必要がある m_coloring 問題に取り組んでいます。これまでの (java) ソリューションは、m をインクリメントし、m_Coloring メソッドを試して、ソリューションが見つからない場合は繰り返します。ただし、より大きなファイルの場合、m が 6 を超えると、計算に時間がかかります。私たちが使用するように与えられたアルゴリズムにはプルーニングが組み込まれていないと言われました.

vColor = new int[nodes+1];
vColor[1] = 1;
while(unsolved)
{
    m++;
    mColoring(1);
}

static void mColoring(int i)
{
    int color;
    if (promising(i))
    {
        if (i==nodes)
        {
            unsolved = false;
        }
        else
        {
            for(color = 1; color<=m; color++)
            {
                if(unsolved)
                {
                    vColor[i+1] = color;
                    mColoring(i+1);
                }
            }
        }
    }
}

static public boolean promising (int i)
{
    int j=1;
    boolean promise = true;

    while(j<i && promise)
    {
        if(adjMatrix[i][j] && vColor[i] == vColor[j])
        {
            promise = false;
        }
        j++;
    }
    return promise;
}
4

1 に答える 1

0

シンプルで効率的でよく知られている正確なアルゴリズムは、Brélaz最小飽和度ヒューリスティック DSATUR (つまり、利用可能な色が少ない頂点を新しい候補頂点として選択し、より多くの異なる色の近傍を持つエイリアスを選択する) を使用して、完全な列挙スキーム内で分岐します。

基本的な刈り込み戦略は暗黙的です。すべての候補頂点は、前の頂点で使用されている色数 + 1 (飽和している場合に割り当てられる新しい色) までしか持てません。これは、最後の割り当てが新しい色であった頂点をバックトラックする任意の分岐に沿って検索を剪定できることを意味します。

申し訳ありませんが、正確な DSATUR ベースのアルゴリズムの Java 実装への参照を提供することはできませんが、興味があれば、C、C++ の参照を提供できます。

于 2014-07-28T21:41:30.023 に答える