java - Java中的蛮力色数

Question

这是对矩阵色数的蛮力尝试。从某种意义上说，它似乎可以为我提供所需的正确颜色数量，但它不是 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 1 0 1 0 1
0 1 1 0 1 1
1 1 0 1 0 1
1 1 1 1 1 0
1 失败
2 失败
3 失败
4 失败
5 失败

颜色：1 2 3 1 3 6

Answer 1

嘎嘎，我该睡觉了！但我数不清有多少次我把任务推迟到最后一刻，所以我对你的最后期限表示同情。

这并不是真正的“蛮力”方法，因为这实际上归结为尝试每个可能的节点着色组合并检查哪些不冲突。您的方法是一种称为贪婪着色的启发式方法。它可以找到最佳结果，但也可以产生任意错误的解决方案。也就是说，我已经尝试手动检查您提供的示例输入（谢谢，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 检查顶点 2，依此类推。您正在检查尚未分配颜色的顶点。所以不要限制j，n而是限制在你当前的 vertex v。

最后，使用 likeif(match == false)结构相当混乱且没有必要。改用就好if(!match)了。

希望这可以帮助。如果您仍然卡住并且我恰好及时赶上了评论，我可以提供更多指示。