5

我有以下问题：

给定空间中的 n 个点，我正在搜索一个穿过它们的超平面。

此类问题的最简单示例是两点 (x_1=0,x_2=0) 和 (1,-1)，我希望返回 1*x_1+1*x_2=0。

我的观点将是 32 位整数的 n 元组。所需超平面 a_1 x_1 + a_2 x_2 + ... = c 的系数 a_i 也必须是 32 位整数。如果无法以这种方式定义超平面，我想报告这个。

我的项目是用 C++ 编码的。

我可能可以自己编写代码，但我预计这将是相当多的工作。另外，我的预感是，这是一个足够普遍的问题，可能会有一个开源库来解决我的问题。有人知道可以解决我的问题的图书馆吗？

提前致谢！

4

3 回答 3

3

实际上这并不难，因为给定的点是线性无关的。

让 Z^n 中的 u^i 成为您的节点，然后将 v^i 定义为 (u^i_0, ..., u^i_{n-1},-1)。

现在创建一个矩阵 A

( v^0_0     v^0_1 ...     v^0_n     )
( v^1_0     v^1_1 ...     v^1_n     )
    .         .             .
    .         .             .
    .         .             .
( v^{n-2}_0 v^{n-2}_1 ... v^{n-2}_n )

你要解决的是A * x == 0。

现在继续执行高斯消除。确保您仍然让系数为整数。因此，您不必执行 r_k -= r_ki * r_i / r_ii，而必须执行 r_k = r_ki * r_i - r_ii * r_k。在每一步之后，将处理后的行除以其最大公约数。这通常可以避免溢出。如果您遇到溢出，只需为矩阵运算本身使用更大的类型。

最后，您将拥有一个矩阵，其中最多有两列包含多个条目。您的解决方案将仅取决于这两行的值的选择，例如，它看起来像

1 1 1 0 0 0
2 0 0 1 0 0
0 1 0 0 1 0
1 1 0 0 0 1

将任何值分配给 x_0 和 x_1（在此示例中），您就完成了。x 的最后一个值将是超平面等式的右手边。

于 2012-07-21T16:58:47.023 回答
2

我自己没有用过，但LinBox看起来像你想要的。

于 2012-07-21T16:59:12.840 回答
-1

您需要做的就是求解一个线性方程组：

X*A = C

其中 A = (a_1, ..., a_n)^T, C= (c, ..., c)^T。它们都是n1 个向量。并且X是一个m矩阵n

x^1_1  ...  x^1_n
x^2_1  ...  x^2_n
  .     .     .
  .     .     .
  .     .     .
x^m_1  ...  x^m_n

其中每一行是一个点的坐标。假设m有点（无论它们是否线性相关），并且m<=n。

要求解线性方程组，请尝试 2​​ 种情况：C = (1, ..., 1)^T 和 C = (0, ..., 0)^T。

然后你可以使用任何算法，比如高斯或高斯-乔丹消除，来寻求 A = (a_1, ..., a_n)^T。如果m<n和/或点是线性相关的，您将在 中拥有自由变量A，否则A是唯一确定的。从确定的A中，您可以判断 的所有元素是否可能A是整数。

于 2012-07-22T19:30:33.880 回答