2

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

巡回セールスマンの問題を解決するために最近傍アルゴリズムを使用しています。非常に高速ですが、正確ではありません。私ができる2つの改善についてどこかで読みました。1 つ目は、1 つのランダム ポイントから開始する代わりに、各ノードから開始する最近傍アルゴリズムを実行します。(したがって、N 個のノードがある場合、最近傍が N 回実行されます) 次に、合計距離が最小のルートを比較して選択します。これははるかに正確であるように見えます。しかし、遅すぎます。

もう 1 つの方法は、開始ノードをランダムに選択する代わりに、特別なノードを選択することです。その後、最近傍を 1 回だけ実行して結果を取得します。これは上記の方法ほど正確ではありませんが、以前のようにアルゴリズムが 1 回だけ実行されるため、はるかに高速です。しかし残念ながら、その記事をどこで読んだのか、この開始ノードを選択する基準を思い出せませんでした。

各ノードから他のノードまでの合計距離を取得する必要があると思います。次に、最大値を持つノードを開始ノードとして選択する必要があります。（私の言葉では、これはグラフから「最も離れた」ノードを選択すると同時に、グラフの中心に近いノードを選択することを避けています）この方法で得られるルートは、最適な最短ルートにかなり近いはずです。

私は正しいと思いますか？

編集:ユークリッド距離を持つメトリック TSP を扱っています。

4

2 に答える 2

1

おそらく、O(K*N*log(N)) しかかからない O(log N) といういくつかの開始ノードで K-NN アルゴリズムを実行する必要があるようです。最適なツアーを選択してから、 2 オプトまたは 2.5 オプトのツアー改善ヒューリスティックを使用して、移動回数または時間制限を制限します。

これにより、おそらくk-opt または v-optベースのアルゴリズムを見始めない限り、時間と精度の最適なバランスが得られるはずです。とはいえ、あなたには彼らのための時間がないようです。

于 2013-04-23T03:46:02.040 に答える
0

最近傍を行うたびにキャッシュすることもできます。K 最近隣人を実行すると、さらに良い結果が得られます。これがどのように機能するかです：

  1. 各ノードについて、K 個の最近傍を見つけます。キャッシュに保存します。
  2. Nearest Neighbor を実行する必要があるときはいつでも、最初にキャッシュをチェックしてください。それ以外の場合は、最近傍を実行してキャッシュに追加します。
于 2013-04-22T16:19:41.773 に答える