nearest neighbor algorithmとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > nearest neighbor algorithmの意味・解説 

最近傍法

(nearest neighbor algorithm から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/12/10 02:39 UTC 版)

ナビゲーションに移動 検索に移動

最近傍法(さいきんぼうほう、: 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.

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「nearest neighbor algorithm」の関連用語

nearest neighbor algorithmのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



nearest neighbor algorithmのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの最近傍法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS