SAT解算器中的目标函数是如何表示的

Question

SAT解算器可用于解决旅行推销员问题，其中所选边之间的成本总和很重要。我知道你会要求求解器再次寻找更低的成本。这个最大值是如何用连接正规形式表示的？

Answer 1

这个想法是将伪布尔约束转换为CNF，并且可以使用许多不同的编码。天真的编码是枚举所有会导致更高成本(指数(的部分模型。

注：我是以下出版物的合著者：您可能会发现PBLib很有用，因为它提供了不同的编码。