次のグラフ演習を解決しようとしています。
無向加重グラフには、V 個の頂点と E 個のエッジがあります。0 とラベル付けされた頂点から開始して、T(T<=V) 頂点を訪問するために必要な最小の重みを見つけます。さらに、2 つの訪問された頂点間にエッジがある場合、その重みは 0 に設定されます。
これは、典型的な巡回セールスマンの問題ではありません。これは、2 つの頂点にアクセスすると、それらの間のエッジの重みが 0 になるという条件が追加されているためです。
Prim の最小スパニング ツリー アルゴリズムを使用してアプローチすると、T == V の場合に問題が解決しますが、必ずしもすべての頂点にアクセスする必要はないため、常に最小の重みが返されるとは限りません。
最小のスパニング ツリーを見つけて、すべての「ターゲット」頂点に到達する能力を妨げないすべてのエッジをカットすることを考えましたが、それは過度であり、おそらく正しくないようです。
何かご意見は？
編集：例を挙げます。0、1、2、および 3 のラベルが付いた 4 つの頂点を持つグラフがあるとします。次の辺 (from、to、weight) があります: (0,1,1) (0,2,2) (1,3,4) ) (2,3,1) 最小スパニング ツリーには、エッジ (0,1,1)、(0,2,2)、および (2,3,1) が含まれます。これを使用すると、すべての頂点に 0 から到達できます。ただし、演習の目標は、これらの頂点の T 個に到達することです。そうは言っても、たとえば、頂点 2 と 3 に到達するだけでよく、エッジ (0,1,1) は不要であり、したがって、ターゲット頂点に到達するために必要な合計ウェイトは 1 ではなく 2+1 になります。 +2+1。