D次元メトリック空間にN点のセットがあります。サブセット内の任意の 2 点間の最小距離が最大になるように K 個を選択したいと考えています。
たとえば、3D ユークリッド空間で N=4 および K=3 の場合、解は、最も長い短辺を持つ四面体の面になります。
それを達成するための古典的な方法はありますか？多項式時間で正確に解けますか?
できる限りグーグルで検索しましたが、この問題をどのように呼び出すかまだわかりません。
私の場合、通常は N=50、K=10、D=300 です。
説明:
力ずくのアプローチは、N 点の中から K 点のすべての組み合わせを試し、すべてのサブセットで最も近いペアを決定することです。解は、最長のペアを生成するサブセットによって与えられます。
簡単な方法で、O(K^2) プロセスを実行し、N! を繰り返します。/ K!(NK)! 回。
ふむ、10^2 50! /10！40！= 1027227817000
単位円板グラフに関する論文は有益ではあるが、落胆させられると思うかもしれません。たとえば、http://citeseerx.ist.psu.edu/viewdoc/download ?doi=10.1.1.84.3113&rep=rep1&type=pdf には、NP 完全の単位ディスク グラフでの最大独立集合問題は、ディスクが代表が知られています。単位円盤グラフは、平面に点を配置し、最大で単位距離離れた点のすべてのペア間にリンクを形成することによって得られるグラフです。
したがって、多項式時間で問題を解決できれば、選択した2つの点間の最小距離が1をわずかに超える値が見つかるまで、Kのさまざまな値に対して単位円板グラフで実行できると思います。単位円盤グラフ上の最大独立集合となり、多項式時間で NP 完全問題を解くことになります。
（自転車に飛び乗ろうとしているので少し急いでいますが、単位円グラフに関する論文を検索すると、少なくともいくつかの有用な検索用語が見つかるかもしれません）
これを少しずつ説明しようとしています：
ここでは、2 つの問題を関連付ける別の試みを示します。
最大独立集合については、http://en.wikipedia.org/wiki/Maximum_independent_set#Finding_maximum_independent_setsを参照してください。これの決定問題バージョンは、「このグラフには、2 つのエッジが結合しないような K 個の頂点がありますか?」です。これを解決できれば、さまざまな K についてこの質問をして最大の K を見つけ、次に 1 つまたは複数のノードを削除したグラフのバージョンについて質問して K ノードを見つけることで、最大の独立集合を確実に見つけることができます。
単位円板グラフで最大の独立集合を見つけることが NP 完全であることを証明せずに述べます。これに関する別のリファレンスはhttp://web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdfです。
あなたの問題の決定バージョンは、「任意の 2 点間に少なくとも D の距離を持つ K 個の点が存在するか?」です。繰り返しますが、多項式時間で元の問題を解決できる場合は、これを多項式時間で解決できます。答えが「はい」となる最大の D が見つかるまで試してから、点を削除して何が起こるかを確認してください。
単位円板グラフは、2 点間の距離が 1 以下の場合にエッジを持ちます。したがって、元の問題の決定版を解くことができれば、D = 1 を設定して問題を解くだけで、単位円板グラフの問題の決定版を解くことができます。
だから私はあなたの問題を解決できるなら、それをあなたの問題に変えることでNP完全問題を解決できることを示す一連のリンクを構築したと思います。