有向无环图中连接子图的最大权重
我正在研究涉及逻辑电路（可以表示为DAG）的研究问题。 DAG中的每个节点都有一个给定的权重，可以是负的。 我的目标是找到一个连接的子图，使得节点权重的总和最大。
给定边权重的最大权重连接子图问题显然是NP-hard，但我希望的是，定向无环性和我正在处理节点权重而不是边权重的事实使问题更容易一些。 有人能指出我如何开始攻击这个问题的正确方向吗？
谢谢
您提到的问题是NP难题，请参阅Trey Ideker，Owen Ozier，Benno Schwikowski和Andrew F. Siegel，Bioinformatics，Vol 18，p.233-240,2002年发表的“在分子相互作用网络中发现监管和信号电路”
和本文的补充信息：http://prosecco.ucsd.edu/ISMB2002/nph.pdf
第一种方法，为每个边分配起始节点权重的倒数，并应用像Bellman-Ford这样的最短路径算法。 Dijkstra的算法不会工作，因为某些边缘可能是负面的。
第二种方法，从每个叶节点开始，为每个边添加“标签”，以跟踪所有涉及的节点的id和总权重。 没有必要标记节点，因为每个节点保证只从叶子开始的每个链只被访问一次。 例如，给定以下Acyclic Directed图（从顶部到底部），其中每个节点权重为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}。
在此预处理之后，为每个根节点找到最大的权重路径。 这些信息位于其出站边缘的标签中。
你提到那个连接的子图应该是“最大的”。 为此，贪婪地选择一个顶点并将其增长直到不能成长。 这保证了最大限度。 但是，如果你的意思是“最大”，那么问题可能是NP_Complete。 另外让我提醒你，节点加权图比边缘加权图更普遍。 为前者构建的每种算法都适用于后者，反之亦然并非总是如此。 这很容易看到。 尝试一下自己。 我理解这个问题，我觉得它是在P.如果这是正确的，那么提示是为DAGs使用一些特殊属性（这是你的研究知道，因为你的研究，这似乎是一个讲座笔记问题）。 对于一般图，这可以简化为steiner树，因此它是NP-Cmplete（事实上也适用于平面图）。
链接地址: http://www.djcxy.com/p/35277.html上一篇: Maximum weight connected subgraph in an directed acyclic graph