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.1 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 - задача решена с помощью локального поиска с начальным решением, полученным алгоритмом Бар-Иегуды-Эвена. Ячейки таблицы соответствуют времени в секундах, затраченному на работу каждого алгоритма.