问用移除计算图的“节点闭包”

EN

二十个！相当大，大于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属于Si时，才是从Si到xj的弧。节点闭包和集合覆盖之间有一个直接的对应关系:要从集合覆盖中获取节点闭包，删除与所选集合对应的顶点，然后从节点闭包中获取集合覆盖，取其顶点被选择的所有集合加上包含每个顶点被选择的xj的集合。

(注意，对于集合覆盖，贪婪算法达到最佳逼近比！)对你的问题来说，类似的事情可能是真的。)