最近傍法

最近傍法（さいきんぼうほう、英: nearest neighbor algorithm）とは、巡回セールスマン問題を解くのに使われた最初のアルゴリズムの1つ。素早く短い経路を求められるが、最短でないことが多い。

概要

巡回セールスマン問題での最近傍法の使い方は以下のようになる。

アルゴリズムは次のようなステップで構成される。

  1. 任意の頂点を現在の頂点として選ぶ。
  2. 現在の頂点とまだ訪れていないある頂点 V を結ぶ最も重み付けの軽い辺を探す。
  3. V を現在の頂点とする。
  4. V に訪れたという印を付ける。
  5. 全頂点を訪れたら、終了。
  6. ステップ2に戻る。

頂点を訪れた順番がこのアルゴリズムの出力になる。

最近傍法の実装は簡単で実行も高速だが、人間が問題を見て容易に発見できるような最短経路を見逃すことがある。一般に、経路の最後の方の（都市間の）距離が最初の方の距離と変わらないなら、その旅程は適当と言える。後になるほど距離が大きくなるようなら、もっと最短の経路があることが疑われる。求めた経路が十分よいものかどうかをチェックするアルゴリズムも存在する。

最悪の場合、最適な経路よりもずっと長い経路が得られる。正確に言えば、あらゆる定数 r について、最近傍法の経路の長さが最適な経路の長さの r 倍になるような問題が必ず存在する。さらに言えば、任意の都市数の問題で最近傍法の結果が最悪経路になるような都市間の距離の設定が存在する[1]。

脚注

  1. ^ G. Gutin, A. Yeo and A. Zverovich, 2002

参考文献

  • G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
  • J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
  • G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.

関連項目