用删除法计算图的“节点闭合”

20!相当大,大于2^61。幸运的是,有更好的方法来解决小实例:(编辑)动态编程。通过保存每个子问题的最优解,我们需要花费一些内存来获得非常大的时间节省。

下面是一些用Python编写的示例代码。在用另一种语言实现下面的代码时,您可能需要对顶点0,…,n-1进行编号,并将这些集合实现为位向量。

# find a smallest node closure of G
# G is a graph in adjacency-list format: G[v] is the set of neighbors of v
def node_closure(G):
    # maps subsets of vertices to their smallest node closure
    smallest = {frozenset(): []}
    def find_smallest(S):
        if S in smallest:
            return smallest[S]
        else:
            candidates = [[v] + find_smallest(S - frozenset([v]) - G[v]) for v in S]
            return min(candidates, key=len)
    return find_smallest(frozenset(G))

这个问题的NP硬度从设定覆盖降低。 保持客观价值 . 这意味着,除非p=np,否则多项式时间算法的最佳保证就是它总是输出一个最多为 O(log n) 比最佳值大几倍。

如果 x1, ..., xm 要覆盖的元素和 S1, ..., Sn 是集合,那么集合覆盖的目标是选择其并集为 {x1, ..., xm} . 假设每个元素都至少出现在一个集合中,那么就制作一个带有节点的图。 x1, ..., xm, S1, ..., Sn, R 有弧的地方 R 对所有 Si 为了所有 i, j 一个弧线 硅 到 xj 如果且仅当 XJ 属于 硅 . 在节点闭合和集合覆盖之间有一个直接的对应关系:要从集合覆盖中获得一个节点闭合,请删除与所选集合对应的顶点,然后 R ;要从节点闭包中获取集覆盖,请获取选择了其顶点的所有集,再加上包含每个顶点的集 XJ 选择了其顶点。

(注意,对于集合覆盖,贪婪算法达到最佳近似比!对于您的问题,类似的情况可能是正确的。)

我会用不同的方式来描述这个问题。要将顶点分成两组。第一组由“根节点”和第二组“从属节点”组成,即直接连接到根节点的节点。

        root     dependent
                  B
           A  <
                  C

                  E
           D  <
                  F

^{图0:可能的结果图。}

您希望最小化根节点的数量。这与最大化依赖节点的数量相同,这与最大化结果图中的边数相同,这与最小化从开始图构建时移除的边数相同。

让我们先看看蛮力:对于将节点分成一个根集和一个从属集的每个二部分,首先检查它是否满足问题语句的条件,最后尽可能做到最好。有一个指数数量的两分法,所以这将必须加以完善。

如果我们将每个边视为具有可能的状态“未知”、“取下”或“移除”,取下一个边将移除源自其末端节点的所有边以及结束于该节点的所有边(见图1)。但是,无论如何,我们最多可以保留一个以特定节点结尾的边。

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

^{图1:取A-D边,删除此处显示的所有其他边。}

有许多“贪婪”的启发式方法:

• 将具有最传出边缘的节点放入根集,将其所有连接的节点放入从属集(我认为这是您的建议)。

这就存在这样一个问题,即一些连接的节点将更好地放入根集,这将使我们得到第一次优化:

• 将具有最多传出连接的节点放入根集中,并将其所有连接的节点标记为“可访问”。然后循环,但只计算到每个点上不“可到达”的节点的连接。当所有节点都在根集中或“可访问”时停止。最后,将所有不在根集中的“可到达”节点放入从属集,并在它们可以连接的根节点之间任意分布。

这看起来很好,但不一定是最佳的。也许你可以从另一边开始:

• 将传出连接数最少的节点放入从属集。“去掉“所有的外边”。取“其来自具有最多传出连接数的节点的传入边缘,并将该节点放入根集。循环,直到所有节点都位于根集中或从属集中。

我仍然不能证明这是否是最佳的,但至少我不能直接想到一个打破它的情况。