c - Christofidesアルゴリズムでショートカットステップを実装するには?

Question

三角形の不等式に従うグラフで TSP の 3/2 近似を取得するためのクリストフィデス アルゴリズムを実装しています。Kruskal のアルゴリズムと隣接行列を使用して最小全域木を計算するためのコードは既にあります。

ここで、エッジを 2 倍にし、オイラー ツアーを見つけて、複製ノードをショートカットすることで、Christofides を実装したいと考えています。この手順を実行するにはどうすればよいですか? アルゴリズムと (オプションで) C コードが欲しいです。

ありがとう！

Answer 1

「ショートカット」ステップは、オイラー ツアーから少なくとも 1 回ツアーに登場したすべてのノードを切り取ることによって機能します。たとえば、ツアーがあった場合

A→B→A→D→A→E→A

あなたはサイクルで終わるでしょう

A→B→D→E→A

これを行う 1 つの方法は次のとおりです。ツアーでこれまでに訪れたすべてのノードのセットを維持します。ツアーに沿って歩いているときに、未訪問のノードに遭遇した場合は、それをサイクルに追加してセットに追加します。訪問したノードに遭遇した場合は、スキップしてください。最後に、見つけた最後のノードから開始ノードに戻るエッジを追加します。

お役に立てれば！