Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению 01.03.02 Прикладная математика и информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Алгоритмы для задачи SET-COVER

Зандакова Ирина Ивановна

Нижний Новгород, 2020

Содержание

• Введение
• 1. Постановка задачи о покрытии множества

2. Обзор литературы

3. Приближенные алгоритмы

3.1 Жадный алгоритм

3.2 Алгоритм Бар-Иегуды-Эвена

4. Практическая часть

Заключение

Литература

Приложения

Введение

• Задача о покрытии множества широко известна в комбинаторике, информатике, исследовании операций и теории сложности и имеет множество применений. В 1972 году в своей работе R. Karp.Reducibility among combinatorial problems. Fifty Years of Integer Programming. 1972. 1958-2008. pp. 219-241. Р. Карп показал, что задача о покрытии множества, отвечающая на вопрос: “можно ли покрыть множество k подмножествами?” является NP-полной. Как NP-полная задача, задача о покрытии множества также является задачей, к которой сводится множество других задач дискретной оптимизации: задачи разбиения, стандартизации и упаковки множества, задача о наибольшей клике, задача минимизации полинома от булевых переменных и др. Более того, все перечисленные задачи можно свести обратно к задаче о покрытии множества. На практике необходимость использования данной задачи возникает при необходимости разместить пункты обслуживания, в системах информационного поиска, в проектировании интегральных схем и конвейерных линий и т. д. Такое широкое прикладное применение задачи о покрытии множества делает поиск способов повышения эффективности ее решения актуальным.
• В данной работе рассматривается взвешенная задача о минимальном покрытии множества, которая является NP-сложной. Эта задача является фундаментальной задачей дискретной оптимизации и за время ее существования было проведено множество исследований и предложено множество подходов к ее решению: начиная точными методами и заканчивая различными комбинациями метаэвристик. В данной работе внимание будет уделено приближенным алгоритмам решения задачи о покрытии множества. В последнее время исследователи все чаще решают задачу о покрытии эвристическими методами, полагая что приближенные алгоритмы исчерпали себя. Целью же данной работы является показать, что приближенные методы могут улучшить решения, полученные с помощью других подходов и что применение их может позволить за меньшее время найти лучшее решение.
• Для достижения поставленной цели были поставлены следующие задачи:

· изучить приближенные методы решения взвешенной задачи о минимальном покрытии множества;

· реализовать жадный алгоритм и алгоритм Бар-Иегуды - Эвена и сравнить их временную сложность;

· применить результаты, полученные жадным алгоритмом и алгоритмом Бар-Иегуды - Эвена, в других подходах решения задачи;

· показать улучшение качественных или временных характеристик по сравнению с решениями, полученными без применения решений, полученных с помощью приближенных алгоритмов.

1. Постановка задачи о покрытии множества

Задача о покрытии множества является широко известной задачей в дискретной оптимизации и имеет множество практических применений.

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

Для каждого подмножества мы устанавливаем в соответствие переменную , которая является индикатором взятия подмножества в покрытие (1 - множество входит в покрытие, 0 - нет). Таким образом, можно записать решение для задачи о покрытии множества как вектор .

Дано: множество из элементов, набор , , функция весов

Надо: минимизировать , с ограничениями: , ,

Определим частоту элемента как число подмножеств, содержащих этот элемент. Пусть - частота наиболее частого элемента.

В этой работе будет рассмотрено два алгоритма аппроксимации, которые достигают приближения или .

2. Обзор литературы

При написании данной работы были использованы научная и учебно-методическая литература, статьи из зарубежных периодических изданий, предоставленных электронными ресурсами библиотеки НИУ ВШЭ.

Задача о покрытии множества известна как NP-сложная задача. Как и для других задач этого класса, многие алгоритмы были усовершенствованы, чтобы дать приближенные решения с доказанными гарантиями эффективности.

Верхние оценки временной сложности точных методов сопоставимы со сложностью поисковых алгоритмов (Lifschitz and Pittel, 1983) Lifschitz V., Pittel B. (1983). The worst and the most probable performance of a class of set-covering algorithms. SIAM J. Cornput, 12. pp. 329-346.. В связи с этим при решении практических задач эвристические методы сокращения поиска становятся все более актуальными. Большое внимание уделяется разработке гибридных алгоритмов, в которых схемы поиска сочетаются с отсечками и различными эвристиками для получения верхних и нижних границ для оптимума целевой функции на вспомогательных подзадачах.

Балас и Хо были одними из первых, кто успешно применил метод ветвей и границ для задачи о покрытии с лагранжевой эвристикой в своей работе «Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study». Используя тот же подход, был предложен гибридный алгоритм ветвей и границ, который включает срезы Гомори, лагранжеву релаксацию и другие эвристики (Beasley and Jonsten, 1992) Beasley J.E., Jonsten K. (1992). Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58, pp. 293-300.

Основными источниками, раскрывающими фундаментальные основы приближенных алгоритмов, являлись работа Бар-Иегуды и Эвена «A linear time approximation algorithm for the weighted vertex cover problem» и работа Хватала «A Greedy Heuristic for the Set-Covering Problem и учебно-методическое пособие «Приближенные алгоритмы для NP-трудных задач А.В. Кононов, П.А. Кононова (2014). Приближенные алгоритмы для NP-трудных задач. Новосибирский гос. ун-т. -- Новосибирск: РИЦ НГУ.. В статье Бар-Иегуды и Эвена приводится более глубокое изучение взвешенной задачи о минимальном покрытии множества и предлагается алгоритм аппроксимации решения задачи о покрытии.

Коновалов, Фатхи и Кобак в работе «Применение генетического алгоритма для решения задачи покрытия множеств» сравнили жадный алгоритм, генетический алгоритм и модификацию генетического алгоритма, предложенную М.Х. Нгуен Нгуен М.Х.(2008). Применение генетического алгоритма для задачи нахождения покрытия множества // Динамика неоднородных систем. T. 33., Вып. 12. с. 206-219. Результаты исследования показали, что обе модификации генетического алгоритма намного превосходят жадный алгоритм по качественным показателям, однако по параметру трудоемкости выигрывает жадный алгоритм.

В своей статье Коновалов, Остапенко и Кобак И.С. Коновалов, С.С. Остапенко, В.Г. Кобак (2017). Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи о покрытии множества. Вестник Донского государственного технического университета №3(90), 137-144. провели сравнительный анализ точных и приближенных алгоритмов на примере метода ветвей и границ и генетического алгоритма. Результаты исследования показали, что генетический алгоритм гарантирует получение результата с незначительной погрешностью, но за определенный фиксированный промежуток времени.

В статье «A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem» Рафаэль Хассин и Асаф Левин впервые предлагают улучшение приближения жадного алгоритма. Приведенные результаты показали, что жадный алгоритм не является наилучшим для аппроксимации задачи о минимальном покрытии.

В работе «Solving Set Cover and Dominating Set via Maximum Satisfiability» Чжендун Лэй и Шаовэй Цай сформулировали задачу о покрытии множества и задачу о доминирующем множестве для взвешенной частичной максимальной выполнимости (Maximum Satisfiability) и предложили несколько правил сокращения, чтобы упростить эти экземпляры MaxSAT. Также они разработали алгоритм локального поиска, адаптированный для таких случаев. Результат экспериментов показал, что этот алгоритм лучше, чем все современные алгоритмы для задачи о покрытии множества, задачи о доминирующем множестве и MaxSAT.

3. Приближенные алгоритмы

В математике, компьютерной науке и экономике оптимизационная задача - это задача поиска наилучшего решения из всех возможных решений. Постановка любой задачи оптимизации начинается с определения набора независимых переменных, определения области допустимых значений этих переменных. Обычно оптимизируется скалярная мера качества, которая зависит от переменных (целевая функция). Решение оптимизационной задачи - это приемлемый набор значений переменных, которому отвечает оптимальное решение целевой функции. Под оптимальным решением понимают максимальность или минимальность целевой функции.

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

(1)

для любого экземпляра задачи . - обозначение для оптимального веса задачи.

Пусть - это задача оптимизации с неотрицательными весами, . Полиномиальный алгоритм для задачи называется -приближенным алгоритмом (-factor approximation algorithm), если

(2)

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

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

3.1 Жадный алгоритм

Джонсон D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences. 1974. Vol. 9. pp. 256-349 и Ловас L. Lovбsz. On the ratio of optimal integral and fractional covers. Discrete Mathematics. 1975. Vol. 13. pp. 383-390 предложили простой жадный алгоритм для задачи о минимальном покрытии множества: на каждой итерации следует брать множество, которое покрывает максимальное количество еще не покрытых элементов. Хватал V. Chvatal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research. 1979. Vol. 4, No. 3. pp. 233-235 обобщил этот алгоритм на взвешенный случай.

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

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

Жадный алгоритм:

Присвоить U =0 и W=0

While W?U do:

Выбрать множество U для которого и минимально.

Присвоить U =U и

Очевидно, что время работы такого алгоритма составляет , где - это количество элементов в универсуме, а -количество подмножеств. Можно доказать следующую оценку погрешности:

Теорема 3.1.1. B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms. 2006. Springer-Verlag Berlin Heidelberg. Для любого экземпляра задачи о минимальном взвешенном покрытии множества жадный алгоритм находит покрытие, вес которого не превосходит , где - максимальная мощность подмножества среди всех , .

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

Для каждого определим - номер итерации, на которой элемент будет покрыт. Положим



Фиксируем подмножество и положим . Имеем

благодаря выбору на шаге (заметим, что при ). Обозначив , получим:

Поскольку , получаем

Просуммируем по всем из оптимального покрытия и получим

Более точный анализ погрешности невзвешенного случая приведен в работе Славика P. Slavik. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms. 1997. Vol. 25. pp. 237-254. Раз и Сафра 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 29^th Annual ACM Symposium on Theory of Computing. 1997. pp. 475-484 установили, что найдется такая константа , что при не существует алгоритма с оценкой погрешности . В действительности оценка погрешности не может быть достигнута при , если только не окажется, что всякая -сложная задача может быть решена за время U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM. 1998. Vol. 45. pp. 634-652.

3.2 Алгоритм Бар-Иегуды-Эвена

Задачу о покрытии множества можно представить в виде целочисленной задачи линейного программирования (ILP):

с ограничениями:

Первое ограничение гарантирует, что каждый элемент универсума будет покрыт хотя бы одним подмножеством. Второе ограничение - индикатор того, будет ли включено подмножество в покрытие.

Путем применения линейной релаксации можно ослабить ограничение, действующее на переменные . Теперь задача линейного программирования (LP) выглядит следующим образом:

Оптимизация в этих задачах соотносится следующим образом:

Пусть оптимальное решение LP задачи о покрытии множества. Применив округление, можем получить решение для ILP задачи.

Однако возникает проблема: если просто округлить решение вверх, то целевая функция задачи сильно возрастет. В таком случае необходимо дополнительное условие:

где кратность элемента , то есть количество множеств из в которые входит этот элемент. Пусть .

Теперь докажем, что после перехода к решению задачи ILP каждый элемент остается покрытым. В условии ILP

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

поскольку не более, чем в раз больше, чем . Следовательно,

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

Этот алгоритм поиска приближенного решения состоит из двух этапов:

1. запустить LP-solver для линейной программы полиномиального размера

2. округлить решение

В свой работе Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Вып. 20. № 1. С. 51-68. Хачиян доказал, что задачи линейного программирования можно решить за полиномиальное время. Исходя из этого временная сложность такого алгоритма решения задачи о покрытии также полиномиальна: необходимо сначала запустить LP-solver и затем за линейное время округлить полученное решение. Проблема такого подхода к решению задачи о покрытии множества в том, что приходится пользоваться методами для решения задачи линейного программирования, которые работают за полиномиальное время. Поэтому возникает необходимость решить эту задачу более эффективно.

К каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной задаче, называемой прямой задачей. Запишем двойственную задачу для LP задачи о покрытии множества:

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

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

Теорема 3.2.2. Допустимые решения и прямой и двойственной задач соответственно оптимальны тогда и только тогда, когда выполняются следующие условия дополнительной нежесткости:

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

Расслабленное условие дополняющей нежесткости:

Таким образом, если будут найдены какие-либо две точки и , удовлетворяющие расслабленным условиям дополняющей нежесткости, для некоторых и , то это будет источник для приближения как в прямой, так и в двойственной задачах, с коэффициентом .

Теорема 3.2.3. Пусть и - решения для соответствующих задач линейного программирования. Если выполнены расслабленные условия дополняющей нежесткости и , то .

Доказательство.

Подход Primal-Dual применим ко многим задачам дискретной оптимизации. Такой подход позволяет заметно улучшать качество и уменьшать временные затраты алгоритмов решения различных задач, однако он требует более глубокого изучения задач.

Primal-dual метод лежит в основе разработки алгоритмов для задач комбинаторной оптимизации. Основная идея, заключающаяся в венгерском алгоритме H.W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly. 1955. Vol. 2. pp. 83-97., была расширена и формализована группой ученых G.B. Dantzig, L.R. Ford and D.R. Fulkerson. A primal-dual algorithm for linear programs. In H. W. Kuhn and A. W. Tucker, editors, Linear Inequalities and Related Systems. 1956. Vol. 38. pp. 171-181. Princeton University Press, Princeton. как общая основа для линейного программирования и, таким образом, она стала применимой к широкому кругу задач. Несколько десятилетий спустя Бар-Иегуда и Эвен 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. стали первыми, кто применил метод primal-dual к разработке алгоритмов аппроксимации. Впоследствии эта парадигма была применена для получения приближенных алгоритмов для широкого набора NP-сложных задач.

В этом разделе будет рассмотрен алгоритм Бар-Иегуды - Эвена, который применим к общей задаче о минимальном взвешенном покрытии множества.

Общий вид задач линейного программирования выглядит следующим образом:

Дано: матрица и вектор-столбцы

Надо: найти такой вектор-столбец , что и значение - максимально, либо выяснить, что множество пусто, либо определить, что для всех найдется такой вектор-столбец , что и .

Здесь обозначает скалярное произведение векторов. Запись для векторов и (одинаковой размерности) означает, что указанное неравенство выполняется покоординатно. Если размеры матриц и векторов не указаны, то всегда предполагается что они равны друг другу (в смысле операции умножения).

Линейная программа представляет собой экземпляр вышеуказанной задачи. В дальнейшем они будут записаны в виде . Допустимым решением линейной программы называется такой вектор , что . Допустимое решение, доставляющее искомый максимум, называется оптимальным решением.

Для доказательства теоремы 2 нам понадобится следующее утверждение.

Утверждение 3.2.4. Пусть и - допустимые решения линейных программ

(1.1)

(1.2)

соответственно. Тогда .

Доказательство. Имеем

Алгоритм Бар-Иегуды - Эвена:

Присвоить U и

Присвоить для всех

Присвоить для всех

While do:

Выбрать элемент

Пусть , причем и значение минимально

Присвоить

Присвоить для всех таких , что

Присвоить U =U и

Теорема 3.2.5.¹ B. Korte, J. Vygen. Combinatorial Optimization. Theory and Algorithms. 2006. Springer-Verlag Berlin Heidelberg. Для любого экземпляра задачи о минимальном взвешенном покрытии множества алгоритм Бар-Иегуды - Эвена находит покрытие, вес которого не превосходит , где - частота наиболее частого элемента множества .

Доказательство. Задача о минимальном взвешенном покрытии множества может быть записана в виде целочисленной задачи линейного программирования:

где строки матрицы соответствуют элементам множества , а столбцы соответствуют векторам инцидентности множеств из . Оптимум линейной релаксации:

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



также будет нижней оценкой для .

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

Наконец, заметим, что

Очевидно, что доказательство теоремы 2 использует методы линейного программирования, однако сам алгоритм Бар-Иегуды - Эвена не включает в себя решение задачи линейного программирования.

Теорема 3.2.6. Сложность алгоритма Бар-Иегуды - Эвена по времени выполнения линейна и равна

afghan refugee distress discrimination

4. Практическая часть

Исследовательская часть данной работы была выполнена в среде разработки Jupyter Notebook, так как данная среда позволяет интерактивно работать с кодом непосредственно в браузере, что позволяет быстро выполнять различные куски кода и сразу же их корректировать. Для работы с данными был выбран язык программирования Python 3.7.0., поскольку в нем имеется множество инструментов для анализа данных.

Очевидно, что задавать матрицу задачи каждый раз это неудобный и долгий процесс, поэтому для тестирования рассматриваемых алгоритмов мной был написан программный код, реализующий генерацию различных матриц задачи о покрытии множества с размерами MxN, где M - количество элементов в универсуме, а N - количество подмножеств, среди которых необходимо найти минимальное покрытие. Матрицы генерируются таким образом, что для каждой сгенерированной матрицы обязательно найдется решение, то есть в каждой строке имеется хотя бы одна ячейка со значением 1, то есть каждый элемент по крайней мере входит в какое-то одно подмножество. Также в каждом столбце имеется хотя бы одна ячейка со значением 1, то есть каждое подмножество не пусто и покрывает как минимум один элемент. Это сделано для того, чтобы в каждой задаче было конкретное заданное количество непустых подмножеств.

Были реализованы рассматриваемые алгоритмы: жадный алгоритм и алгоритм Бар-Иегуды-Эвена. На вход подается матрица задачи и список весов подмножеств. Пример решения задачи жадным алгоритмом можно увидеть на рисунке 3. Решение такой же задачи методом Бар-Иегуды-Эвена - на рисунке 4.

Исходя из полученных результатов можно сказать, что на задачах небольших размерностей оба алгоритма могут давать одинаковые решения. На этом же наборе данных точный алгоритм (bruteforce) дал такое же решение, что говорит о том, что на задачах небольших размерностей алгоритмы могут давать точное решение.

Рисунок 1. Матрица, подаваемая на вход

Рисунок 2. Веса подмножеств

Рисунок 3. Решение задачи жадным алгоритмом

Рисунок 4. Решение задачи алгоритмом Бар-Иегуды-Эвена

Были сравнены временные возможности решения задачи с помощью симплекс метода, жадного алгоритма и алгоритма Бар-Иегуды-Эвена. В таблице 1 содержатся данные о среднем времени работы алгоритмов на матрицах различных размерностей. Для этих экспериментов были сгенерированы матрицы со средней плотностью, вероятность появления в матрице единиц и нулей одинакова и равна 0,5. На рисунке 5 представлены графики роста затрачиваемого времени с ростом размерности матриц.

Таблица 1.

Рисунок 5.

На рисунке 5 очень наглядно продемонстрировано, что время работы симплекс метода растет экспоненциально и во много раз превосходит время работы жадного алгоритма и алгоритма Бар-Иегуды-Эвена. На рисунке 6 представлены те же графики, но в приближенном масштабе, чтобы оценить и сравнить алгоритмы жадный и Бар-Иегуды-Эвена.

Рисунок 6.

На рисунке 6 видно, что временная сложность жадного алгоритма растет быстрее, чем сложность алгоритма Бар-Иегуды-Эвена. Это может быть обусловлено тем, что поскольку время работы жадного алгоритма составляет , а время работы алгоритма Бар-Иегуды-Эвена оценивается как , то есть оно линейно и зависит от суммарной мощности всех подмножеств, то на разреженных графах алгоритм Бар-Иегуды - Эвена будет работать быстрее, чем жадный алгоритм. Однако, оценивая время работы жадного алгоритма на данных больших размеров можно сделать вывод о том, что алгоритм работает все еще достаточно быстро.

Основная цель работы - показать, что приближенные алгоритмы могут быть полезными в комбинации с другими подходами к решению задачи о минимальном покрытии множества. Для сравнения был реализован локальный поиск для решения задачи о покрытии. Сравнивались результаты работы алгоритма с различными начальными решениями - (1) на вход подавался вектор длины N, заполненный единицами и (2) на вход подавался вектор решения, полученного с помощью рассматриваемых приближенных алгоритмов.

Для задачи с матрицей, изображенной на рисунке 7, функция локального поиска достигла локального минимума с решением [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] с весом 19 за 48 итераций.

Рисунок 7.

Для той же задачи в качестве начального решения положили решение, полученное с помощью жадного алгоритма: [0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], вес этого решения составляет 16, время работы составило 0.000998 секунд. Функция локального поиска не смогла улучшить это решение, достигая решений с таким же весом.

Решение этой же задачи, полученное с помощью алгоритма Бар-Иегуды-Эвена: [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] с весом 21. Положив его в качестве начального решения в алгоритм локального поиска получаем: вес нового решения составил 14, полученное решение - [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. Алгоритм смог добиться оптимального решения за 21 итерацию.

В таблице 2 представлена серия экспериментов, в которых для каждой матрицы решения были найдены с помощью локального поиска, жадного алгоритма и алгоритма Бар-Иегуды-Эвена. Столбцы соответствуют значениям: local - задача решена с помощью локального поиска, local+greedy - задача решена с помощью локального поиска с начальным решением, полученным жадным алгоритмом, local+bar - задача решена с помощью локального поиска с начальным решением, полученным алгоритмом Бар-Иегуды-Эвена. Ячейки таблицы соответствуют времени в секундах, затраченному на работу каждого алгоритма.

Таблица 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

Размещено на Allbest.ru

...