最大权重连接子图在有向无环图中

Question

我正在研究涉及逻辑电路的研究问题(可以表示为DAG).DAG中的每个节点都有一个给定的权重,可以是负数.我的目标是找到一个连接的子图,使得节点权重之和最大.

给定边缘权重的最大权重连接子图问题显然是NP难的,但我希望的是有向非循环性质以及我处理节点权重而不是边权重的事实使得问题更容易一些.有人能指出我如何开始攻击这个问题的正确方向吗？

谢谢

Answer 1

第一种方法，为每条边分配起始节点权重的倒数，并应用最短路径算法，如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}。

经过此预处理后，找到每个根节点的最大权重路径。该信息位于其出站边缘的标签中。