lisp - 约束满足问题中的启发式是否确保没有回溯？ (当存在解决方案时)

Question

我正在用 Scheme 做一个 map 着色问题，我使用了最小剩余值(选择具有最少合法颜色的顶点)和度启发式选择具有最多邻居的顶点)。如果某个配置存在解决方案，这些启发式方法是否会确保它不需要回溯？

Answer 1

我们来做一个简单的理论分析。

1. Graph coloring is NP-complete对于一般图形(如果不要求着色少于 4 种颜色)。这意味着不存在已知的多项式时间算法。

2. 您的启发式算法可以在多项式时间内计算。

3. 假设你不需要回溯，那么你需要做n步，每一步都需要多项式时间(n是顶点数).因此，您可以在多项式时间内解决问题。
4. 要么您已经证明了 P=NP，要么您的假设是错误的。

我让您来决定第 (4) 点中的哪个选项更合理。