optimization - primm グラフからの TSP および Lin-Kernighan アルゴリズム

Question

TSP の問題をコーディングしようとしています。Primm algo のおかげで、既に最小の重みグラフを持っています。このグラフから Lin-Kernighan アルゴリズムを構築できることも読みましたが、その作成方法がわかりません。

誰かがそれを実行する方法を私に説明できますか?

ありがとう

Answer 1

最小スパニング ツリーからオイラー回路を構築する必要があり、Lin Kernigan を使用して重複するパス (2 つのエッジ間の x クロス接続) を削除できます。