8

宿題があり、解き方がわかりません。あなたが私にアイデアを与えることができれば、私はとても感謝しています.

これが問題です:「N 個の頂点と N 個のエッジを持つ接続された無向グラフが与えられます。各頂点にはコストがあります。サブセット内の頂点の総コストが最小になるように、頂点のサブセットを見つける必要があります。各エッジは、サブセットの少なくとも 1 つの頂点に付随しています。」

前もって感謝します！

PS: 私は長い間解決策について考えてきました。私が思いついた唯一のアイデアは、バックトラッキングまたは 2 部グラフでの最小コスト マッチングですが、どちらのアイデアも N=100000 には遅すぎます。

4

2 に答える 2

2

これは、動的計画法を使用して線形時間で解決できます。

N 個の頂点と N 個の辺を持つ連結グラフには、ちょうど 1 つのサイクルが含まれます。このサイクルを検出することから始めます (深さ優先探索の助けを借りて)。

次に、このサイクルのエッジをすべて削除します。このエッジに付随する 2 つの頂点はuとvです。このエッジの削除後、ツリーができました。根uを持つ根付き木として解釈します。

このツリーの動的プログラミングの再帰は、次のように定義できます。

  • w 0 [k] = 0 (葉ノードの場合)
  • w 1 [k] = vertex_cost (葉ノードの場合)
  • w 0 [k] = w 1 [k+1] (1 つの子孫を持つノードの場合)
  • w 1 [k] = vertex_cost + min( w 0 [k+1], w 1 [k+1]) (1 つの子孫を持つノードの場合)
  • w 0 [k] = sum( w 1 [k+1], x 1 [k+1], ...) (分岐ノードの場合)
  • w 1 [k] = vertex_cost + sum(min( w 0 [k+1], w 1 [k+1]), min( x 0 [k+1], x 1 [k+1]), .. .)

ここkにノードの深さ (ルートからの距離) があります。w 0は、 wが「サブセット」にない場合のノードwから始まるサブツリーのコストです。w 1は、w が「サブセット」にある場合のノード w から始まるサブツリーのコストです。 「サブセット」で。

各ノードについて、 w 0とw 1の 2 つの値のみを計算する必要があります。しかし、サイクル上にあったノードの場合、4 つの値が必要です: w i,j 。ここで、ノードvが「サブセット」にない場合は i=0、ノードvが「サブセット」にある場合は i=1 、j=0 の場合現在のノードは「サブセット」にありません。現在のノードが「サブセット」にある場合は j=1。

「サブセット」の最適コストは、min( u 0,1 , u 1,0 , u 1,1 ) として決定されます。「サブセット」自体を取得するには、各サブツリー コストとともにバック ポインターを格納し、それらを使用してサブセットを再構築します。

于 2012-12-16T12:04:38.667 に答える
1

エッジの数が同じ数の頂点に厳密であるため、NP-Complete である一般的な頂点カバーの問題ではありません。ここに多項式の解があると思います：

  1. N 個の頂点と (N-1) 個のエッジのグラフはツリーです。グラフには N 個の頂点と N 個のエッジがあります。まず、ループを引き起こしているひどいエッジを見つけて、グラフをツリーにします。DFS を使用してループを見つけることができます ( O(N))。ループ内のエッジのいずれかを削除すると、ツリーが作成される可能性があります。極端な条件では、N 個の可能なツリーが得られます (生のグラフは円です)。

  2. O(N)考えられる各ツリー ( ) に単純な動的計画アルゴリズム ( ) を適用O(N^2)し、コストが最小のものを見つけます。

于 2012-12-16T11:57:13.583 に答える