如何编码检查不等式系统是否有解决方案

Question

我需要找到可以检查系统是否像这样的算法

x1 * k + b > y1, x2 * k + b > y2, ..., xn * k + b < yn

有解决方案 我用 x[i] 和 y[i] 代替，未知变量是 k,b.

Answer 1

如果只有最后一个不等式是“<”，其他不等式都是“>”。检查方法如下：

将系统转换为：b > y1 - x1 * k, b > y2 - x2 * k, ..., b < yn - xn * k

并且容易看出原系统是否有解等价于系统yn - xn * k > y1 - x1 * k, yn - xn * k > y2 - x2 * k, ...有解决方案

等价于yn - y1 > (xn - x1) * k, yn - y2 > (xn - x2) * k, ...有无解

然后你需要讨论xn - xk的符号，它们是零，正还是负，你可以进一步将系统转化为更简单的形式。例如，如果 xn - x1 > 0 且 xn - x2 <0，它将如下所示：k < (yn - y1)/(xn - x1), k > (yn - y2)/(xn - x2)， ...

然后很容易检查新的简单系统是否有解，相当于原来的系统有无解。

Answer 2

你的问题等同于询问点是否线性可分（其中一个 class 点对应不等式为 >，其他点为 <）。

如果存在分隔线，您可以使用 Perceptron Algorithm 查找分隔线。该维基百科页面也提供了一些替代算法。