集合覆盖问题的一种随机近似算法研究

武汉科技大学 组合数学 课程论文 第 1 页 集合覆盖问题的一种随机近似算法研究 摘摘 要要 集合覆盖问题 SCP 是运筹学中最基本的组合问题 本文给出了集合覆 盖问题的一种随机近似算法 给定的子集的集合 S 和 S 中每 个子集的权值 带权的集合覆盖问题是从 S 中选择费用和最小的子集使得其并 集覆盖 E 对 E 中每一个未被覆盖的元素 以某一精心设计的概率分布选择包 含该元素的子集 直到 E 中所有元素均被覆盖 算法结束 关键词关键词 随机算法 近似算法 集合覆盖 1 1 引言引言 自从集合覆盖问题提出以来 相继有很多学者利用不同思想提出了很多不 同的算法 这些算法主要分为完整算法和启发式算法 完整算法基本上建立在 分支定界基础上 通过比较和分析 Caprara 等人认为 CPLEX 算法是求解 SCP 最好的完整算法 但如果问题规模比较大时 其时间代价会非常高 而启发式 算法则以牺牲解的精度来取得较好的时间复杂度 在可接受的时间内找到一个 最优近似解 在实际问题中 最优近似解一般也能够满足现实的要求 与上述确定算法不同 本文从概率的角度给出了集合覆盖问题的一种随机 算法 由于算法的随机性 每次运行输出的覆盖都是随机的 本文证明了算法 所求覆盖费用的期望值不超过最优覆盖的 B 倍 其中 算法每次运行输出的覆盖都可能不同 因此 可以多次运行该算 法得到一系列覆盖 从中选择费用最小的 该覆盖很可能接近最优解 甚至可 能就是最优解 本算法的时间复杂度是线性的 这为算法的多次运行奠定了基 础 另外 当 B 较小的时候 本文算法可以给出比当前结果较优 的解 2 2 算法算法 1 设为 n 个元素的集合 S 为 E 的子集的集 合 所谓 E 的覆盖是 S 的一个子集 C C 中元素的并集为 E 经典的集合覆盖问 题欲求 E 的一个覆盖 C 使得 C 在 E 的所有覆盖中所含元素个数最少 武汉科技大学 组合数学 课程论文 第 2 页 形式化描述为 输入 集合 E S 输出 使得 且最小 2 带权的集合覆盖问题则是更一般的情况 仍设 对有一个非负 权值叫 表示选择所需要的费用 覆盖 C 的费用为 C 中元素权值的和 相应地 问题的输出是求最小费用的覆盖 形式化描述为 输人 输出 使得 且最小化 3 带权集合覆盖问题的随机近似算法 Algorithm WSC RA 如下 输入 带权重的集合覆盖问题的一个实例 E S W 输出 集合覆盖 C 第一步 以任意顺序排列 E 中的元素 第二步 选择下一个元素 从中随机选择 x 使得 第三步 return C 注意到 包含元素多的集合被选中的概率较大 而在每一轮循环中 算法 以较大概率选择权重较小的集合 3 3 算法近似比的分析算法近似比的分析 武汉科技大学 组合数学 课程论文 第 3 页 定理定理 1 1 假设 其中 那么算法 WSC RA 是一个在期望意义下近似比为 B 的近似算法 首先固定输入实例 E S W 中元素被试探的顺序 并假设是 E S W 的一个最优覆盖 通过 WSC RA 算法得到的解 C 是 S 的一个随机子集 定义定义 1 1 对于任意 s 定义如下一个变量 X 令表示 X 的期望值 表明了集合 s 实际对覆盖 C 的贡献 并且变量的分布和的值在执行算法 WSC RA 之前已经确定 那么算法的输 出结果和期望权重可以表达为 现在的目标是适当地把算法 WSC RA 的分析一般化 考虑在中的集 合 本文将证明这些集合是 C 的主要组成部分 用另外的参数表示这部分元 素 定义定义 2 2 令为算法 WSC RA 计算出的集合 同时这些集合在最优 解中 因为在算法执行之前就已经确定了 显然有 因此 并且因为 所以有 定理定理 2 2 即算法输出解 C 的期望值至多是期 武汉科技大学 组合数学 课程论文 第 4 页 望权重的 B 倍 证明证明 首先通过在集合覆盖实例上做的一个游戏来描述定理的证明 假设 集合覆盖实例在开始时 每个的初始资本为 这些权重是在算法执行之 前确定的 那么 S 中集合所有的资本的总和正好是算法的输出结果的期望权重 假设存在一个全局策略 在该策略下 每个集合 s S 可以分配它的全部资 本到它所包含的元素上 并且每个元素能够从包含它的集合 即 L e 中接收到 相同数量的资本 然后 每个元素 e 向在中并且包含它的集合 即 归 还它所接收的资本 因此 如果 L e 中仅有一个集合 即 那么 所接收到的资本是它所分配给 e 的资本的倍 如果 那么 e 向中的每一个集合所归还的资本必然 少于该集合所分配给 e 的资本的倍 如果 L e 中所有的集合都在中 那么 e 向中的每一个集合所归还的资本恰好等于该集合所分配给 e 的 资本 不难看出 经过上述处理后 每个在中的集合的资本至多增加至原来资 本的倍 而没有在中的集合破产了 资本为 O 由此可以看出 现在 S 中的所有资本至多是开始时元素所拥有资本的 B 倍 因为每个集合 s 开始 时 所拥有的资本为 可以用下式表示 这个表达式与定理 2 中的表达式是等价的 现在唯一需要说明的是 上述把资本分配到元素的资本分配策略是存在的 为什么存在这样的分配策略呢 考虑每个集合 s S 如果它所包含的元素中有 一个把它选择到覆盖 C 中 那么它才会在覆盖 C 中 因此 集合 s 对于覆盖费 用的贡献的期望是由把它选择到 C 中的元素的贡献组成的 集合 s 中的元素以 一定的概率 P 把它选择到覆盖 C 中 从而对 C 的费用作出贡献 更进一步 元 素 e 对于 武汉科技大学 组合数学 课程论文 第 5 页 L e 中的集合的贡献大小为 由此可见 每个元素 e 对于 L e 中的集合的贡献是相同的 前面的论证是 利用分配策略以一种比较明显的方式把覆盖 C 的费用和最优覆盖的费用关联 起来 如果一个元素 e E 被算法 WSC RA 考虑到 然而还没有被覆盖时 则称该 元素为关键的 关键元素 e 使得算法从 L e 中随机地选择一个集合添加到 C 中 如果随机选择了 s 到 C 中 则 s 是因为关键元素 e 而被随机选择到 C 中 定义定义 3 3 对于任意元素 e E 和任意定义随机变量如下 注意到对于每个元素 e 有且仅有一个为非 o 而且对于任 意的集合 至多有一个它所包含的元素可以选择它到覆盖 C 中 因此有 由此可以得到 虽然对于 s 至多有一个为非零 但是它们的期望值都可以是非零的 因为 期望是建立在算法 WSC RA 对所有可能的选择的基础上 需要说明的是 对于任 意 任意 5 这个说明隐含了所期 望的分配策略的存在性 这是因为每个集合 s S 分配价值为的资本 给它所包含的元素 e 因而 每个元素可以从包含它的集合接收到相同价值的 资本 因此有以上的分配策略 武汉科技大学 组合数学 课程论文 第 6 页 定理定理 3 3 对于任意 e E 任意 s 证明证明 4 4 结束语结束语 武汉科技大学 组合数学 课程论文 第 7 页 给定图以及定义在顶点上的费用函数 W 所谓顶点覆盖 S 是顶点 集合的一个子集 满足对于每条边 u 和 v 至少有一个被 S 覆盖 最 小费用顶点覆盖问题是要求一个费用最小的顶点覆盖 把边集 E 看成要覆盖的 对象 每个顶点看成它所关联边的集合 这样顶点覆盖问题就转化成集合覆盖 问题 每条边包含在 2 个子集中 即 B 2 因此本文算法所求的顶点覆盖费用 的期望值不会超过最优顶点覆盖的 2 倍 参考文献参考文献 武汉科技大学 组合数学 课程论文 第 8 页 1 金银秋 最小覆盖算法及正确性证明 计算机应用与研究 1993 2 39 4t 2 宋恩民 求解析取范式永真性问题的