Таблица 2.
На рисунке 8 приведены графики роста времени затраченного на работу алгоритма с увеличением размерности задачи.
По результатам серии экспериментов видно, что применение приближенных алгоритмов помогло снизить затрачиваемое время в огромное количество раз.
Рисунок 8.
В таблице 3 приведены результаты серии экспериментов, в которых также решались задачи с разными размерностями. Столбцы здесь соответствуют столбцам из таблицы 2. В ячейках содержится информация о весе решений, полученных различными способами.
Таблица 3.
Исходя из результатов проведенных экспериментов, можно сделать вывод, что приближенные алгоритмы могут существенно улучшить как временные, так и качественные показатели локального поиска для решения задачи о покрытии множества.
Заключение
Основываясь на результатах проведенных экспериментов, можно сделать вывод о том, что приближенные алгоритмы решения задачи о покрытии могут существенно улучшить решение задачи, получаемые с помощью других подходов. Таким образом, цель данной работы - показать практическую ценность приближенных алгоритмов - достигнута.
В дальнейших исследованиях возможно применение алгоритмов аппроксимации к другим подходам решения взвешенной задачи о минимальном покрытии множества, например, различные метаэвристики.
Литература
1. R. Karp.Reducibility among combinatorial problems. Fifty Years of Integer Programming. 1972. 1958-2008. pp. 219-241.
2. D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences. 1974. Vol. 9. pp. 256-349.
3. L. Lovбsz. On the ratio of optimal integral and fractional covers. Discrete Mathematics. 1975. Vol. 13. pp. 383-390.
4. V. Chvatal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research. 1979. Vol. 4, No. 3. pp. 233-235.
5. P. Slavik. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms. 1997. Vol. 25. pp. 237-254.
6. R.Raz, S. Safra. A sub constant error probability low degree test, and a sub constant error probability PCP characterization of NP. Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 1997. pp. 475-484.
7. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM. 1998. Vol. 45. pp. 634-652.
8. H.W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly. 1955. Vol. 2. pp. 83-97.
9. G.B. Dantzig, L.R. Ford and D.R. Fulkerson. A primal-dual algorithm for linear programs. In H.W. Kuhn, A.W. Tucker, editors, Linear Inequalities and Related Systems. 1956. Vol. 38. pp. 171-181. Princeton University Press, Princeton.
10. R. Bar-Yehuda, S. Even. A linear time approximation algorithm for the weighted vertex cover problem. Journal of algorithms. 1981. Vol. 2. pp. 198-203.
11. V. Lifschitz, B. Pittel (1983). The worst and the most probable performance of a class of set-covering algorithms. SIAM J. Cornput, 12. pp. 329-346.
12. J.E. Beasley, K. Jonsten (1992). Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58, pp. 293-300.
13. R. Hassin, A. Levin (2005). A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem. SIAM Journal on Computing, Vol. 35(1). pp. 189-200.
14. S. Listrovoy S. Minukhin (2012). The solution algorithms for problems on the minimal vertex cover in networks and the minimal cover in Boolean matrixes. International Journal of Computer Science Issues, Vol. 9, Issue 5, No 3
15. Zhendong Lei, Shaowei Cai (2020). Solving Set Cover and Dominating Set via Maximum Satisfiability. Youth Innovation Promotion Association, Chinese Academy of Sciences
16. А.В. Кононов, П.А. Кононова (2014). Приближенные алгоритмы для NP-трудных задач. Новосибирский гос. ун-т. -- Новосибирск: РИЦ НГУ.
17. И.С. Коновалов, С.С. Остапенко, В.Г. Кобак (2017). Сравнение эффективности работы точных и при-ближенных алгоритмов для решения задачи о покрытии множества. Вестник Донского государственного технического университета №3(90), 137-144.
18. Нгуен М.Х. (2008). Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. T. 33., Вып. 12. с. 206-219
19. И.С. Коновалов, В.А. Фатхи, В.Г. Кобак (2016). Применение генетического алгоритма для решения задачи покрытия множеств. Вестник Донского государственного технического университета №3(86), 125-132.
Приложение 1
Код на Python для генерации случайных матриц для задачи о покрытии множества. В матрице - M строк (элементы универсума), N столбцов (подмножества)
def generate_matrix(M,N): # функция генерирующая случайные матрицы
matrix = [[random.random() for y in range(N)] for x in range(M)]
for i in range(M):
for j in range(N):
if matrix[i][j]>0.8:
matrix[i][j]=0
else:
matrix[i][j]=1
for i in range(M): # заполнить пустые строки
row_sum = 0
for j in range(N):
row_sum += matrix[i][j]
if (row_sum == 0):
matrix[i][random.randint(0,N-1)] = 1
for i in range(N): # заполнить пустые столбцы
column_sum = 0
for j in range(M):
column_sum += matrix[j][i]
if (column_sum == 0):
matrix[random.randint(0,M-1)][i] = 1
return matrix
Функция, преобразовывающая матрицу в список подмножеств:
def to_list(matrix):
a = []
for i in range(N):
c = []
for j in range(M):
if (matrix[j][i] == 1):
c.append(j)
a.append(c)
return a
Приложение 2
Функция, решающая задачу о минимальном взвешенном покрытии множества с помощью жадного алгоритма. На вход подаются матрица задачи, веса подмножеств и универсум:
def greedy(sample, weights, universe):
R = []
W = []
subsets = to_list(sample)
start_time = datetime.now()
while (W != universe):
num = 1000
for i in range(N):
cov_ability = len(list(set(subsets[i]) - set(W)))
if (cov_ability > 0):
number = weights[i]/cov_ability
if (number < num):
num = number
index = i
R.append(subsets[index])
W = list(set(W+subsets[index]))
timee = datetime.now() - start_time
return timee
Приложение 3
Функция, решающая задачу о минимальном взвешенном покрытии множества с помощью метода Primal-Dual (алгоритм Бар-Иегуды-Эвена). На вход подаются матрица задачи, веса подмножеств и универсум:
def bar_yehuda_even(sample,weights,universe):
R = []
W = []
y = [0]*M
c_s = weights
subsets = to_list(sample)
elems = list(set(universe) - set(W))
start_time = datetime.now()
while (len(elems)>0):
e = elems[0]
c = []
min = 100
for i in range (N):
if (sample[e][i] == 1):
if (c_s[i] < min):
min = c_s[i]
index = i
y[e] = c_s[index]
for i in range(N):
if (sample[e][i] == 1):
c_s[i] = c_s[i]-y[e]
R.append(index)
W = W + subsets[index]
elems = list(set(universe) - set(W)) # список непокрытых элементов
timee = datetime.now() - start_time
return time
Приложение 4
Решение взвешенной задачи о минимальном покрытии симплекс-методом с помощью библиотеки Pulp.
def lp_solver(sample,weights): # for task with 30 subsets
x = []
c = weights
x_lp = []
answer = []
start_time = datetime.now()
for i in range(N):
x.append(0)
x[i] = pulp.LpVariable("x %d" %i, lowBound = 0)
problem = pulp.LpProblem('0', pulp.LpMinimize)
problem += x[0]*c[0]+x[1]*c[1]+x[2]*c[2]+x[3]*c[3]+x[4]*c[4]+x[5]*c[5]+x[6]*c[6]+x[7]*c[7]+[8]*c[8]+x[9]*c[9]+x[10]*c[10]+x[11]*c[11]+x[12]*c[12]+x[13]*c[13]+x[14]*c[14]+x[15]*c[15]+x[16]*c[16]+x[17]*c[17]+x[18]*c[18]+x[19]*c[19]+x[20]*c[20]+x[21]*c[21]+x[22]*c[22]+x[23]*c[23]+x[24]*c[24]+x[25]*c[25]+x[26]*c[26]+x[27]*c[27]+x[28]*c[28]+x[29]*c[29], "Функция цели"
for i in range(M):
problem += x[0]*sample[i][0]+x[1]*sample[i][1]+x[2]*sample[i][2]+x[3]*sample[i][3]+x[4]*sample[i][4]+x[5]*sample[i][5]+x[6]*sample[i][6]+x[7]*sample[i][7]+[8]*sample[i][8]+x[9]*sample[i][9]+x[10]*sample[i][10]+x[11]*sample[i][11]+x[12]*sample[i][12]+x[13]*sample[i][13]+x[14]*sample[i][14]+x[15]*sample[i][15]+x[16]*sample[i][16]+x[17]*sample[i][17]+x[18]*sample[i][18]+x[19]*sample[i][19]+x[20]*sample[i][20]+x[21]*sample[i][21]+x[22]*sample[i][22]+x[23]*sample[i][23]+x[24]*sample[i][24]+x[25]*sample[i][25]+x[26]*sample[i][26]+x[27]*sample[i][27]+x[28]*sample[i][28]+x[29]*sample[i][29] >= 1
problem.solve()
for variable in problem.variables():
x_lp.append(variable.varValue)
# print (variable.name, "=", variable.varValue)
# print ("weight:")
# print (value(problem.objective))
for i in range(len(x_lp)):
if (x_lp[i] >= 1/f):
answer.append(1)
else: answer.append(0)
# print("cover:", answer)
# print ("Time :")
timee = datetime.now() - start_time
return time
Приложение 5
Точный алгоритм решения взвешенной задачи о минимальном покрытии множества (метод полного перебора)
def_weight = 1000
def_solution = [0]*10
for i in range(1024):
solution = list(mas[i])
cover = set()
for i in range(len(solution)):
if (solution[i] == 1):
cover = cover.union(set(subsets[i]))
if (cover == set(universe)):
weight = sum(list(np.array(weights)*np.array(solution)))
if (weight < def_weight):
def_weight = weight
def_solution = solution
Приложение 6
Локальный поиск решения задачи о минимальном покрытии множества
solution = [0]*N
for i in range(len(greedy_solution)):
solution[greedy_solution[i]] = 1
def change_solution(solution):
new_solution = solution.copy()
length_solution = len(new_solution)
node_to_change = random.randint(0, length_solution - 1)
new_solution[node_to_change] = abs(solution[node_to_change] - 1)
return new_solution
def is_covered(solution,subsets,universe):
cover = set()
for i in range(len(solution)):
if (solution[i] == 1):
cover = cover.union(set(subsets[i]))
if (cover == set(universe)):
flag = 1
else:
flag = 0
return flag
def local_search(solution,subsets,universe,weights):
weight = sum(list(np.array(weights)*np.array(solution)))
print('weight', weight)
new_solution = change_solution(solution)
print(new_solution)
if (is_covered(solution,subsets,universe)):
new_weight = sum(list(np.array(weights)*np.array(new_solution)))
if (new_weight < weight):
solution = new_solution
print('new weight', new_weight)
return solution
weight = 1000
for i in range(1000):
solution = local_search(solution,subsets,universe,weights)
weight_ = sum(list(np.array(weights)*np.array(solution)))
if (weight_ < weight):
weight = weight_
else: break