スパニングツリーの最小変動アルゴリズム

Question

以下の質問にインタビューで尋ねられ、効率的な解決策が見つけられません。ここで

は問題です：

我々はネットワークを構築したいと我々はn個のノードと、m個のエッジを与えています。エッジ は双方向であり、エッジのコストがわかります。 のすべてのコストは配列Cに保持されているため、C [i、j]は エッジi-jのコストを示します。ノードi、jが接続されていない場合、C [i、j]は無限大です。

ここでも、正確にK個のノードが、このプロパティ（無線 送信用）を持つ他のノードに 無線で通信できることもわかります。無線技術をノードiに設定するには、コストB [i]が必要です。従ってノード012へのワイヤレス伝送の能力を使用するためには ノードi、これはノードiに無線技術を設定するためにB [i]を、ノードjに B [j]を費やすことになる。

したがって、2つのノードi、jのいずれかが通信できる（ のパスが接続されている）ネットワークを構築するために必要な最小コストを見つけることが重要です。

パスとは、ノードiからノード につながるエッジがあるか、または をサポートするノード間でワイヤレス伝送を使用できることを意味します。

最小スパニングツリーが要求されますが、たとえばノードi、jおよびkにワイヤレステクノロジを使用すると、可能なエッジij、ik、jkを追加しますが、 i、jでは、余分なエッジijしか持たないため、エッジは無線伝送にどのノードを使用するかによって異なります。

簡単な例：

レッツは、私たちが4 nodesと3 edgesC[1,2]=9 , C[1,3]=3 , C[3,4]=5（他のC[i,j] are infinite）を持っていると言います。

ノード2および3は、セットアップコストB [2] = 2およびB [3] = 1でワイヤレステクノロジーをサポートします。

は、この例では、最小のコストは、次のようになります。 16 = 8 (for edge 1-3) + 5 (for edge 3-4) + 2 (for set up cost 2) + 1 (for set up cost in node 3).

9ので、トータルコストが9+8+5 = 22.

になり、我々はコストと edge 1-2を含まなければならないし、ネットワークを作るために、エッジ2-3にワイヤレス技術を使用しなかった場合

私はこの種の最小スパニングツリー問題のための効率的なアルゴリズムを探しています。何か助けていただければ幸いです。ありがとうございます！

Answer 1

まず最初に、スパニングツリーの問題を解決してください。これは、あなたにビート試行のための現職の回答を与えます。

ここで、元のグラフと同じ別のグラフを作成し、このネットワークに新しいノードを追加します。すべてのK個のノードをB [i]に等しいエッジ重みでこの新しいノードに接続します。このエッジは、ノードiに無線を追加するコストを表します。新しいグラフの最小スパニングツリーを見つけてください。ノードは、このノードを介して "wifi"として接続できるようになりました。

（私はどのKノードがwifiをサポートしていると仮定していますが、NノードのKを選択する必要はありません。そうでなければ、この新しい最小スパニングツリーにKノード））。