集合覆盖问题-线性规划求解-python实现
基于贪⼼思想的近似算法是⽬前常⽤的解决集合覆盖问题的算法，⽹上也有很多相关的实现代码。
除此之外，线性规划其实也能够解决集合覆盖问题，之所以不常⽤是因为算法效率相对贪⼼算法较低（具体原理这⾥不再解释），下⾯对⽐分析两个算法在解决集合覆盖问题上的性能。
1. ⾸先⽣成符合条件的集合和⼦集族
⽣成集合
# ⽣成⼤⼩固定的集合X，利⽤python内置函数set能避免集合元素重复问题
X =set()
for n in range(1000):
X = random.sample(range(1,10000), n)
print('集合X中元素个数：',len(X))
print('集合X：', X)
⽣成相应的⼦集族
# ⽣成⼦集族
"""
⼦集族⽣成规则：
先⽣成能够覆盖集合X中全部元素的⼦集族，
若要求⼦集族中⼦集的个数和集合X中元素个数相同，
则剩下的⼦集族随机⽣成。
具体⽣成规则可根据要求⾃⼰设计
"""
S0 = random.sample(X,20)
n1 = random.randint(1,20)
x1 = random.randint(1, n1)
# 从前⾯的已⽣成的⼦集中抽取x元素，从剩下未被抽中的集合中抽取n-x元素
S1 =(random.sample(set(S0), x1))+(random.sample(set(X)-set(S0), n1-x1))
Sub_set =[S0, S1]
for item in range(2, n):
S_item_len = random.randint(1,20)
S_last_len = random.randint(1, S_item_len)
Sub_set_item =list(chain.from_iterable(Sub_set))# 压平嵌套列表
if len(set(X)-set(Sub_set_item))>= S_item_len-S_last_len:
# 当前循环⽣成的⼦集
S_now =(random.sample(set(Sub_set_item), S_last_len))+(random.sample(set(X)-set(Sub_set_item), S_item_len-S_last_len)) # 所有⼦集组成的⼦集族
Sub_set.append(S_now)
else:
Sub_set.append(list(set(X)-set(Sub_set_item)))
break
# print(set(X)-set(list(chain.from_iterable(Sub_set))))
# 检查集合中的元素是否已被⼦集族全覆盖
for j in range(n-len(Sub_set)):
select_num = random.randint(1,20)
select_sub = random.sample(X, select_num)
Sub_set.append(select_sub)
print('⼦集族：', Sub_set)
2. 调⽤python的plup包实现线性规划求解-为保证线性规划求解得到的⼦集族覆盖集合X，⽤线性规划中的舍⼊法作为判断是否保留某个
⼦集的判定准则。
# 求解线性规划问题
"""
# ⽬标函数：min CX  -----此问题中C取值为1
# 约束条件：AX>=B
# 定义C---⽬标函数的系数
"""
C =[1]*n
A =[[0for i in range(n)]for i in range(n)]
for i in range(len(X)):
for j in range(len(Sub_set)):
if X[i]in Sub_set[j]:
A[i][j]= A[i][j]+1
B =[1]*n
# 定义X
X =[pulp.LpVariable(f'x{i}', lowBound=0, upBound=1)for i in range(n)]
# 确定最⼤化最⼩化问题，最⼤化只要把Min改成Max即可
m = pulp.LpProblem(sense=pulp.LpMinimize)
m += pulp.lpDot(C, X)
# 设置约束条件
for i in range(len(A)):
m +=(pulp.lpDot(A[i], X)>= B[i])
m.solve()# 求解
object_result = pulp.value(m.objective)
result =[pulp.value(var)for var in X]
3. 完整代码如下
# 集合覆盖问题-线性规划算法
import time
import random
import pulp
from itertools import chain
import matplotlib.pyplot as plt
# ⽣成有限集X
X =set()
iter_ =[100,200,500]# ⽤于⽐较算法性能
time_cost =[]
for n in iter_:
start_t = time.clock()# 计算程序运⾏时间
X = random.sample(range(1,10000), n)
print('集合X中元素个数：',len(X))
print('集合X：', X)
# ⽣成⼦集
S0 = random.sample(X,20)
n1 = random.randint(1,20)
x1 = random.randint(1, n1)
# 从前⾯的⼦集中抽取x元素，从剩下的集合中抽取n-x元素
S1 =(random.sample(set(S0), x1))+(random.sample(set(X)-set(S0), n1-x1))    Sub_set =[S0, S1]
for item in range(2, n):
S_item_len = random.randint(1,20)
S_last_len = random.randint(1, S_item_len)
Sub_set_item =list(chain.from_iterable(Sub_set))# 压平嵌套列表
if len(set(X)-set(Sub_set_item))>= S_item_len-S_last_len:
# 当前循环⽣成的⼦集
# 当前循环⽣成的⼦集
S_now =(random.sample(set(Sub_set_item), S_last_len))+(random.sample(set(X)-set(Sub_set_item), S_item_len-S_last_len)) # 所有⼦集组成的⼦集族
Sub_set.append(S_now)
else:
Sub_set.append(list(set(X)-set(Sub_set_item)))
break
# print(set(X)-set(list(chain.from_iterable(Sub_set))))
# 检查集合中的元素是否已被⼦集族全覆盖
for j in range(n-len(Sub_set)):
select_num = random.randint(1,20)
select_sub = random.sample(X, select_num)
Sub_set.append(select_sub)
print('⼦集族：', Sub_set)
# 计算X中每个元素的频率并返回最⼤频率f-⽤于舍⼊法判断
all_f =[0]*n
for i in range(len(X)):
for j in range(len(Sub_set)):
if X[i]in Sub_set[j]:
all_f[i]= all_f[i]+1
f =max(all_f)
# 求解线性规划问题
# ⽬标函数：min CX  -----此问题中C取值为1
# 约束条件：AX>=B
# 定义C---⽬标函数的系数
C =[1]*n
A =[[0for i in range(n)]for i in range(n)]
for i in range(len(X)):
for j in range(len(Sub_set)):
if X[i]in Sub_set[j]:
A[i][j]= A[i][j]+1
B =[1]*n
# 定义X
X =[pulp.LpVariable(f'x{i}', lowBound=0, upBound=1)for i in range(n)]
# 确定最⼤化最⼩化问题，最⼤化只要把Min改成Max即可
m = pulp.LpProblem(sense=pulp.LpMinimize)
m += pulp.lpDot(C, X)
# 设置约束条件
for i in range(len(A)):
m +=(pulp.lpDot(A[i], X)>= B[i])
m.solve()# 求解
object_result = pulp.value(m.objective)
result =[pulp.value(var)for var in X]
# 舍⼊法保留最终结果
for item in range(len(X)):
if result[item]>=1/f:
result[item]=1
else:
result[item]=0
final_set =[]
for item in range(len(Sub_set)):
if result[item]==1:
final_set.append(Sub_set[item])
print('可⾏解C：', final_set)
# 记录运⾏时间
end_t = time.clock()
time_iter = end_t-start_t
print("集合覆盖问题-基于动态规划运⾏时间", time_iter)
time_cost.append(time_iter)
print('\n')
random python# 结果可视化
plt.plot(iter_, time_cost)
plt.show()
3. 程序运⾏结果
横轴为X中元素个数，纵轴为算法运⾏时间，可与相同集合⼤⼩时的贪⼼算法性能做对⽐。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。