以前の出版物では、再帰的網羅的検索を使用した平面上の巡回セールスマン問題を解決するためのアルゴリズムを検討しました。 結果は好奇心was盛でしたが、最終ルートには明らかに最適でないセクションが含まれていました。 提案された記事では、「再帰的欲張りアルゴリズム」と呼ばれる改善されたアルゴリズムについて説明します。 最終的なルートは、再帰的網羅的検索と比較して、平均で8％優れていることをすぐに認めます。
もう一度問題を定式化します。
平面上にあるN個のノードを指定します。 入力ノード（In）と出力ノード（Out）が指定されています。 入力ノードで始まり、出力ノードで終わり、各ノードを一度だけ通過する、すべてのノードにまたがる最短パスを見つける必要があります。
問題を解決するための計画を統合するために、2つの考慮事項を基礎とします。
1.平面上の2点間の最短経路は直線上にあります。
2.最も遠いノードは、これらの離れたノードが他のノードと最適な方法で接続されていない場合、ルートの全長で最大の誤差を生じます。
これら2つの考慮事項に基づいて、この方法でアルゴリズムを構築します。
1.入力ノードと出力ノードを直線セグメントで接続します。 「Vkh」ノードから「Vkhod」ノードへのこの最終ルートは、明らかに最短です。
2.ただし、問題には、残念ながら、最終ルートにも含める必要がある他のノードがあります。 したがって、この最短ルートを最小限に抑えて、他のノードを1つずつ順番に追加していきます。
3.このため、残りのすべてのノードから、最初の2つのノードまで相互に離れたノードを選択し（2番目の考慮事項により、このノードは最大誤差を導入します）、最適な方法で見つかった最短ルートにそれを含めます-InとOutの間の接続を切断し、接続しますこの3番目の遠距離ノードを介した入出力。
4.次に、最初の3つのノードから相互に離れたノードを再帰的に見つけて、最終ルートに含めます。これにより、ルートの長さの増加が最小限になります。 この4番目のノードをオンにすると、2つのエッジを選択できることは明らかです（3番目のノードにはそのような選択はありませんでした）。 5番目のノード-3つのエッジの選択など。 したがって、以下では、現在の受信ルートのすべてのエッジを整理し、それらからブレークの長さが最小の増加になるエッジを選択する必要があります（この「貪欲な」状況では、アルゴリズムの名前が付けられています）。
5.残りのノードについても同じことを行います。
Object Pascalのプログラムとソースコードは、 ここからダウンロードできます 。
アルゴリズムの利点：
1.シンプル。
2.速度。 クアッドコア2.67 GHzプロセッサーを搭載したマシンでは、3秒で1000ノードが（平均して）計算されます
27秒で2000ノット
87秒で3000ノット
4000ノット-207秒で
時間の増加は指数関数的ですが、実際のタスクではこの成長は非常に遅いです。
3. 以前に提案されたアルゴリズムと比較して、結果は約8％が最良です。
4. RAMの最小使用。
5.設定の欠如。
6.交差点のチェックなしの交差点の最小数。
欠点は、いつものように、利点の裏返しです。
1.設定が不足していても、必要に応じて、計算時間を短縮してルートの品質を低下させることはできません。
2.交差点は非常にまれですが、まだ起こります。
3.指数関数的成長は、どのように減速するかがまだ不明です。 すべてのエッジではなく、このノードに最も近いエッジのみを反復処理することが可能です。
再帰的欲張りアルゴリズムを使用した平面上の巡回セールスマン問題の解決
All Articles