我参加了一个算法课程，我们在其中重点讨论了 LP，以及对 LP 的许多简化。我记得，普通的 LP 不是 NP-Hard。整数 LP 是 NP-Hard。我目前正在学习 AI 课程的介绍，我想知道 CSP 是否与 LP 相同。
似乎有很多重叠，我无法找到任何证实或否认我的怀疑的东西。
如果它们不相同（或不能归结为另一个），它们的概念的核心区别是什么？
约束满足问题和线性规划有什么区别？
人工智能
比较
约束满足问题
线性规划
2021-11-01 21:58:21
1个回答
LP 是一个数学问题，用于优化受线性（不）等式约束的线性函数：
在哪里是一个连续变量（向量）。如果问题是可行的，那么存在唯一的全局最优解
另一方面，约束满足问题只是上述 LP 的约束部分。所以我们对最优解不感兴趣，只对满足约束的一组值感兴趣。如果变量的域是连续的，则可以将其重铸为具有假目标的虚拟 LP，例如，然后用 LP 求解器求解（例如单纯形算法）
然而，许多 CSP 具有离散变量，因此它们不是 LP。此外，CSP 问题对于普通 LP 算法可能有太多变量无法处理，因此存在特定于问题的快捷算法。我们常常乐于找到可行的解决方案而忘记了“最优性”
其它你可能感兴趣的问题