0

これは、行列の彩色数に対する力ずくの試みです。必要な正しい色数が得られるという意味では機能しているようですが、1,2,3,4 ではなく 1,2,3,6 が表示されます。何らかの理由で、マトリックスがより少ない色で成功する可能性がある場合でも、それでも失敗し、最大数に達し続けます。失敗し続けるのには何か理由があるのですか？

「n」は色の最大数です。"v" は頂点、"m" は現在使用されている色の数です。

疑似コード: http://i42.tinypic.com/deoc2u.jpg

static int color(){ 
       int i;
       for(i = 1; i <= n; i++)
       {
               if(color(0,i)){
                       return i;}
       }
       return i;
}

    static boolean color(int v, int m) {

    if(v > n-1)
            return true;
    else
    {
            for(int i = 1; i <= m; i++)
            {
                    boolean match = false;
                    q[v] = i;

                            for(int j = 0; j < n; j++)
                            {
                                    if(input[v][j] == 1)                
                                    {
                                            if(q[v] == j+1)
                                                    match = true;
                                    }
                            }

                    if(match == false)
                    {
                            if(color(v+1,m)) 
                                    return true;
                    }
            }
            q[v] = 0;
            return false;
    }

}

出力例:

ファイル名: file1
入力
6
0 1 1 0 1 1
1 0 1 1 1 1
1 0 1 0 1
0 1 1 0 1 1
1 0 1 0 1
1 1 1 1 1 0
1 失敗
2 失敗
3 失敗
4 失敗
5 失敗

色: 1 2 3 1 3 6

4

1 に答える 1

0

ああ、私は眠るべきです！でも、絶対最後の瞬間まで延期した回数は数えられないので、締め切りに共感しています。

これは実際には「ブルートフォース」アプローチではありません。実際には、考えられるすべてのノードの色付けの組み合わせを試し、競合しないものを確認するためです。あなたのアプローチは、欲張りカラーリングとして知られるヒューリスティックです。最適な結果を見つけることができますが、任意に悪い解決策を生み出す可能性もあります。そうは言っても、私はあなたが提供したサンプル入力（ありがとう、Microsoft Paint）を手動で調べてみましたが、そのアルゴリズムに従うと、頂点0から開始したときの結果は実際に4になるはずです。

だから、これがあなたのコードに間違っているかもしれないと私が信じていることです。次の抜粋では...

if(input[v][j] == 1)
{
    if(q[v] == j+1)
    match = true;
}

i他の頂点の色ではなく、現在の頂点の色（とにかく）を頂点インデックスと比較しているようです。内部テストを次のように変更する必要があると思います...

if(i == q[j])

または、必要に応じて（違いはありません）...

if(q[i] == q[j])

また、チェックが多すぎます。頂点0に色1を割り当てることができます。次に、頂点1が隣接している場合は、頂点0に対してチェックする必要があります。頂点2は、0と1が隣接している場合は、それらに対してチェックする必要があります。まだ色を割り当てることができなかった頂点をチェックしています。したがって、現在の頂点に限定するのではなく、限定してjください。nv

最後に、のような構造を使用することif(match == false)はかなり混乱し、必要ではありません。if(!match)代わりに使用してください。

お役に立てれば。あなたがまだ立ち往生していて、私がたまたまコメントを間に合うようにキャッチした場合、私はより多くのポインタを提供することができます。

于 2011-11-16T01:08:26.040 に答える