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< br> 输入
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。然后需要对照顶点 0 检查顶点 1 是否相邻。顶点 2 需要对照 0 和 1 检查它们是否相邻，依此类推。您正在检查尚未分配颜色的顶点。因此，不要将 j 限制为 n，而是将其限制为当前顶点 v。

最后，使用像 if(match == false) 这样的构造相当混乱，而且没有必要。只需使用 if(!match) 即可。

希望这有帮助。如果您仍然遇到困难，而我碰巧及时看到了评论，我可以提供更多指导。