c语言算法 - 贪婪算法 - 二分覆盖

核心提示：二分图是一个无向图，它的n个顶点可二分为集合A和集合B，c语言算法 - 贪婪算法 - 二分覆盖，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中），检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A'

二分图是一个无向图，它的n个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A' 覆盖集合B（或简单地说，A' 是一个覆盖）。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时，A' 为最小覆盖。

例1-10 考察如图1 - 6所示的具有1 7个顶点的二分图，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A'={ 1 , 1 6 , 1 7 }是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译人员进行翻译”这一类的问题。

二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k个集合S={S1 , S2 ,., Sk }，每个集合Si 中的元素均是全集U中的成员。当且仅当èi S'Si=U时，S的子集S' 覆盖U，S '中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S' 为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 , ., Sk ，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。

例1 - 11 令S={S1，...，S5 }, U={ 4，5，...，15}, S1={ 4，6，7，8，9，1 3 }，S2={ 4，5，6，8 }，S3={ 8，1 0，1 2，1 4，1 5 }，S4={ 5，6，8，1 2，1 4，1 5 }，S5={ 4，9，1 0，11 }。S '={S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖，S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。

集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。

例1-12 考察图1 - 6所示的二分图，初始化A'=且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。顶点1能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }），顶点2 覆盖一个( { 4 } )，顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 , 9 , 1 0 , 11 }。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点{ 1 0 , 11} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A'={ 1 6 , 1 , 1 7 }。

图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。

1.数据结构的选取及复杂性分析

为实现图13 - 7的算法，需要选择A' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A' 仅使用加法运算，则可用一维整型数组C来描述A '，用m 来记录A' 中元素个数。将A' 中的成员记录在C[ 0 :m-1] 中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi 值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。