特定の無向加重グラフで最遠 K 近傍を見つけたいです (グラフは疎な加重行列として与えられますが、推奨される表現を使用できます)。問題が明確に定義されていることを確認するために、互いに最大の距離を持つ k 個のノードを見つけたいと考えています。最適なセットに近いソリューションも問題ありません-メッシュ内の最も遠い点を見つけるために必要なだけです:)
1244 次
1 に答える
1
まともな解決策を探しているだけだと仮定すると、巡回セールスマンの問題の「最も遠い挿入」の開始位置に似た単純な解決策をお勧めします。
- 空のセットに 1 つのポイントを追加します。できればコーナーまたはエッジに 1 つ追加します (もちろん、すべてを試すこともできます)。
- セットに最も遠いポイントを追加します (セット内の現在のポイントからの距離を最も長くします)
- セットに k 個のポイントが存在するまで、前の手順を繰り返します。
最適ではありませんが、おそらくそれほど悪くはありません。
これを改善したい場合は、ヒューリスティックを使用して結果を改善できます。たとえば、次のようになります。
- 点 1 から j までを省略した集合 j を考える
- これらの j 点を置き換えるためにすべての可能な点を試してください
- 考えられる最善の解決策を記録する
- 点 2 から j+1 までを省略した集合を考える
など
さらに、k が大きすぎず (たとえば 5 未満)、ポイントの合計量が大きすぎず (たとえば 100 未満) である場合、考えられるすべての組み合わせを計算する方がおそらく簡単です。これは、ノルム計算が効率的に実行できることを前提としています。
編集:
これを実装したいことがわかったら、通常の続行方法は、似たようなものを見つけて、ニーズに合わせて少し編集することです。このページを下にスクロールすると、最も遠い挿入の例が見つかるはずです。「遠く」の測定値に従うように編集すると、管理しやすくなります。
于 2012-11-11T10:32:29.003 に答える