現在、100を超えるノードがある加重グラフが与えられています。問題は、作成されたグラフに属するノードの配列 (インスタンスの場合は 10 ノード) を介して最短ツアーを見つける方法です。質問は巡回セールスマンの問題に似ていますが、そうではありません。
私の現在の解決策は非常に簡単です ステップ 1: 10 個のノードの配列から新しいグラフを作成します。ステップ 2 からツアーを作成する必要があります。ダイクストラを使用してノード間の距離を見つけ、グラフ内のすべての頂点を接続します。巡回セールスマン問題に
簡単。ただし、ステップ 2 の複雑さは O(n^2) です。これは、新しいグラフのノードのすべての組み合わせに対して最短パス (多項式の複雑さを持つダイクストラ) を見つける必要があるためです。
アルゴリズムを高速化するにはどうすればよいですか? 最良のケースは、新しいグラフのノードのペアの組み合わせごとに最短距離を見つけなければならないというボトルネックを解消できることです。