0

我正在处理一个 m_coloring 问题，其中我必须使用回溯确定无向图的色数 m。到目前为止，我的（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 回答