4

問題に進む前に、いくつかの定義を説明しましょう。

ポイントAは、ポイントBと同じ座標（2倍の値を持つ可能性があります）、たとえば（1.2,3.5,4.3,2.6）であると言います。

点Aが点Bを支配します。ただし、1。点Aのすべての座標<=点Bのすべての座標、および2.点Aの1つの座標<点Bの対応する座標

例：与えられた

A=(2,3,4,5)
B=(2,3,4,6)

条件1が成立するためAがBを支配し、条件2の場合、Aの4番目の成分<Bの4番目の成分。

別の例を考えると、

A=(2,3,4,5)
B=(2,3,4,5)

どちらの場合も条件2が成立しないため、AがBを支配することはなく、その逆も同様です。

n次元の座標のリストが与えられたので、他の座標に支配されていない座標のセットを見つけたいと思います。これらの座標はスカイラインセットと呼ばれます。

5次元の座標があるとしましょう

(2,1,2,1,2)
(1,2,1,2,1)
(3,3,3,3,3)
(4,4,4,4,4)

スカイラインセットは

(2,1,2,1,2)
(1,2,1,2,1)

今、私は関数を書きたいと思います：

List<double[]> SkylineSet(List<double[]> Coordinates, int dimension)

与えられた入力例：

 List<double[]> newList=new List<double[]>();
 newList.Add(new double[] {2, 1, 2, 1, 2});
 newList.Add(new double[] { 1, 2, 1, 2, 1 });
 newList.Add(new double[] { 3, 3, 3, 3, 3 });
 newList.Add(new double[] { 4, 4, 4, 4, 4 });

SkylineSet(newList,5)出力します

(2,1,2,1,2)
(1,2,1,2,1)

これは、各座標のペアワイズ比較によって達成できますが、座標の数は非常に多くなる可能性があります。これを効率的に解決する方法を知っている人はいますか？

4

2 に答える 2

1

ポイントをKDツリー（またはそのようなデータ構造）に配置します。これで、特定のポイントが支配的なポイントを効率的に見つけることができます。支配されたものを削除し、残りのすべてのポイントについて繰り返します。

于 2012-09-13T14:01:08.047 に答える
0

これがうまくいくかどうかはわかりません。それは私の頭の中でもっともらしいようです。これはまさにあなたがすでに行っていることかもしれません。

支配行列NxNを作成します。ここで、Nはポイントの数です。マトリックスの値は、「等しい」、「支配的」、「支配的」、「どちらでもない」です。すべてのマトリックスセルを「等しい」に設定します。この行列は、アルゴリズムの最後に結果を保持します。

最初の座標から始めます。

ここでは、現在の座標のすべての値だけでなく、それらがどのポイントに関連しているかを示す1つの配列があると想定しています。

現在の座標のみを見て、部分的な支配の関係を確立します。支配の関係には、「等しい」、「支配されている」、「支配している」という1つの値があります。「どちらでもない」ということはありません。

この配列を二重ネストループで実行します（I = 0、N-2; J = I + 1、N-1）。2つのポイントのリレーションRと、これら2つのポイントのリレーションマトリックス内のセルCが与えられると、マトリックスは次のように新しい値Cに更新されます。

Cが「等しい」場合、C =R
です。Cが「どちらでもない」場合、変更されません。
Cが「支配的」であり、Rが「支配的」である場合、Cは「どちらでもない」になります。それ以外の場合は変更されません。
Cが「支配的」であり、Rが「支配的」である場合、Cは「どちらでもない」になります。それ以外の場合は変更されません。

すべての座標に対してこのプロセスを繰り返し、結果をマトリックスに蓄積します。

最後に、各ポイントのマトリックスを実行します。他のポイントと「支配的な」関係がないすべてのポイントを取ります。

于 2012-09-13T14:45:01.543 に答える