最近傍法（さいきんぼうほう、英: nearest neighbor algorithm）とは、巡回セールスマン問題を解くのに使われた最初のアルゴリズムの1つ。素早く短い経路を求められるが、最短でないことが多い。巡回セールスマン問題での最近傍法の使い方は以下のようになる。アルゴリズムは次のようなステップで構成される。頂点を訪れた順番がこのアルゴリズムの出力になる。最近傍法の実装は簡単で実行も高速だが、人間が問題を見て容易に発見できるような最短経路を見逃すことがある。一般に、経路の最後の方の（都市間の）距離が最初の方の距離と変わらないなら、その旅程は適当と言える。後になるほど距離が大きくなるようなら、もっと最短の経路があることが疑われる。求めた経路が十分よいものかどうかをチェックするアルゴリズムも存在する。最悪の場合、最適な経路よりもずっと長い経路が得られる。正確に言えば、あらゆる定数 r について、最近傍法の経路の長さが最適な経路の長さの r 倍になるような問題が必ず存在する。さらに言えば、任意の都市数の問題で最近傍法の結果が最悪経路になるような都市間の距離の設定が存在する。

出典:wikipedia