Создаете рандомную булевскую матрицу 8 строк, 10 столбцов. И находите безизбыточное покрытие используюя алгоритм Закревского( минимальный
столбец/максимальная строка).
Ответы
Я создам рандомную булевскую матрицу 8 строк, 10 столбцов:
1 0 0 0 1 1 1 1 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 1 0 1 1 1 0 0
0 1 0 0 0 1 0 1 1 1
1 0 1 0 0 1 0 1 1 0
0 0 1 1 0 1 0 0 0 1
1 1 1 0 0 1 1 1 0 0
0 0 0 1 1 1 1 0 0 1
Чтобы найти безизбыточное покрытие, Я буду использовать алгоритм Закревского. Сначала я нахожу максимальную строку, которая содержит наибольшее количество единиц. В данном случае, это строка номер 7:
1 1 1 0 0 1 1 1 0 0
Затем я удаляю все столбцы, в которых есть единицы в этой строке. В данном случае, я удаляю столбцы 1, 2, 3, 6, 7 и 8:
0 1 0 1 0
1 0 1 0 0
0 0 1 0 0
0 1 0 1 1
1 0 0 1 1
0 1 1 0 0
1 1 0 0 0
0 0 1 1 0
Теперь я повторяю процесс: нахожу максимальную строку и удаляю все столбцы, в которых есть единицы в этой строке. В данном случае, максимальная строка - это строка номер 1:
1 0 0 0 1
Удаляю столбцы 1 и 5:
0 1 0
1 0 0
0 0 0
0 1 1
1 0 1
0 1 0
1 1 0
0 0 1
Максимальная строка теперь строка номер 4
0 1 1
Удаляю столбцы 2 и 3:
0
1
0
1
0
0
1
1
Теперь я не могу удалить больше столбцов, так как матрица осталась без строк. Это значит, что я нашел безизбыточное покрытие, которое состоит из строк 7, 1 и 4 и соответствующих столбцов:
2 3 4
1 5
0 1
Это означает, что каждый столбец в матрице содержится в как минимум одной из этих строк. Кроме того, каждая строка в покрытии содержит по крайней мере одну из единиц в каждом столбце, который ей принадлежит. Таким образом, мы можем использовать только эти три строки и соответствующие столбцы для полного покрытия матрицы.