最近傍アルゴリズム

最近傍アルゴリズム

クラス	近似アルゴリズム
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle \Theta (N^{2})}$
最悪の場合の 空間複雑度	${\displaystyle \Theta (N)}$
最適	いいえ

最近傍アルゴリズムは、巡回セールスマン問題を近似的に解くために使用された最初のアルゴリズムの 1 つです。この問題では、セールスマンはランダムな都市から出発し、最も近い都市をすべて訪問するまで繰り返し訪問します。このアルゴリズムは、短いツアーをすぐに実現しますが、通常は最適なツアーにはなりません。

アルゴリズムの手順は次のとおりです。

1. すべての頂点を未訪問として初期化します。
2. 任意の頂点を選択し、それを現在の頂点uとして設定します。u を訪問済みとしてマークします。
3. 現在の頂点uと未訪問の頂点vを結ぶ最短の辺を見つけます。
4. v を現在の頂点uとして設定します。v を訪問済みとしてマークします。
5. ドメイン内のすべての頂点が訪問された場合は終了します。それ以外の場合は、手順 3 に進みます。

訪問された頂点のシーケンスがアルゴリズムの出力です。

最近傍アルゴリズムは実装が簡単で、実行も高速ですが、その「貪欲」な性質により、人間の洞察力で簡単に気付く短いルートを見逃すことがあります。一般的な目安として、ツアーの最後の数ステージの長さが最初のステージの長さと同程度であれば、ツアーは妥当です。最後の数ステージの長さが最初のステージよりはるかに長い場合は、もっと良いツアーが存在する可能性があります。もう 1 つの確認方法は、下限アルゴリズムなどのアルゴリズムを使用して、このツアーが十分かどうかを推定することです。

最悪の場合、アルゴリズムは最適ツアーよりもはるかに長いツアーを導きます。正確には、定数rごとに巡回セールスマン問題の例があり、最近傍アルゴリズムによって計算されたツアーの長さは最適ツアーの長さのr倍よりも長くなります。さらに、都市の数ごとに、最近傍ヒューリスティックが唯一の最悪のツアーを生成する都市間の距離が割り当てられます。(アルゴリズムが開始頂点としてすべての頂点に適用された場合、見つかった最善のパスは少なくとも N/2-1 の他のツアーよりも優れています。ここで N は頂点の数です。) ^[1]

最近傍アルゴリズムでは、実行可能なツアーが存在する場合でも、それをまったく見つけられない場合があります。

• G. Gutin、A. Yeo、A. Zverovitch、「TSP の指数近傍と支配分析」、『巡回セールスマン問題とそのバリエーション』、G. Gutin および AP Punnen (編)、Kluwer (2002) および Springer (2007)。
• G. Gutin、A. Yeo、A. Zverovich、「巡回セールスマンは貪欲であってはならない：TSP の貪欲型ヒューリスティックスの支配分析」。離散応用数学 117 (2002)、81–86 ページ。
• J. Bang-Jensen、G. Gutin、A. Yeo、「貪欲アルゴリズムが失敗するとき」離散最適化 1 (2004)、121–127。
• G. Bendall と F. Margot、「組み合わせ問題に対する貪欲型耐性」、離散最適化 3 (2006)、288–298。