最近傍アルゴリズム
これらのアルゴリズムの手順は次のとおりです。
- すべての頂点を未訪問として初期化します。
- 任意の頂点を選択し、それを現在の頂点uとして設定します。uを訪問したとしてマークします。
- 現在の頂点uと未訪問の頂点vを結ぶ最短のエッジを見つけます。
- vを現在の頂点uとして設定します。vを訪問したとしてマークします。
- ドメイン内のすべての頂点が訪問されている場合は、終了します。 それ以外の場合は、手順3に進みます。
訪問された頂点のシーケンスは、アルゴリズムの出力です。,
最近隣アルゴリズムは実装が容易で迅速に実行されますが、その”貪欲な”性質のために、人間の洞察で容易に気づく短いルートを見逃すことがあり 一般的なガイドとして、ツアーの最後のいくつかのステージが最初のステージに匹敵する場合、ツアーは合理的です。 別のチェック用アルゴリズムなどの下限となるアルゴリズムの推定このツアーです。,
最悪の場合、アルゴリズムの結果、最適なツアーよりもはるかに長いツアーになります。 正確には、すべての定数rに対して、最近傍アルゴリズムによって計算されたツアーの長さが最適ツアーの長さのr倍より大きくなるような移動セールスマン問題のインスタンスが存在します。 さらに、都市の数ごとに、最近傍ヒューリスティックがユニークな最悪の可能なツアーを生成する都市間の距離の割り当てがあります。, （アルゴリズムが開始頂点としてすべての頂点に適用されている場合、見つかった最良のパスは、少なくともN/2-1他のツアーよりも優れています。）
最近傍アルゴリズムは、存在する場合でも実行可能なツアーをまったく見つけられない可能性があります。