Участник:ZhibekK/Градиентный алгоритм поиска покрытия 0,1-матрицы
Градиентный алгоритм поиска покрытия 0,1-матрицы
Автор: Какимжанова Кыз-Жибек
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Задача поиска минимального покрытия матрицы является достаточно трудоемкой. В связи с этим, вместо поиска минимального покрытия, часто используют эвристические алгоритмы, позволяющие получать не очень "длинные" покрытия. К числу таких алгоритмов относится и градиентный (или "жадный") алгоритм, суть которого заключается следующем: на каждом шаге в матрице выбирается строка, покрывающая наибольшее число еще не покрытых столбцов. Алгоритм завершает свою работу после шага, на котором все выбранные строки образуют покрытие матрицы. Полученное покрытие называется градиентным.
Рассмотрим следующий пример:
[math]M = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ \end{bmatrix}[/math]
Градиентное покрытие матрицы [math]M[/math] образуют все ее строки. Так как на первом шаге алгоритм выберет первую строку, а на последующих шагах последовательно выберет все остальные. Полученное покрытие не является ни минимальным ни тупиковым.
1.2 Математическое описание алгоритма
Вход: [math]М = (m)_{i,j}[/math] - матрица, состоящая из 0 и 1, без нулевых столбцов.
Выход: Градиентное покрытие матрицы [math]М[/math].
Будем говорить, что i-я строка покрывает j-й столбец, если [math]m_{i,j} = 1[/math]. Множество строк [math]I[/math] матрицы [math]M[/math] назовем покрытием матрицы [math]M[/math], если все строки из [math]I[/math] в совокупности покрывают все столбцы матрицы [math]M[/math]. Другими словами если для любого столбца j матрицы [math]M[/math] существует номер i из [math]I[/math], такой, что [math]m_{i,j} = 1[/math].
Тогда в результате выполнения описанного выше алгоритма получим градиентное покрытие матрицы [math]M[/math].
Следующее утверждение дает верхнюю оценку длины покрытия, получаемого с помощью градиентного алгорит- ма для матриц с заданной «густотой».
Теорема. Пусть для действительного [math]\gamma, 0\lt \gamma \le 1[/math], в каждом столбце матрицы [math] M, M \in B^{p,s}[/math], имеется не меньше, чем \gamma · p, единиц. Тогда покрытие матрицы [math]M[/math] , получаемое с помощью градиентного алгоритма, имеет длину не больше, чем [math]\left \lceil \frac{1}{\gamma} \ln^{+}(\gamma s) \right \rceil + \frac{1}{\gamma}[/math].
В качестве примера применения градиентного алгоритма рассмотрим задачу о "протыкании" граней булева куба его точками. Задача о "протыкании" системы, состоящей из подмножеств [math] N_1, N_2, \ldots, N_p[/math] множества [math] N = {\alpha_1, \ldots, \alpha_s}[/math] заключается в нахождении такого подмножества множества [math] N [/math], в котором при любом [math]i, i \in [1,p][/math], имеется хотя бы один элемент из [math] N_i [/math]. Эта задача сводится к задаче о выделении подпокрытия из покрытия отрезка [1,p] его подмножествами [math] I_1, \ldots, I_s[/math], где [math] I_i = {j: \alpha \in N_j}[/math] при всех [math] i, i \in [1,s][/math]. В таком случае имеет место следующее утверждение:
Теорема. При любых натуральных [math]n[/math] и [math]m[/math], [math]m \le n[/math], в кубе [math] B^n[/math] всегда найдется подмножество мощности не более, чем [math] n·2^m[/math], протыкающее все грани ранга [math]m[/math].
2 Литература
Ложкин С.А. "Лекции по основам кибернетики" (учебное пособие для студентов) - М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР N 05899 от 24.09.2001), 2004 г. — 251 с.
