java - グラフでいくつかのノードを互いに切断する最小コストを取得する方法

Question

特定のグラフで、グラフ内のノードを互いに切断する最小コストを計算したいと考えています。例:このグラフで、これらのノード間のいくつかのエッジを削除することによって、
を切断したいとします。つまり、 と を削除すると、ノードとが切断されます。ここでコストとは、削除されるエッジの長さを意味します。この例では、 を切断するための最小コストの合計は、とを相互に 2+1=3 とします。 誰かがヒントを提供できますか。この問題を分類することはできません。node Anode Cnode Fedge A-Bedge F-EACFNode ANode CNode F
shortest path problemminimum spanning tree problem

Answer 1

これを多端子切断問題と呼びます。残念ながら、ウィキペディアのエントリはないようです。問題は、重み付けされたグラフと端子と呼ばれる頂点のサブセットが与えられた場合に、エッジの最小重みセットを計算することです。エッジを削除すると、端子のすべてのペアが切断されます。悪いニュースは、この問題が NP 困難であることです。そのため、ブルート フォースできないインスタンスで最適なソリューションが本当に必要な場合は、おそらく整数計画法に頼る必要があります。良いニュースは、単純な 2 近似アルゴリズムがあることです (知られている最良の係数ではありませんが、線形計画法をブラッシュアップし、研究文献を読んで「より良い」ものを使用する必要がある場合があります)。各端子を他の端子から分離する st カットの結合。