2

オブジェクト [a, b, c, d, ...] の配列と、オブジェクト x と y がどのように「異なる」かを示す数値を与える関数 distance(x, y) とします。

そのサブセット要素間の最小差を最大化する長さ n の配列のサブセットを見つけるアルゴリズムを探しています。

もちろん、要素を削除すると距離が大きく変わる可能性があるため、他の要素との最小の差で配列を並べ替えて、上位 n 個のエントリを取得することはできません。たとえば、a=b の場合、a を削除すると、b と別の要素との最小距離が劇的に変化します。

これまでのところ、私が見つけた唯一の解決策は、最小距離が最小の要素を繰り返し削除し、各繰り返しで距離を再計算して、n 個の要素だけが残るか、またはその逆に新しい要素を繰り返し選択することでした。距離を再計算し、新しいピックを追加するか、距離の最小値に基づいて既存のものを置き換えます。

これらの反復なしで同じ結果を得る方法を知っている人はいますか?

PS: ここに例を示します。マトリックスは各要素間の「距離」を示しています...

   あいうえお
a - 1 3 2
b 1 - 4 2
c 3 4 - 5
日 2 2 5 -

2 つの要素のみを保持する場合、それは c と d になります。3 のままにしておくと、それは a または b、c および d になります。

4

2 に答える 2

3

この問題はNP 困難であるため、それを解くための効率的な (多項式時間) アルゴリズムは誰も知りません。

CLIQUEからの削減による、NP困難であるという簡単なスケッチを次に示します。

グラフ G と数値nの形式のCLIQUE のインスタンスがあり、Gにサイズnのクリークがあるかどうかを知りたいとします。頂点iとjは G で接続されているか、接続されていない場合は 0 です。次に、要素間の最小距離を最大化するサイズnの G の頂点のサブセットを見つけます (問題)。このサブセットの頂点間の最小距離が 1 の場合、G にはサイズnのクリークがあります。それ以外の場合はそうではありません。

于 2013-01-16T00:41:44.317 に答える
1

ガレスが言ったように、これはNP困難な問題ですが、この種の問題を解決するための多くの研究が行われており、ブルートフォースよりも優れた方法が発見されています. 残念ながら、これは非常に大きな領域であるため、解決策の可能な実装を永遠に検討することに費やすことができます。

ただし、これを解決するヒューリスティックな方法に興味がある場合は、グラフ内の最適なパスを見つけるのにかなり効果的であることが証明されているAnt Colony Optimization ( ACO ) を調べることをお勧めします。

于 2013-01-16T19:52:17.607 に答える