5

私はテストのために学んでいます、そして私はこの問題で管理することができません：

n<1000ポイントのセットと整数dが与えられます。タスクは、 A_i（i = 1または2の場合）からのポイントの各ペア間の距離（ユークリッド）が小さくなるように、ポイントA_1とA_2の2つの互いに素なセット（この和集合にはnポイントのセットが与えられます）を作成することです。 dに等しい。不可能な場合は、-1を出力します。

たとえば、次のように入力します。

d = 3、およびポイント：

（5,3）、（1,1）、（4,2）、（1,3）、（5,2）、（2,3）、（5,1）

作成できます：

A_1 = {（2,3）、（1,3）、（1,1）}

A_2 = {（5,3）、（4,2）、（5,2）、（5,1）}

A_iからのポイントの各ペア（i = 1または2の場合）は十分に近いためです。

私は本当にそれを解決する方法を知りたいのですが、わかりません。nが小さいので、アルゴリズムはO（n ^ 2 log n）でもかまいませんが、開始方法がわかりません。おそらく、ポイントの各ペア間の距離を数えることから始めて、最大距離の2つのポイントを取り、それらを異なるセットに配置することを考えていました（それらの距離がdより大きい場合）。次に、残りのペアについてこの手順を繰り返しますが、問題は、次のポイントを合法的にどこに置くことができるかをどのように決定するかです。誰かがこのアルゴリズムを手伝ってもらえますか？

4

3 に答える 3

5

n個のノード（n個の点に対応）を持つ単純なグラフを考えてみましょう。対応する2つのポイント間の距離がdより大きい場合、2つのノードが接続されます。

2つの互いに素なセットを作成できる場合は、2部グラフが必要です（一部のノードが他のノードに接続されていない場合は、任意のセットに入れることができます）。

したがって、単純なグラフの2つの部分をテストするだけで済みます。

http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness

于 2013-01-09T00:28:02.640 に答える
1

距離行列から始めるのは良い考えのようです。次に、この距離行列で、dより大きいすべてのエントリを選択します。このエントリは、対応するポイントが異なるセットにある必要があることを意味します。

2つの空のセットから始めて、関連するすべてのエントリを繰り返します（> d）。

セットが空の場合は、2つのポイントをセットに入れます。それ以外の場合は、次の3つのオプションがあります。

  1. ポイントがどのセットに属しているかが明確な場合は、それらをそれらに配置します（つまり、ポイントを挿入すると、距離行列から取得できる最大距離基準が保持されます）。
  2. いずれかのセットにポイントを挿入できない場合、問題は解決できません。
  3. 両方の点で両方のセットが可能である場合、問題があります。ポイントセットの新しいペアを開始し、それらにポイントを入れることをお勧めします。次に、後続のポイントペアが再び不明な場合は、2番目のセットペアを確認します。それでも不明な場合は、3番目のセットペアなどを確認してください。ポイントペアが前のセットに挿入されている場合、ポイントが明確になっている場合は、次のセットを確認してください。最後に、ポイントのセットのペアのリストがあり、必要に応じて結合できます。

私はちょうど2番目のアプローチのアイデアを思いつきました。これは似ていますが、もう少し速いはずです。

また、距離行列から始めます。

2つのセットに加えて、スタック、キュー、または新しく追加されたエントリを維持します。

したがって、距離行列から最初の関連エントリを選択すると、ポイントが両方のキューに追加されます。キューの1つにエントリがある限り、次の手順を実行します。

ポイントをキューから削除し、セットに挿入します。挿入が最大距離の基準に違反する場合、問題は解決できません。この点の距離行列の行または列を調べて、この行/列の関連するすべてのエントリを抽出します。パートナーポイントを他のセットのキューに追加します（これは別のセットにある必要があるため）。

両方のキューが空の場合は、まだアクセスされていない次の関連エントリをキューに追加して、最初からやり直します。

このアルゴリズムには、ポイントが相互に影響を与える可能性のある順序で処理されるという利点があります。したがって、複数のセットのペアは必要ありません。

于 2013-01-08T23:36:36.100 に答える
1

上部にすべてのポイントがあり、側面にすべてのポイントがある配列を考えてみてください。

セルを定義する2つのポイント（左と上）がd以上離れている場合は、任意のセルにゼロを配列に入力し、2つのポイントがd未満離れている場合は1を入力します。

       (5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)
(5,3),          0      1      0      1      1      1
(1,1),   0             0      1      0      1      0
(4,2),   1      0             0      1      1      1
(1,3),   0      1      0             0      1      0
(5,2),   1      0      1      0             0      1
(2,3),   1      1      1      1      0             0
(5,1)    1      0      1      0      1      0

（注：各三角形に同じ0と1を反転させて入力する必要があります。）

対角線は無視してください。右上の三角形のセクションに注意してください。

0列目をスキップします。

最初の列から始めて、一番上の行に1がない場合は、一番上の行に1がある右側の別の列と交換します。次に、同じ行も入れ替えて、対角線を空白のままにします。（存在しない場合、解決策はありません。）[例：列2と3と行2と3を入れ替える]この行の選択が最適化要因になる可能性があることに注意してください。

次の列に移動し、一番上の行に1がない場合は、右側の列と交換して、対応する行を交換します。存在しない場合は、その列に1が含まれるその下の行と交換して、対応する列を実行してみてください。対角線より下の場合、その下の行は無視する必要があります。

三角形の左上隅に1が含まれているポイントを収集しています。これらのポイントはすべて、コレクションの1つに入れることができます。

これは私が頭の中でこれを行うことに迷うところですが、三角形の右下隅から始めて、他のコレクションにあるポイントを収集する同様のプロセスを実行する必要があります。行と対応する列を入れ替えて、三角形の右下隅に1を集めます。

右上隅に長方形（左下隅が切り取られていない真の長方形）を形成できる十分な行を交換し、その長方形にすべての0が含まれている場合、解決策があります。それができない場合、解決策はありません。

三角形に1が含まれる一番下の行と、三角形に1が含まれる右端の列、およびそれらが出会うセルの比較があります。解が存在するためには、そのセルが三角形の中にある必要があります。

（行と列のスワップをインターリーブして、三角形の左上隅と右下隅から0を削除する方法を見つけるために、大きな「やること」を残しました。ここでの議論で、作成方法を解決できるかもしれません。それは機能します。または、機能しないことを確認してください。）

于 2013-01-08T23:41:27.003 に答える