8

我正在研究一个涉及逻辑电路（可以表示为 DAG）的研究问题。DAG 中的每个节点都有一个给定的权重，可以是负数。我的目标是找到一个连通子图，使得节点权重的总和最大。

给定边权重的最大权重连接子图问题显然是 NP-hard，但我希望有向无环性质以及我处理节点权重而不是边权重的事实使问题更容易一些。有人可以指出我如何开始解决这个问题的正确方向吗？

谢谢

4

4 回答 4

2

您提到的问题是 NP-hard，请参阅：Trey Ideker、Owen Ozier、Benno Schwikowski 和 Andrew F. Siegel 撰写的“在分子相互作用网络中发现调节和信号通路”，Bioinformatics，第 18 卷，第 233-240 页，2002

以及本文的补充信息：http: //prosecco.ucsd.edu/ISMB2002/nph.pdf

于 2011-04-14T14:23:41.960 回答
0

第一种方法，将起始节点权重的倒数分配给每条边，并应用像Bellman-Ford这样的最短路径算法。Dijkstra 的算法将不起作用，因为某些边缘可能是负的。

第二种方法，从每个叶节点开始，向每个边添加“标签”，以跟踪所有相关节点的 ID 和总权重。不需要标记节点，因为每个节点都保证从叶子开始的每个链只被访问一次。例如，给定以下无环有向图（从上到下有向图），其中每个节点的权重为 1：

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

A 和 B 之间的边将被标记为 {{D,B,A},3}，A 和 C 之间的边将有两个标签 {{H,E,C,A},4} 和 {{H,F ,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 回答
0

您提到连接的连接子图应该是“最大的”。为此贪婪地选择一个顶点并使其增长，直到您无法增长。这保证了最大化。但是，如果您的意思是“最大”，那么问题可能是 NP_Complete。另外让我提醒您，节点加权图比边加权图更通用。为前者构建的每个算法都适用于后者，但反之亦然。这很容易看到。自己试试。我理解这个问题，我觉得它在 P 中。如果这是正确的，那么提示是使用 DAG 的一些特殊属性（自从你研究以来你就知道了，这似乎是一个讲义问题）。对于一般图，这可以简化为 steiner 树，因此它是 NP-Cmplete（实际上也适用于平面图）。

于 2011-04-04T09:27:10.577 回答