ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 5, с. 895-910
УДК 519.7
ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ АЛГОРИТМАХ ДУАЛИЗАЦИИ1)
© 2015 г. Е. В. Дюкова, П. А. Прокофьев
(119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: edjukova@mail.ru;p_prok@mail.ru Поступила в редакцию 29.10.2014 г.
Изучаются вопросы синтеза эффективных в типичном случае алгоритмов для дискретных перечислительных задач. Рассматривается одна из центральных перечислительных задач — задача дуализации. Построены новые асимптотически оптимальные алгоритмы дуализации. Показано, что эти алгоритмы требуют меньших временных затрат по сравнению с ранее построенными асимптотически оптимальными алгоритмами дуализации, а также другими известными алгоритмами дуализации, имеющими иные конструктивные особенности. Библ. 20. Табл. 16.
Ключевые слова: дуализация, булева матрица, асимптотически оптимальный алгоритм, неприводимое покрытие, перечисление с полиномиальной задержкой.
Б01: 10.7868/80044466915050105
Рассматривается задача поиска неприводимых покрытий булевой матрицы. Пусть Ь = \\а^\т х п — булевая матрица, и пусть Н — набор столбцов матрицы Ь. Набор Нназывается покрытием матрицы Ь, если каждая строка матрицы Ь в пересечении хотя бы с одним столбцом из Ндает 1. Покрытие Н называется неприводимым, если любое собственное подмножество Н не является покрытием Ь.
Через ^(Ь) обозначается множество всевозможных неприводимых покрытий матрицы Ь. Требуется построить множество ^(Ь).
В теории алгоритмической сложности задача перечисления элементов ^(Ь) считается главной задачей перечисления и называется дуализацией. Существуют другие формулировки дуализации, в частности с использованием понятий теории булевых функций и теории графов и гиперграфов. Приведем эти формулировки.
1. Дана конъюнктивная нормальная форма из т различных элементарных дизъюнкций, реализующая монотонную булеву функцию ¥(хъ ... , хп). Требуется построить сокращенную дизъюнктивную нормальную форму функции Ш.
2. Дан гиперграф Ж с п вершинами и т ребрами. Требуется найти все минимальные вершинные покрытия гиперграфа Ж.
Эффективность алгоритмов перечисления принято оценивать сложностью шага (см. [1]). Говорят, что алгоритм работает с (квази)полиномиальной задержкой, если для любой индивидуальной задачи каждый шаг алгоритма (построение очередного решения) осуществляется за (ква-зи)полиномиальное время от размера входа задачи. В применении к поиску неприводимых покрытий это означает, что для любой булевой матрицы размера т х п время построения очередного неприводимого покрытия должно быть ограничено полиномом или квазиполиномом от т и п. В общем случае алгоритм дуализации с (квази)полиномиальной задержкой до сих пор не построен, и неизвестно, существует ли он. Известны примеры таких алгоритмов для некоторых частных случаев дуализации (см. [1], [2]). Например, в [1] построен алгоритм с задержкой 0(п3) для случая, когда в каждой строке матрицы Ь не более двух единичных элементов, что в постановке 2) соответствует случаю: Ж — граф.
1) Работа выполнена при частичной финансовой поддержке РФФИ (коды проектов 13-01-00787-а, 14-07-00819-а) и гранта Президента РФ НШ-4908.2014.1.
Исследования в области сложности перечислительных задач в основном касаются изучения возможности построения инкрементальных (квази)полиномиальных алгоритмов. В данном случае инкрементальность означает, что алгоритму разрешено на каждом шаге (при построении очередного решения) просматривать множество решений, построенных на предыдущих шагах, и на этот просмотр тратить время, (квази)полиномиальное от размера задачи и числа уже найденных решений. В [3], [4] построен инкрементальный квазиполиномиальный алгоритм дуали-зации. В [5], [6] для ряда частных случаев дуализации построены инкрементальные полиномиальные алгоритмы.
Существует еще один подход к решению рассматриваемой задачи, основанный на понятии асимптотически оптимального алгоритма с полиномиальной задержкой. Подход впервые предложен в [7] и ориентирован на типичный случай (on average). При определенных условиях этот подход позволяет заменить исходную перечислительную задачу Z на более "простую" перечислительную задачу Zx, имеющую тот же вход и решаемую с полиномиальной задержкой. При этом, во-первых, множество решений задачи Zx содержит множество решений задачи Z и, во-вторых, почти всегда с ростом размера входа число решений задачи Zx асимптотически равно числу решений задачи Z. Обоснование данного подхода базируется на получении асимптотик для типичного числа решений каждой из задач Z и Zx.
Таким образом, в отличие от "точного" алгоритма с полиномиальной задержкой асимптотически оптимальному алгоритму разрешено делать "лишние" полиномиальные шаги. Лишний шаг — это построение такого решения задачи Zx, которое либо было найдено ранее, либо построено впервые, но не является решением задачи Z. Число лишних шагов для почти всех задач данного размера должно иметь более низкий порядок роста, чем число всех шагов алгоритма, с ростом размера задачи. Проверка того, является ли шаг лишним, должна осуществляться за полиномиальное время от размера задачи.
К настоящему моменту для случая, когда lg m < (1 — s)lgn , 0 < s < 1, построен ряд асимптотически оптимальных алгоритмов поиска неприводимых покрытий булевой матрицы (см. [7]—[16]). В этих алгоритмах для построения ^(L) используется следующий критерий.
Набор H из r столбцов матрицы L является неприводимым покрытием тогда и только тогда, когда выполнены следующие два условия: 1) подматрица LH матрицы L, образованная столбцами набора H, не содержит строки вида (0, 0, ..., 0); 2) LHсодержит каждую из строк вида (1, 0, 0, ..., 0, 0), (0, 1, 0, ..., 0, 0), ..., (0, 0, 0, ..., 0, 1), т.е. с точностью до перестановки строк содержит единичную подматрицу порядка r. Набор столбцов, удовлетворяющий условию 2), называется совместимым.
В асимптотически оптимальном алгоритме дуализации AO1 (см. [7]) в роли Z1 выступает задача построения совокупности наборов столбцов матрицы L, удовлетворяющих условию 2), в которой каждый набор длины r встречается столько раз, сколько единичных подматриц порядка r этот набор содержит. Фактически с полиномиальной задержкой перечисляются все единичные подматрицы матрицы L. Ясно, что неприводимое покрытие может порождаться только максимальной единичной подматрицей, т.е. такой единичной подматрицей, которая не содержится в других единичных подматрицах. Максимальная единичная подматрица порождает максимальный совместимый набор столбцов, т.е. такой совместимый набор столбцов, который не содержится ни в каком другом совместимом наборе столбцов.
Схема работы алгоритма AO1 позволяет со сложностью шага O(qmn), где q = min{m, n}, перечислять максимальные единичные подматрицы (перечислять с повторениями максимальные совместимые наборы столбцов). Перебор единичных подматриц приводит к тому, что некоторые наборы столбцов строятся неоднократно. При получении очередной максимальной единичной подматрицы Q за время O(mn) алгоритм^O1 проверяет условие 1) для набора столбцов Hматрицы L, который порождается подматрицей Q, и, если условие 1) выполнено, то алгоритм AO1 за время O(mn) проверяет, был ли набор H построен на предыдущих шагах.
В алгоритме AO2 (см. [12]), который является модификацией алгоритма AO1, с полиномиальной задержкой O(qm2n) перечисляются только такие единичные подматрицы матрицы L, которые порождают покрытия. Алгоритм AO2 строит на каждом шаге неприводимое покрытие, однако найденные решения так же, как и в алгоритме AO1, могут повторяться. Этот алгоритм делает меньше лишних шагов по сравнению с алгоритмом AO1. В [16] на базе алгоритма AO2 были построены алгоритмы AO2K и AO2M, позволяющие сократить время счета.
Наименьшее число лишних шагов имеет асимптотически оптимальный алгоритм ОПТ (см. [14]), основанный на перечислении с полиномиальной задержкой O(qm2n) наборов столбцов матрицы L, удовлетворяющих условию 2) и некоторым дополнительным условиям, среди которых условие максимальности. Лишние шаги в алгоритме ОПТ возникают за счет построения максимальных совместимых наборов столбцов, не являющихся покрытиями (не удовлетворяющих условию 1)).
Обоснование асимптотически оптимальных алгоритмов дуализации базируется на следующем утверждении.
Утверждение 1. Пусть &(L) — множество всех единичных подматриц матицы L. Если lgm < < (1— s)lg n , 0 < s < 1, то для почти всех булевых матриц L размера m х n имеет место асимптотика №)| ~ №)|, n
В [17], [18] предложены алгоритмы дуализации RS и MMCS, для описания которых используются понятия теории гиперграфов. Эти алгоритмы основаны на построении наборов вершин S гиперграфа 9, удовлетворяющих условию "crit", которое эквивалентно условию "совместимости" 2) для соответствующего набора столбцов матрицы инцидентности гиперграфа 9. Таким образом, предложенный в [17], [18] подход к построению алгоритмов дуализации не является новым (алгоритмы RS и MMCS фактически являются асимптотически оптимальными). В [17], [18] показано, что алгоритмы RS и MMCS по скорости значительно превосходят ряд других алгоритмов, в частности инкрементальный квазиполиномиальный алгоритм из [4].
В настоящей работе построены асимптотически оптимальные алгоритмы RUNC, RUNC-M, PUNC. Каждый из этих алгоритмов так же, как и алгоритм ОПТ, основан на перечислении совместимых наборов столбцов, удовлетворяющих дополнительным условиям (для разных алгоритмов эти условия разные). Показано, что предлагаемые алгоритмы требуют меньших временных затрат по сравнению с асимптотически оптимальными алгоритмами, построенными ранее в [7] — [16], и в большинстве случаев опережают по скорости счета алгоритмы из [17], [18].
1. ОСНОВНЫЕ ПРИНЦИПЫ РАБОТЫ РАНЕЕ ПОСТРОЕННЫХ И НОВЫХ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ АЛГОРИТМОВ ДУАЛИЗАЦИИ
Асимптотически оптимальные алгоритмы дуализации можно условно разделить на два типа. К первому типу относятся алгоритмы, перечисляющие с полиномиальной задержкой максимальные единичные подматрицы матрицы L (не обязательно все). Такие алгоритмы совершают лишние шаги, связан
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.