8

私は、論理回路 (DAG として表すことができる) を含む研究問題に取り組んでいます。DAG の各ノードには特定の重みがあり、これは負になる場合があります。私の目的は、ノードの重みの合計が最大になるように接続されたサブグラフを見つけることです。

エッジの重みが与えられた最大重み接続サブグラフ問題は明らかに NP 困難ですが、私が望んでいるのは、有向非巡回の性質と、エッジの重みではなくノードの重みを扱っているという事実により、問題が多少簡単になることです。誰かがこの問題への攻撃を開始する方法の正しい方向に私を向けることができますか?

ありがとう

4

4 に答える 4

2

あなたが言及した問題は NP 困難です。次を参照してください: 「分子間相互作用ネットワークにおける調節およびシグナル伝達回路の発見」、Trey Ideker、Owen Ozier、Benno Schwikowski、Andrew F. Siegel、Bioinformatics、Vol 18、p.233-240、2002

およびこの論文の補足情報: http://prosecco.ucsd.edu/ISMB2002/nph.pdf

于 2011-04-14T14:23:41.960 に答える
0

接続されたサブグラフは「最大」である必要があるとおっしゃいました。このために、貪欲に頂点を選択し、成長できなくなるまで成長させます。これにより、最大性が保証されます。ただし、「最大」を意味する場合、問題はNP_Completeである可能性があります。また、ノード加重グラフはエッジ加重グラフよりも一般的であることを思い出させてください。前者用に構築されたすべてのアルゴリズムは後者に適用できますが、その逆は常に正しいとは限りません。これは非常に見やすいです。自分で試してみてください。私が問題を理解しているのは、それがPにあると感じています。それが正しければ、そのためのヒントは、DAGにいくつかの特別なプロパティを使用することです（これは、私たちの研究以来知っているはずであり、これは講義ノートの問題のようです）。一般的なグラフの場合、これはシュタイナー木に還元できるため、NP-Cmpleteです（平面グラフの場合も同様です）。

于 2011-04-04T09:27:10.577 に答える
0

最初のアプローチ、開始ノードの重みの逆数を各エッジに割り当て、Bellman-Ford のような最短経路アルゴリズムを適用します。一部のエッジが負になる可能性があるため、ダイクストラのアルゴリズムは機能しません。

2 番目のアプローチでは、各リーフ ノードから始めて、関連するすべてのノードの ID と合計の重みを追跡する「タグ」を各エッジに追加します。ノードをマークする必要はありません。各ノードは、リーフから始まるチェーンごとに 1 回だけアクセスされることが保証されているためです。たとえば、各ノードの重みが 1 である次の非巡回有向グラフ (上から下へ向かう) があるとします。

                         A     G
                        / \   /
                       /   \ /
                      B     C
                      |    / \
                      D   E   F
                           \ /
                            H

A と B の間のエッジには {{D,B,A},3} のタグが付けられ、A と C の間のエッジには {{H,E,C,A},4} と {{H,F の 2 つのタグが付けられます。 、C、A}、4}。

この前処理の後、各ルート ノードの最大重みパスを見つけます。情報は、アウトバウンド エッジのタグにあります。

于 2011-03-25T19:34:41.270 に答える
0

エッジの重みが与えられた最大重み接続サブグラフ問題がNP困難である場合、あなたの問題はNP困難であると思います。ノードの重みの問題をエッジの重みの問題に減らすことができます。

1)Lets say that your nodes have weights wn1,wn2,wn3,....wnN; where N is # of nodes.

2)Lets also say that the edges can be represented by e1,e2,e3,...eE; E- # of edges.

The weight of the edge ei:nj->nk can be defined as F(wnj,wnk), the function being
arbitrary. For simplicity we can assume wei=wnj+wnk.

Now if we assume that all node weights are independent and non-identical, then we
can say the same about the edge weights. As a DAG with non-identical edge weights
is NP hard, your problem too is. 

Having said that, I think you should proceed in the following way:
1)Look for similarity in node weights for your particular problem. If there are any,
try to look up the literature for similar problems. 

2)If they are hard to find, I suggest you translate your node weight problem to edge 
weight one, and see how the similarity in node weights translates to edge weights
problem and see what simplification can you apply to this problem, again from 
literature.

これが役立つことを願っています。

于 2011-04-23T16:21:29.717 に答える