2

いくつかの方程式によって決定されるオブジェクトの頂点を見つけたいと思います。例えば。

Eq1:   2x + y +  z <= 12;
Eq2:    x + y      >= 23;
Eq3:    x + y +  z <= 10;

そして、それはによって制限されています

x >= 0
y >= 0
z => 0

そしてそれは六面体を与える。このオブジェクトが作成された頂点の位置を知りたいです。

これを行う唯一の方法は、この方程式のすべての可能なバリエーションをチェックするコードを作成することですか?

array = array with this equations (6 elements)

for( i = 1; i <= array.lenght; i++ ){
 for( j = 1; j <= array.lenght; j++ ){
  for( k = 1; k <= array.lenght; k++ ){
    //and there check is solve of a variation is possible
  }   
 }    
}
4

1 に答える 1

3

これは、頂点列挙問題として知られています。多面体を半空間表現 (不等式のセット) から頂点表現に変換することです。一般的なケースでこれを効率的に行うためのアルゴリズムが文献に多数あります。できるだけ効率的にする必要がある場合は、これらのアルゴリズムのいずれかを検討する必要があります。

しかし、限定された縮退していない六面体を形成することが知られている半空間は 6 つしかないため、ブルート フォースはおそらく問題ありません。すべての頂点は 3 つの面の交点にあります。したがって、3 つの不等式の各サブセットを取得し、対応する方程式の交点を計算します。(これを行う方法については、以下を参照してください。)交差が存在しない場合 (たとえば、2 つの平面が平行である場合)、または交差ポイントが他の 3 つの不等式のいずれも満たさない場合、それらの 3 つのファセットは 1 点で交わりません。バーテックス; それ以外の場合、ポイントは頂点の 1 つです。6 C 3 = 20 の組み合わせのそれぞれについて繰り返すと、最終的に 8 つの頂点が得られるはずです。

3 つの不等式の交点を計算するには、単純な線形代数を使用できます。たとえば、次の 3 つの不等式を取ります。

2x +  y +  z <= 12
 x +  y      >= 23
 x           >= 0

それらを行列方程式として書きます。

┌             ┐┌   ┐   ┌    ┐
│ 2    1    1 ││ x │   │ 12 │
│             ││   │   │    │
│ 1    1    0 ││ y │ = │ 23 │
│             ││   │   │    │
│ 1    0    0 ││ z │   │  0 │
└             ┘└   ┘   └    ┘

(行列の行は、各不等式のx、y、およびの係数ですz。) 左側の行列が特異な場合 (つまり、行列式がゼロの場合)、共通の交点はありません。それ以外の場合は、行列を逆にして解を計算します。

┌   ┐   ┌             ┐-1┌    ┐
│ x │   │ 2    1    1 │  │ 12 │
│   │   │             │  │    │
│ y │ = │ 1    1    0 │  │ 23 │
│   │   │             │  │    │
│ z │   │ 1    0    0 │  │  0 │
└   ┘   └             ┘  └    ┘

任意の線形代数ライブラリでこの計算を行うことができます。または、これは 3D であるため、Cramer の規則を使用できます。次に[x y z]、他の 3 つの不等式と照合して、それが頂点かどうかを判断します。

于 2016-03-14T03:54:42.297 に答える