文件名称：基于动态规划的独立集算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:31
集训队论文集
3.2 基于动态规划的独立集算法 动态规划是一种高效、灵活的处理问题的方法。在独立集问题中，动态规划不仅能求 解最优化类问题（如最大独立集、最大权独立集），还能求解计数类问题（如独立集计数）。 下面仍以最大独立集问题为例，但为了体现动态规划的通用性，接下来的讨论将不加入最 优性剪枝等仅针对最优化问题的剪枝。 3.2.1 算法 如果要使用动态规划求解独立集问题，就需要将问题化为规模更小的子问题。对于独 立集，我们有以下两个定理： 定理 3.6. 对于无向图 G = (V, E)和 V ′ ⊆ V，则对于任意 I ⊆ V ′，I 是 G的独立集当且仅当 I 是 G[V ′]的独立集。 证明. (充分性)当 I 是 G[V ′]的独立集时，对于任意 (u, v) ∈ E，若 u, v ∈ V ′，显然 u, v不同 时属于 I；若 u, v有一个不属于 V ′，不妨设 u < V ′，那么 u < I。因此 I 是 G的独立集。 (必要性)当 I是 G的独立集时，由于 G[V ′]的每条边都属于 G，故 G[V ′]的每条边至少 有一个端点不属于 I。因此 I 是 G[V ′]的独立集。 定理 3.7. 对于无向图 G = (V, E)和 v ∈ V，若 I ⊆ V 且 v ∈ I，则 I 是 G 的独立集当且仅当 I − {v}是 G[V − {v} − N(v)]的独立集。 证明. 记 T = V − {v} − N(v)。 (充分性)当 I 是 G的独立集时，N(v) ∩ I = ∅，所以 I − {v} ⊆ T，因为 I 在 G中任意两 点不相邻，且 I − {v} ⊆ I，G[T ] ⊆ G，所以 I − {v}是 G[T ]的独立集； (必要性)当 I − {v}是G[T ]的独立集时，因为 I − {v} ⊆ V − {v} −N(v)，所以 N(v)∩ I = ∅， 又因为 G比 G[T ]多的边均与 v或 N(v)中的结点相邻，所以 I 是 G的独立集。 根据以上两个定理，我们可以用状态压缩的动态规划（DP）对于任意的无向图 G = (V, E)求出 G的独立数 α(G)。 对点集 S ⊆ V，定义 f (S )为 S 在 G上的导出子图的独立数，即 f (S ) = α(G[S ])，显然 f (∅) = 0。 考虑 S , ∅的情况。任取 v ∈ S，考虑一个点集 I ⊆ S。若 v < I，则 I 是 G[S ]的独立 集当且仅当 I 是 G[S − {v}]的独立集；若 v ∈ I，则 I 是 G[S ]的独立集当且仅当 I − {v}是 G[S − {v} − N(v)]的独立集。由此可得： 39