6

我不确定这是否真的是一个“着色”问题，就像它是一个分配/线性规划问题一样。我在这两个方面的专业知识都为零，所以请原谅可能出现的任何菜鸟。但我觉得这个问题之前几乎肯定已经解决/调查过，在查看http://en.wikipedia.org/wiki/Category:Graph_algorithms上的许多图形算法后，我找不到任何东西。我希望能在正确的方向上得到一些指示。

“问题陈述”有效地归结为：

  1. 图中有两种类型的顶点：路由器和核心。

  2. 核心仅连接到路由器。每个核心仅连接到单个路由器。每个都有用户输入/定义的“颜色”。（在我的具体问题中，颜色仅限于说 4/5 可能的颜色之一）。它们的颜色不能改变，它是一个输入参数。（核心是下图中的正方形）

  3. 路由器连接到核心以及其他路由器。他们没有分配给他们的“颜色”。分配颜色是程序/算法目标的一部分。（路由器是下图中的圆形顶点。）

  4. 该程序的目标是为图中的每个路由器分配颜色，以使不同颜色的顶点之间的“交叉”/边的数量最小化。

（另一种观点：本质上，您会得到一个图，其中一些顶点是彩色的，而另一些则不是。目标是对那些没有着色的顶点着色，以使不同颜色的顶点之间的边数最小化。）

我能够将这个（我确定很差）制定为一个整数线性程序，并使用 LP-Solve 设置了一个解决方案/方法。我也有自己的启发式方法。我很想知道解决这个问题的“正确”/已知/其他方法？！

非常感谢！

演示的简单示例。

4

2 回答 2

3

让我们首先关注两种颜色的外壳。我们可以把它变成st min cut的一个实例。这个想法是我们在图中指定了一个s节点和一个t节点，并且我们希望将剩余节点划分为s组或t组，使得两组之间的边权重之和为最小化。对于您的版本，我们有一个主黄色节点s和一个主红色节点t，并且我们在每个核心及其对应的主颜色节点之间放置一个超过原始图中所有边数的高加权边，所有原始边都完好无损，每个边的权重为 1。高成本优势确保我们永远不会非法重新着色任何内核，因为移动所有路由器会更便宜。这个问题可以通过Max flow-Min cut theorem使用标准最大流量算法在多项式时间内解决。最佳选择取决于您的边和顶点数。

在多种颜色的情况下，您正在尝试解决“多端切割”问题。这与最小k切问题有关，但该问题的标准参考是论文The Complexity of Multiterminal Cuts（k切文章间接链接到该论文）。对于超过 2 种颜色，显然如果图形是平面的，问题仍然可以在多项式时间内解决；否则，它是NP-hard，因此您不妨使用整数规划求解器，因为这是另一个 NP-hard 问题。

于 2012-05-25T08:10:36.723 回答
0

如果颜色数量 <= 5 并且路由器 <=10，那么您可以使用蛮力。

选项远少于 5^10 个，特别是如果默认情况下您为每个路由器着色最常见的颜色，然后只需更改其中一些的颜色，必要时回溯。

编辑：还有一个不错的哈密顿路径算法，如果路由器少于 15 个，您也许可以适应您的需求。在图中找到哈密顿圈的动态规划算法是什么？

于 2012-05-25T05:19:02.740 回答