graph - ターゲット コストを持つスパニング ツリーの検索

Question

私はこれにかなり困惑しています。投稿するのは初めてなので、これがばかげた質問である場合はご容赦ください。

重み付けされたエッジを持つグラフ G=(V,E) が与えられたとします。ターゲット コストが c の G のスパニング ツリーを作成したいと考えています。ここで、スパニング ツリーのコストは、すべてのエッジ コストの合計として定義されます。コスト c の G の全域木が存在するかどうかを判断するにはどうすればよいでしょうか?

Answer 1

ここでそれを突き刺します。動的計画法を使用してサブセット合計の問題を解決し、可能なサブセットごとにスパニング ツリーを形成するかどうかを確認します。サブセット合計の一般的な定式化は次のとおりです。 C[i,S] をステートメントのブール値とします。

合計が i になる S のサブセットがあります。

e を任意のエッジとする。その後、再発は通常次のようになります。

C[i,S' U e] = true if C[i, S'] or C[i - weight(e), S']

(エッジ e を使用するか使用しないかのどちらかであり、エッジ e を使用してもサイクルが形成されないことを確認してください)。

ターゲット コストが c の場合、1 <= i <= c ごとに n 回のスイープを実行する必要があります。n はエッジの数です。

最後に、選択したエッジの数が頂点の数より 1 少なく、すべて接続されていることを確認します。

もう 1 つのアプローチは、バックトラック再帰を使用して、すべてのスパニング ツリー <= targetCost を検索することです。