Участник: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-я, 3-я и 4-я строки. Заметим, что градиентное покрытие в данном случае не является ни минимальным ни тупиковым.
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].
2 Литература
Ложкин С.А. "Лекции по основам кибернетики" (учебное пособие для студентов) - М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР N 05899 от 24.09.2001), 2004 г. — 251 с.
