linq - 扩展基于 LINQ 的规范模式以实现包容

Question

复合规范模式有很多基于 LINQ 的实现。我还没有见过使用 Subsumption 的。

是否有任何此类示例已被记录（博客等）或作为开源发布？我有一个想法和概念证明，通过让 ExpressionVisitor 将每个规范转换为规范逻辑形式 (CNF/DNF) 来实现这一点，但我担心这过于复杂。有没有更好的办法？

Answer 1

我担心这过于复杂。有没有更好的办法？

简短的回答是“不，没有” ¹

长答案：“过于复杂”抓住了问题的本质：它是 NP 难的。这是一个简短的非正式证明，它依赖于可满足性问题是 NP-complete的事实：

• 假设您有两个布尔公式，A并且B
• 您需要测试 ifA暗示B，或等效地测试和依赖¬A | B的所有变量分配。换句话说，您需要一个重言式的证明。ABF = ¬A | B
• 假设重言式检验可以在多项式时间内进行
• 考虑¬F， 的倒数F。F是可满足的当且仅当¬F不是重言式
• 使用假设多项式算法测试¬F是否是重言式
• “F可满足”的答案与“是¬F重言式”的答案相反
• 因此，多项式重言式检查器的存在意味着可满足性问题在P，并且P=NP。

当然，问题是 NP-hard 的事实并不意味着对于实际情况没有解决方案：事实上，您转换为规范形式的方法可能会在许多现实世界的情况下产生良好的结果。然而，缺乏已知的“好”算法通常会阻碍实际解决方案的积极开发²。

---

¹带有强制性的“除非P=NP”免责声明。

²除非有一个“相当好的”解决方案，如果您允许“假阴性”，那么您的问题很可能就是这种情况。