0

特定の無向加重グラフで最遠 K 近傍を見つけたいです (グラフは疎な加重行列として与えられますが、推奨される表現を使用できます)。問題が明確に定義されていることを確認するために、互いに最大の距離を持つ k 個のノードを見つけたいと考えています。最適なセットに近いソリューションも問題ありません-メッシュ内の最も遠い点を見つけるために必要なだけです:)

4

1 に答える 1

1

まともな解決策を探しているだけだと仮定すると、巡回セールスマンの問題の「最も遠い挿入」の開始位置に似た単純な解決策をお勧めします。

  • 空のセットに 1 つのポイントを追加します。できればコーナーまたはエッジに 1 つ追加します (もちろん、すべてを試すこともできます)。
  • セットに最も遠いポイントを追加します (セット内の現在のポイントからの距離を最も長くします)
  • セットに k 個のポイントが存在するまで、前の手順を繰り返します。

最適ではありませんが、おそらくそれほど悪くはありません。

これを改善したい場合は、ヒューリスティックを使用して結果を改善できます。たとえば、次のようになります。

  • 点 1 から j までを省略した集合 j を考える
  • これらの j 点を置き換えるためにすべての可能な点を試してください
  • 考えられる最善の解決策を記録する
  • 点 2 から j+1 までを省略した集合を考える

など

さらに、k が大きすぎず (たとえば 5 未満)、ポイントの合計量が大きすぎず (たとえば 100 未満) である場合、考えられるすべての組み合わせを計算する方がおそらく簡単です。これは、ノルム計算が効率的に実行できることを前提としています。

編集:

これを実装したいことがわかったら、通常の続行方法は、似たようなものを見つけて、ニーズに合わせて少し編集することです。このページを下にスクロールすると、最も遠い挿入の例が見つかるはずです。「遠く」の測定値に従うように編集すると、管理しやすくなります。

http://snipplr.com/view/4064/shortest-path-heuristics-nearest-neighborhood-2-opt-farthest-and-arbitrary-insertion-for-travelling-salesman-problem/

于 2012-11-11T10:32:29.003 に答える