5

私は次の問題を抱えています：

空間内にn個の点がある場合、それらを通過する超平面を検索しています。

このような問題の最も簡単な例は、2つのポイント（x_1 = 0、x_2 = 0）と（1、-1）であり、1 * x_1 + 1 * x_2=0を返したいと思います。

私のポイントは、32ビット整数のnタプルになります。目的の超平面a_1x_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を実行する必要があります。各ステップの後、処理された行を最大公約数で除算します。これにより、通常、オーバーフローが回避されます。オーバーフローが発生した場合は、行列演算自体に大きな型を使用してください。

最終的に、複数のエントリを持つ最大2つの列が含まれるマトリックスが作成されます。ソリューションは、これら2つの行の値の選択のみに依存します。たとえば、次のようになります。

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、mbynマトリックスです

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

ここで、各行は点の座標です。ポイントがありm（線形に依存しているかどうかに関係なく）、およびm<=n。

一次方程式を解くには、C =（1、...、1）^ T、およびC =（0、...、0）^Tの2つのケースを試してください。

次に、ガウスやガウスの消去法などのアルゴリズムを使用して、A =（a_1、...、a_n）^Tを求めることができます。m<nおよび/またはポイントが線形に依存している場合は、に自由変数があります。Aそれ以外の場合Aは、一意に決定されます。決定されたものから、のすべての要素が整数Aである可能性があるかどうかを判断できます。A

于 2012-07-22T19:30:33.880 に答える