有向グラフに Christofides アルゴリズムを実装することは可能ですか?
無向グラフがあるとします。このグラフでは、すべての頂点が、グラフ内の他のすべての (それ自体ではなく) 両方向にエッジを持っています。ただし、エッジの重みは、必ずしも両方の方法で同じである必要はありません (非対称)。
たとえば、一方通行の道路がたくさんあるストリート マップを考えてみます。
ここで、すべての頂点を通る巡回セールスマン ツアーの近似値を見つけたいと考えています。
まず第一に、Christoffides アルゴリズムはそのような TSP に対して定義されていません。これは、最小スパニング ツリーが有向グラフに対して定義されていないためです。
それでも、エドモンズ アルゴリズムをルートとして、ツアーの開始点への最適な分岐を見つけることからアルゴリズムを開始します。
次に、分岐の最小完全一致を見つけて、それがオイラー グラフになるようにします。これはハンガリアン アルゴリズムで発生します。このアルゴリズムでは、最小の一致が検出されるため、分岐のすべての頂点のあとがきに同じ量のエッジが出てきます。
最後のステップでは、オイラー ツアーを見つけ、ショートカットを使用してツアーを最適化します。
質問があります：
- アルゴリズムを正しく実装したい方法ですか、それとも間違っていて機能しませんか
- それが機能する場合、tsp の最適解の 1.5 倍に制限されますか?