УДК 519.8

Сравнение эффективности работы жадных алгоритмов для задачи о покрытии множества

Кулакова Мария Алексеевна – магистрант Московского государственного университета им. М.В. Ломоносова

Аннотация: В статье рассматривается стандартная задача о покрытии множества минимальной мощности в невзвешенном случае. Рассматриваются свойства булевой матрицы, при выполнении которых жадные алгоритмы могут давать решение более близкое к оптимальному. Данная задача является NP-сложной, поэтому поиск оптимального решения в матрицах большого размера является затруднительным. Для поиска приближенного решения задачи представлено несколько видов жадных алгоритмов. Было проведено сравнение эффективности приведенных алгоритмов по времени их работы и по мощности получаемого покрытия в зависимости от размеров и плотности матрицы. Для повышения эффективности по проверке построения полного покрытия приведена новая постановка задачи с введением дополнительного вектора y.

Ключевые слова: дискретная оптимизация, целочисленное программирование, задача о минимальном покрытии множества, жадный алгоритм, эвристический алгоритм.

Введение

Поиск оптимального решения задачи оптимизации часто является очень сложной задачей, зависящей от выбора и правильного использования правильного алгоритма. Выбор алгоритма может зависеть от типа задачи, доступности алгоритмов, вычислительных ресурсов и временных ограничений. Комбинаторная задача о покрытии множества широко известна в дискретной оптимизации, у нее существует множество различных трактовок и многочисленных приложений. [4] В последние дни появляется все больше актуальных задач из реальной жизни, которые могут быть сформулированы в виде дискретных оптимизационных задач, в частности, в виде задач о покрытии множества. Исследуемая задача является NP-сложной, так как она обобщает NP-полную задачу о вершинном покрытии. В связи с этим пока неизвестно точного алгоритма, который будет решать поставленную задачу за полиномиальное время.

Существует две основные группы методов для решения задач дискретной оптимизации — это точные и эвристические [3][5]. Их разница состоит в том, что точные алгоритмы решения могут гарантированно давать оптимальное решение задачи, в то время как эвристические дают только приближенное решение.

Перед формулировкой задач следует ввести следующие определения:

Определение: Покрытие – это такой набор столбцов матрицы A, в котором каждая строка матрицы A в пересечении хотя бы с одним столбцом из покрытия дает 1.

Определение: Покрытие называется неприводимым, если любое собственное подмножество покрытия не является покрытием матрицы А.

Определение: Покрытие называется минимальным, если оно является покрытием минимальной мощности.

В стандартной формулировке задачи о наименьшем покрытии фигурирует матрица A, размера m×n. Помимо квадратных матриц также рассматриваются матрицы, у которых количество строк (или столбцов) значительно превосходит количество столбцов (строк). В настоящей работе рассматривалась частная задача с единичными весами , которая имеет свою специфику. Необходимо найти такой набор столбцов, который покроет все строки матрицы A, минимальной мощности.

Условие , где x – набор выбранных столбцов, вектор, полностью состоящий из единиц, означает, что все строки матрицы A будут покрыты данными столбцами. Данное условие было мной переформулировано для использования в дальнейшем. Введем вектор-столбец у, размера m, состоящий из нулей и единиц, в котором на i-ой компоненте стояла 1 в случае, если . Исходя из этого вводится ограничение, что скалярное произведение векторов Ax и y равняется 0. По постановке задачи известно, что для построения покрытия необходимо, чтобы в выбранных столбцах в каждой строке присутствовала хотя бы одна единица, то есть . Следовательно, нужно минимизировать сумму компонент y. Этот минимум будет достигнут в нулевом векторе θ тогда, когда будет построено полное покрытие матрицы A.

Благодаря этому вектору при решении задачи с помощью программы покрытые строки можно будет не удалять из матрицы (тем самым меняя и редуцируя ее), а маскировать при помощи вектора y.

Постановка задачи

Стандартная задача о покрытии множества в матричном виде звучит следующим образом. Дана булева матрица A, размера m×n. Нужно найти минимальное покрытие столбцами строк матрицы, т. е. нужно найти такие k столбцов, что каждая строка матрицы A будет иметь хотя бы одну единицу в выбранных k столбцах. В терминах линейного булевого программирования:

Введем вектор столбец y (зависящий от x) у которого будут стоять значения 0 в тех местах, где у вектора Ax стоят ненулевые компоненты, т. е. скалярное произведение этих векторов будет равно 0. И перепишем условие для , используя вектор y. Когда будет выполнено данное условие (будет построено покрытие), то вектор y будет являться нулевым вектором. В терминах линейного булевого программирования:

Свойства матрицы A. В случае невзвешенной задачи о покрытии, в виду ее особого вида, при исследовании матрицы A можно произвести некоторые упрощения для задачи, подробнее о них [2].

Утверждение 1. случае, если в матрице A присутствует строка, полностью состоящая из 0, то из этого следует, что данную строку нельзя покрыть ни одним столбцом, а значит задача не имеет решения.

Утверждение 2 (Процедура редукции). Пусть в матрице A есть строки, в которых присутствует только одна единица. Не ограничивая общности, предположим, что таковой является i-ая строка. Тогда для того, чтобы покрыть i-ую строку, в покрытие точно необходимо взять столбец j, у которого на пересечении с i-ой строкой стоит единица.

При решении задачи, пользуясь утверждением 2, можно провести процедуру редукции и сразу отобрать в покрытие столбцы, которые покрывают строки с единственной единице. При этом взятые столбцы с большой долей вероятности покрывают и другие строки, тем самым мы упростим задачу, снизив ее размерность.

Для того чтобы осуществить редукцию необходимо посчитать сумму единиц в каждой строке матрицы, после чего отобрать те строки, в которых эта сумма равняется единице. Для получения вектора x, т. е. набор выбранных в покрытие столбцов, нужно логически сложить выбранные строки. Далее построение покрытия может начинаться не с нулевого вектора, а с построенного после применения редукции.

Для следующего утверждения необходимо ввести понятие доминирования столбцов.

Определение: Столбец j матрицы A называется доминирующим над столбцом k, если . Столбец k в таком случае называется доминируемым.

Утверждение 3 (Процедура проверки на доминирование). Пусть в матрице A присутствует доминирование столбцов, в таком случае для построения минимального покрытия следует убрать множество доминируемых столбцов.

Процедуру проверки на доминирование столбцов матрицы можно проводить после каждого включения столбца в покрытие, потому что после покрытия данным столбцом строк, могут появиться новые доминирующие столбцы. Например, пусть в матрице есть столбцы i = (1, 1, 1, 0, 0, 0) и

j = (1, 0, 1, 0, 0, 1). Изначально ни один из столбцов не доминирует над другим и оба столбца имеют в себе одинаковое количество единиц. Теперь пусть в какой-то момент построения покрытия оказалась покрыта последняя строка, в этот момент вектор y имеет вид y = (1, 1, 1, 1, 1, 0). В этом случае возникает ситуация доминирования столбцом i над столбцом j. Для проверки на доминирование необходимо проверить логическое условие: пусть y – вектор размерности m, показывающий какие строки покрыты на данный момент, т. е. у него стоят 0 напротив тех строк, которые покрыты, и 1 в противном случае. Векторы i и j – столбцы размерности m, которые нужно проверить на доминирование. Если верно условие , где AND – логическое умножение, тогда верно, что столбец i доминирует столбец j.

Жадные алгоритмы. Для решения поставленной задачи были рассмотрены различные варианты жадного решения. Принцип его работы изложен в работе [1] Простейшим из них является, так называемый, Next-Fit или NF, который заключается в следующем:

• Осуществляется перебор столбцов слева направо;
• Если в j-ом столбце стоит единица в еще непокрытой i-ой строке, то данный столбец берется в покрытие;
• Перебор происходит до тех пор, пока не будет построено полное покрытие матрицы.

Данный алгоритм работает за константное время, в худшем случае за линейное время. Для приближения к оптимальному решению следует применять обратный ход, который заключается в переборе всех столбцов в построенном покрытии и в случае, если можно убрать столбец, при этом, если оставшиеся будут продолжать образовывать полное покрытие, то данный столбец можно убрать. Обратный ход работает за линейное время, зависит от числа столбцов в матрице. Очевидно, что покрытие, построенное алгоритмом NF не будет являться оптимальным, при этом в худшем случае оно может быть бесконечно далеким от оптимального.

Для улучшения алгоритма можно отсортировать все столбцы с учетом количества единиц и к полученной матрице применить Next-fit. Данный алгоритм имеет название Next-Fit-Decreasing или NFD. При этом стоит учитывать, что быстрая сортировка имеет в среднем сложность O(n ln n). Как и для NF верно утверждение, что NFD может построить бесконечно далекое от оптимального решение.

Классическим жадным алгоритмом является Best-Fit или BF, его отличие от NF заключается в том, что на каждой итерации выбирается столбец с максимальным числом непокрытых строк.

Однако возможна ситуация, когда существует не один, а множество столбцов с максимально количество непокрытых строк. В таком случае, для алгоритма BF нет разницы какой из таких столбцов брать. Учитывая данное замечание, для улучшения решения была предложена модификация, которая состоит в том, чтобы брать столбец, который покрывает более редкие строки. Например, если в какой-то строке стоит только 1 единица, то для оптимального покрытия необходимо взять столбец, в котором стоит данная единица (как в процедуре редукции). Далее, если в строке стоят две единицы, то в покрытие мы точно должны взять один (или возможно оба) из этих столбцов. И так далее. Для этого вводится вектор  который содержит в себе сумму по каждой строке. Данный алгоритм в моей работе имеет название Best-fit-with-min-weights или BFW_Min. По времени выполнения BFW_Min сравним с BF.

Результаты экспериментов

Для сравнения эффективности приведенных жадных алгоритмов были написаны программы на языке Python и проводились эксперименты по поиску минимального покрытия при помощи данных программ. Для более достоверных результатов каждый алгоритм применялся к разным матрицам фиксированного размера 10 раз, после чего бралось среднее время работы и средняя мощность полученного покрытия. В работе алгоритмы были применены к различающимся по плотности булевым матрицам, которые были сгенерированы псевдослучайным образом с помощью равномерного распределения.

По итогам экспериментов для алгоритмов типа NF (рассматривались алгоритмы NF, NFD без модификаций, с применением операции редукции и с применением редукции и процедуры обратного шага) лучший результат по мощности покрытия последние из перечисленных, при этом алгоритм NFD за счет сортировки показывает гораздо худшее время работы. Поэтому при использовании алгоритмов данного типа стоит использовать алгоритм NF с использованием обратного шага и редукции.

Для сравнения алгоритмов типа BF были рассмотрены BF, BFW_Min без и с применением операции редукции. Алгоритмы, использующие редукцию, не только работают быстрее при увеличении строк в матрице (в виду того, что сокращается количество строк, которые необходимо покрыть), но и дают меньшее по мощности покрытие. В связи с этим для поиска приближенного решения задачи стоит использовать алгоритм BFW_Min с использованием редукции.

Данную задачу возможно решить, используя методы линейного программирования и метод ветвей и границ. Для поиска оптимального решения был использован пакет cvxpy и решатель использующий пакет GLPK_MI. Но все же при увеличении размеров матрицы и количества единиц, время работы недетерминированно увеличивается, а в некоторых случаев и вовсе не может справиться с решением. Чтобы сравнить насколько близки полученные с помощью жадных алгоритмов решения с оптимальным, был проведен эксперимент с матрицей, у которой количество столбцов n = 300 и количеством столбцов m от 1000 до 8500. Ко всем алгоритмам была применена операция редукции, для алгоритмов типа NF был применен обратный шаг.

Таблица 1. Зависимость времени работы алгоритмов при количестве столбцов = 300 с вероятностью появления единицы в матрице = 1/80.

Кол-во столбцов	Среднее время работы, с
	Optimal	NF	NFD	BF	BFW_Min
1000	2.014	0.128	0.172	0.084	0.078
3500	3.897	0.353	0.892	0.074	0.085
6000	6.707	0.667	1.429	0.047	0.061
8500	9.434	1.046	2.375	0.031	0.030

Таблица. 2 Зависимость мощности покрытия при количестве столбцов = 300 с вероятностью появления единицы в матрице = 1/80.

Кол-во столбцов	Средняя мощность покрытия
	Optimal	NF	NFD	BF	BFW_Min
1000	155.9	169.0	165.2	160.9	159.6
3500	244.2	248.9	249.3	245.4	245.2
6000	275.8	276.4	276.6	275.8	275.8
8500	289.0	289.2	289.0	289.0	289.0

При анализе таблицы 1 видно, что время поиска оптимального решения при увеличении количества столбцов растет значительно быстрее, чем время работы жадных алгоритмов. Из данных таблицы 2 заметно, что из жадных алгоритмов лучшие результаты показывает алгоритм BFW_Min.

Список литературы

1. Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ – 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. – С. 889-892.
2. Кристофидес Н. Теория графов. Алгоритмический подход // М.: Мир, 1978. – С. 53-65.
3. Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. – 2000. – Т. 7. – №. 2. – С. 22-46.
4. Корбут А. А., Финкельштейн Ю. Ю. Дискретные задачи математического программирования // Итоги науки и техники. Серия «Теория вероятностей. Математическая статистика. Теоретическая кибернетика». – 1967. – № 0. – С. 59-108.
5. Кононов А.В. Приближенные алгоритмы для NP-трудных задач: учеб.-метод. пособие /А.В. Кононов, П.А. Кононова; Новосиб. гос. ун-т. Новосибирск: РИЦНГУ, 2014. 117 с.