Дипломная работа: Алгоритмы для задачи SET-COVER

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

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

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

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

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

Программа подготовки бакалавров по направлению 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.