如何评估图形着色难度？

Question

我正在开发一个基于HTML Canvas和JavaScript的小型游戏来进行自我训练，我选择创建一款地图着色难题游戏。

我最初计划使用给定算法解决难题所需的时间来设置难度，但最终我选择实现暴力求解算法。其他算法对我来说太复杂了，因为我没有找到一些清晰的资源来解释如何实现最优3或4种颜色方案。

我的问题是有些棘手的难题可以制作出来，使得暴力求解需要很长时间，而采用另一种求解方法则可能很容易解决难题。

那么，您如何确定地图着色难题的相对难度？

- thomas

---

感谢大家提供高质量的答案！ - thomas

Answer 1

你的地图是一个无向图。顶点是需要填充颜色的表面，而边缘则连接相邻表面。
当每个表面有很少的相邻表面时，难度较低。如果每个顶点都有许多边，则难度较高。
因此，排列难度的一种方法就是：

difficulty = total_number_edges - total_number_vertices

一个天真的公式。现在，你可以通过添加其他变量来改进这个公式，例如每个定点的最大边数或总顶点数（拼图面积越大，难度越高，需要更多时间填充）。

difficulty = (total_number_edges - total_number_vertices)  
                        * (total_number_vertices / max_edges_in_vertex)

你应该成为大师公式的创造者 :)

- Iulius Curt

---

我进行了试验和研究，得出结论：对于每个算法，都可以找到一类难以解决的谜题。作为人类，我相信我们学习得很快，并且可以根据谜题调整策略。因此，我决定遵循您的建议，采用天真的方法并进行一些改进。 - thomas

Answer 2

地图/图形着色问题是“NP完全问题”。这意味着科学界几乎可以确定，对于某些问题实例（即难题），任何给定的算法都将花费指数级（巨大）的时间。这就是为什么你实现的任何算法（包括你的“蛮力”机制）都会在某些难题实例上失败。

我建议你实现几种不同的算法来解决你的难题，例如：

• 算法1-逐个选择一个随机区域，并给它一个仍然“适合”的颜色，即不是任何有色邻居的颜色。如果遇到冲突（无法给所选区域着色），则停止算法。运行此循环，比如说，N次，并计算循环实际上着色整个地图的次数；让这个数字为K。这里你得到一个得分K/N（百分比），0％=困难问题（可能不可能），100％=非常容易的问题

• 算法2-向算法1添加一定量的回溯，例如允许最多1,000个回溯步骤。运行相同的“采样”循环。你会得到另一个0％-100％的得分。

然后使用得到的分数（从Alg. 2获得的分数比从Alg. 1获得的分数更高，因为它更强大）来获取难题的相对难度。

整个过程的关键是，如果您得到分数（0％，0％），即您不知道难题是否可解决，您应该将其丢弃，因为您不想向观众呈现可能无法解决的问题：）

最后，使用自己的判断力将分数“映射”到“人类可读”的难度描述——选择几个难题，手动解决它们，检查程序计算的分数，然后看看百分比分数如何映射到您对难度的感知。

- Antti Huima

---

确定平面图的色数是NP完全问题。当我第一次阅读您的答案时，我认为您的意思是给图着色是NP完全问题，但实际上并不是这样。有算法可以用4种颜色、5种颜色等来给平面图着色。 - Christian Ammer

哦，那不是真的。即使在平面图上，着色本身也是NP完全问题。请查阅任何标准参考资料。此外，所有的平面图都可以用4种颜色进行着色。这就是著名的四色定理。 - Antti Huima

我在阅读[N Robertson]、[DP Sanders]、[P Seymour]和[R Thomas]的论文《Efficiently four-coloring planar graphs》中得知，使用k种颜色对平面图进行着色，当k<=2或k>=6（如果可能，则k<=2）时是显然的。当k=5时，存在一种线性算法，当k=4时，存在一种二次算法。此外，还有一个网站附有关于四色定理和二次算法的简要摘要。该网站为：http://people.math.gatech.edu/~thomas/FC/fourcolor.html#Algorithm。 - Christian Ammer

你说得没错，但这并不违背NP完全性。维基百科上写道：“图着色问题是计算难题。对于给定的k，除了k = 1和k = 2的情况外，确定一个给定的图是否允许k-着色是NP完全的。特别地，计算色数是NP难的。即使在度为4的平面图上，3-着色问题仍然是NP完全的。”关键在于，一个可4-着色的图也可能是可3-着色的，而检查这一点是NP完全的。 - Antti Huima

Answer 3

我发现了一段话，这给了我一个想法，可以让你评估困难程度。

一类近似算法是基于“贪心”方法的 - 顶点按顺序处理，每个顶点分配到最低编号的颜色，不与其之前已着色邻居冲突。因为当前顶点相邻的顶点可能使用所有四种颜色，第五种甚至第六种、第七种等颜色可能是必要的。当贪心算法需要创建新的颜色类时，该顶点被称为在“僵局”中。

因此，必要颜色类的数量可能是您难题的难度。您可以按顶点度数从高到低处理顶点（排序模式为最大优先）。

我在Raymond A. Archuleta和Henry D. Shapiro的论文A Fast Probabilistic Algorithm For Four-Coloring Large Planar Graphs中找到了引用的段落。

- Christian Ammer

---

但是必要的颜色类别数量通常只有2、3或4种。因此，你不能真正将难度划分为3个数字。更不用说4种颜色的拼图可能非常容易，也可能非常复杂。 - Iulius Curt

@iuliux: 不，贪婪算法遍历所有节点，并按照确定的顺序（例如最大优先级）进行迭代，不能找到最小必要颜色数（_色数_）。可能需要第五、第六、第七等颜色。所需颜色数可能是难度的指标。 - Christian Ammer