algorithm - 完整的图 k 着色求解器

Question

我正在寻找一个完整的 CSP 求解器，这意味着它总能找到一个解决方案（如果存在），并且会告诉您是否存在解决方案。首选为图形着色优化的求解器，但不是必需的。那里有许多迭代算法/求解器，但我的工作需要完整性（？）。

我已经使用弱承诺搜索算法实现了自己的求解器，但我确信有许多优化和基于线程的功能可以使求解器更快，并允许我增加可以在模拟中使用的变量数量. 我意识到这是一个指数级难题，但每一点都会有所帮助！

Answer 1

有人已经实现了Mehrotra 和 Trick的分支定价方法。我没有使用过这段代码，但我相信这种方法在精确着色方面是最先进的。