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

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

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

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