НОВАЯ РЕДАКЦИЯ ПРИНЦИПА ГРУППОВЫХ РЕЗОЛЮЦИЙ ДЛЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЗВЕШЕННОМ ПОКРЫТИИ

НОВАЯ РЕДАКЦИЯ ПРИНЦИПА ГРУППОВЫХ РЕЗОЛЮЦИЙ ДЛЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЗВЕШЕННОМ ПОКРЫТИИ

Герман Олег Витольдович

канд. техн. наук, доцент, Белорусский государственный университет информатики и радиоэлектроники,

Беларусь, г. Минск

Герман Юлия Олеговна

канд. техн. наук, доц., Белорусский государственный университет информатики и радиоэлектроники,

Беларусь, г. Минск

A NEW VERSION OF THE GROUP RESOLUTION PRINCIPLE FOR A MINIMUM WEIGHTED COVER PROBLEM

Oleg German

Candidate of technical sciences, associate Professor, Belarussian state university of informatics and radioelectronics,

Republic of Belarus, Minsk

Julia German

candidate of technical sciences, associate Professor, Belarussian state university of informatics and radioelectronics,

Republic of Belarus, Minsk

АННОТАЦИЯ

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

ABSTRACT

A new version of the method based on the principle of group resolvents for solving the combinatorial optimization problem on the minimum weighted coverage of a 0,1-matrix is presented. First, the size of the matrix (the number of columns) when adding new group resolvents is limited to twice the number of rows, so that it is possible to write new resolutions over the old ones without losing the solution. Second, the principle of resolutions for the weighted case is the same as for the unweighted case. Thirdly, the method is strengthened by the ability to construct group resolvents without looking for a complete coverage at each iteration - there are situations when the process can be stopped and a resolvent can be built on a reduced syndromic matrix, which enhances the general convergence of the method.

The complexity estimation of the method corresponds to the previously reported and characterizes the polynomiality of the method in the average case.

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

Keywords: cover, minimum weighted cover, group resolution principle, binary matrice.

Введение

Комбинаторные задачи довольно часто встречаются на практике, но их характерной особенностью является переборный характер процесса решения (эффективный алгоритм с точки зрения вычислительной сложности не известен для значительного класса этих задач [1]). Поэтому используют эвристические методы, генетические алгоритмы, нейронные сети, статистические методы и другие способы поиска решений. Имеются в некотором смысле универсальные переборные задачи, к которым можно эффективно свести другие комбинаторные задачи. Одной из таких задач является задача о минимальном покрытии 0,1-матрицы. Остановимся на одном из практически апробированных методов ее решения – принципе групповых резолюций (п.г.р.) [2, 3]. Этот метод хорошо проявил себя в среднестатистическом смысле. В настоящей статье представлен вариант с улучшенной реализацией метода – групповые резольвенты записываются поверх ранее добавленных, что  останавливает рост требуемой памяти после добавления максимум n резольвент (n  – число строк в матрице); процесс порождения групповых резольвент выполняется аналогично невзвешенному случаю для задачи о покрытии, что сокращает затраты времени собственно на построение групповых резольвент. Таким образом, для поиска минимального взвешенного покрытия 0,1-матрицы можно использовать п.г.р., изложенный в [4] в практически в неизменном виде.

Определения и формальная схема метода

Определение. Строка i 0,1-матрицы М покрывает столбец j, если она содержит в нем «1».

Определение. Покрытием 0,1-матрицы М называется множество строк p таких, что каждый столбец матрицы М покрывается хотя бы одной строкой из p

Возьмем в качестве примера матрицу, показанную на рисунке 1.

Рисунок 1. Исходная 0,1-матрица с весами строк w_j

Будем рассматривать в качестве весов w_j (одноименный столбец на рисунке 1) целые положительные числа. Нас интересует покрытие с минимальным суммарным весом строк. Как и для невзвешенного случая на каждой итерации метода ищем некоторое подходящее (эвристическое) покрытие для чего:

(I) определяем столбец j с минимальным числом единиц – объявляем его синдромным;

(II) в этом столбце выбираем строку i с минимальным весом, которая его покрывает. Сокращаем текущую матрицу как описано далее;

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

(IV) добавляем групповую резольвенту к текущей матрице (см. Замечание 1) и возобновляем итерации, пока не получим нулевую групповую резольвенту. Лучшее из найденных решений и есть искомое.

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

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

Сокращение матрицы, выполняемое для найденного столбца j и строки i в п. (II) приведенной выше схемы, реализуется так: удаляем из текущей матрицы М все столбцы, где строка i содержит «1», а также удаляем все строки, которые содержат в столбце j «1», включая саму строку i. Помещаем строку i в формируемое текущее покрытие p.

Иллюстрация метода на примере

Обратимся к примеру на рисунке 1. Выбираем столбец j5 (минимальное число единиц) и строку i10 (минимальный вес). Столбец j5 объявляем синдромным. Редуцируем (сокращаем) матрицу М к виду, показанному на рисунке 2.

Рисунок 2. Первое сокращение матрицы

Выбираем столбец j3 (объявляем синдромным) и строку i1. Редуцируем матрицу, изображенную на рисунке 2, к виду, показанному на рисунке 3.

Рисунок 3. Второе сокращение

Выбираем столбец j1 (объявляем синдромным) и строку i2. Наконец, на последнем шаге итерации выбираем синдромный столбец j8 и строку i4. Таким образом, найдено первое покрытие p ={ i1, i10, i2, i4} с весом 14.

Строим синдромную матрицу на синдромных столбцах (рисунок 4) и находим резольвенту res1.

Рисунок 4. Синдромная 0,1-матрица с весами строк w_j

Возобновляем процесс на исходной матрице М, расширенной за счет присоединения столбца res1 (рисунок 5).

Рисунок 5. Возобновление итераций на расширенной матрице

Выбираем столбец j5 (минимальное число единиц) и строку i10 (минимальный вес). Столбец j5 объявляем синдромным. Редуцируем матрицу к виду, показанному на рисунке 6.

Рисунок 6. Первая редукция

Выбираем столбец j3 (объявляем синдромным) и строку i1. Редуцируем матрицу к виду, показанному на рисунке 7.

Рисунок 7. Очередная редукция

Выбираем столбец res1  и строку i8. Получаем покрытие p = { i1, i10, i8} с весом 15.    Строим синдромную матрицу (рисунок 8).

Рисунок 8. Вторая резольвента

Возобновляем процесс (рисунок 9).

Рисунок 9. Третья итерация

Выбираем столбец j5 и строку i10. Столбец j5 объявляем синдромным. Редуцируем матрицу к виду, показанному на рисунке 10.

Рисунок 10. Первая редукция на третьей итерации

Выбираем столбец res2 и строку i6. Столбец res2 объявляем синдромным. Редуцируем матрицу к виду, показанному на рисунке 11.

Рисунок 11. Вторая редукция на третьей итерации

Выбираем столбец j9 и строку i1, затем столбец j8 и строку i3. К этому моменту текущее покрытие имеет следующий вид p = { i1, i10, i6, i3} с весом, равным 20. Находим резольвенту res3 (рисунок 12).

Рисунок 12. Определяем групповую резольвенту res3

Эту новую резольвенту записываем поверх res1, поскольку res1 не использовалась как синдромный столбец. Возобновляем итерации на матрице, показанной на рисунке 13.

Рисунок 13. Новая стартовая матрица

Выбираем столбец j5 и строку i10. Столбец j5 объявляем синдромным. Редуцируем матрицу к виду, показанному на рисунке 14.

Рисунок 14. Первая редукция на четвертой итерации

Далее выбираем столбцы res2 и res3, и строки i4, i6. Текущее множество p = { i10, i6, i4}. Его вес равен 15. Дальнейшее наращивание этого покрытия только увеличивает вес. Ранее было найдено покрытие p ={ i1, i10, i2, i4} с весом 14. Поэтому процесс здесь останавливаем и строим синдромную матрицу на найденных столбцах (рисунок 15).

Рисунок 15. Новая резольвента res4

Стартуем пятую итерацию на матрице, показанной на рисунке 16.

Рисунок 16. Новая стартовая матрица

Выбираем столбец res4 и строку  i9. Редуцируем матрицу (рисунок 17).

Рисунок 17. Первая редукция

Выбираем столбец j1 и строку i2. Редуцируем матрицу (рисунок 18).

Рисунок 18. Вторая редукция

Выбираем столбец j8  и строку i4. Текущее покрытие (не достроенное) имеет вид p = {i2, i4, i9} с весом 17. Его вес уже больше веса лучшего из ранее найденных покрытий. Поэтому процесс обрываем и строим синдромную матрицу (рисунок 19).

Рисунок 19. Вторая редукция

Получили новую резольвенту res5. Далее выкладки опускаем и получаем очередное (неполное) покрытие p = {i8, i9} с весом 18 и синдромными столбцами res4 и res5. Синдромная матрица на этих двух столбцах дает нулевую резольвенту (последние два столбца на рисунке 19). Таким образом, алгоритм поиска минимального взвешенного покрытия завершен. Оптимальное решение таково: p ={ i1, i10, i2, i4} с весом 14.

Заключение

В настоящей статье изложен теоретически оптимальный метод эффективный в среднестатистическом смысле [2, 3]. Задача взвешенного минимального покрытия 0,1-матрицы решается на основе п.г.р. без каких-либо существенных модификаций в его принципе, что указывает на универсальный характер п.г.р. Его сложностная оценка в среднем близка к полиномиальной и служит основанием для практического использования метода. Приведенный в статье вариант алгоритма не ведет к росту затрат памяти и позволяет решать задачи сравнительно высокой размерности.

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

1. Pardalos P.V., Ding-Zhu Du, Graham R. (editors). Handbook of combinatorial optimization. Springer. 2013. – 685p.
2. Герман О. В., Найденко В. Г. Статистически оптимальный алгоритм для задачи о минимальном покрытии // Экономика и математические методы. 1993. т. 29. Вып. 4. С. 662-667.
3. Герман О. В. Обобщенный статистически оптимальный метод решения задачи о минимальном взвешенном покрытии 0,1-матрицы //Экономика и математические методы. 1994, т. 30. Вып. 4. С. 139-150.
4. German J. O. One version of the group resolution principle for discrete optimization //Proc. of Intern. conf. Information Technologies and Systems (ITS) 2020. Minsk, BSUIR, 2020, pp.165-167.