algorithm - 如何评估图形着色难题的难度？

我正在开发一个基于HTML Canvas和JavaScript的小型游戏来训练自己，我选择创建一个 map 着色益智游戏。

我最初计划使用给定算法解决难题所需的时间来设置难题难度，但最终我选择实现暴力破解算法。其他算法对我来说太复杂了，因为我没有找到清楚的资源来很好地解释最佳3色或4色性的算法。

我的问题是可以制作一些棘手的难题，因此蛮力求解需要很长时间，而使用另一种求解方法仍然可能很容易。

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

最佳答案

您的 map 是非定向图。顶点是要填充颜色的表面，边缘是连接的邻居。
当每个表面上的邻居数量很少时，一个难题的难度就很低。一个难题是每个顶点都有很多边。
因此，对难题进行排名的方法将是:

difficulty = total_number_edges - total_number_vertices

天真。现在，您可以通过添加其他其他变量(例如，顶点中的边的最大数量或顶点的总数)来改进此公式(要解决的难题是，要填充很多表面的难题更加困难并且需要更多时间)

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

您应该是主配方的发明者:)

关于algorithm - 如何评估图形着色难题的难度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5513805/