0

タイトルが下手ですみません。グラフアルゴリズムは初めてです。

私は数日間問題に悩まされています。有向非巡回グラフのすべてのノードが重み付けされている場合、重みが負になる可能性がある場合、重みの合計が最大になるセットを見つけるにはどうすればよいですか?

たとえば、5 つのノードのグラフがあります。

  • ノード 1 : 重み 30、ノード 4 に向けられたエッジを持つ
  • ノード 2 : 重み 25、エッジがノード 4、5 に向けられている
  • ノード 3 : 重み -65、エッジなし
  • ノード 4 : 重み -20、エッジからノード 5
  • ノード 5 : 重み 2、エッジなし

最大ポイントを見つけながら、たとえば、ノード 1 が選択された場合、ノード 4 と 5 を選択する必要があります (ノード 1 から直接/間接的に隣接しているため)。

したがって、最大ポイントは- (30-20+2)+(25)=37 です。

ノード 1 と子孫 4,5 の場合、次にノード 2 の場合 (ノード 4,5 は考慮されなくなりました)

問題が明確になったことを願っています。どうすればこれを達成できるか教えてもらえますか？

4

1 に答える 1

0

あなたの質問を正しく理解できれば...あなたが望むのは、そのノードが到達できる値の合計を最大化するノードを見つけることです。

これを行う擬似コードを次に示します。

def maxVertex(Vertices):
    for vertex in reversed_topological_sorted(Vertices):
         vertex.value = vertex.weight
         if vertex.neighbors:
                vertex.value += sum( other_vertex.value for other_vetrex in vertex.neighbors )

     return max(Vertices,key=lambda vertex: vertex.value)
于 2012-04-28T07:10:47.827 に答える