Question

Создаете рандомную булевскую матрицу 8 строк, 10 столбцов. И находите безизбыточное покрытие используюя алгоритм Закревского( минимальный столбец/максимальная строка).

Answer 1

Я создам рандомную булевскую матрицу 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

Это означает, что каждый столбец в матрице содержится в как минимум одной из этих строк. Кроме того, каждая строка в покрытии содержит по крайней мере одну из единиц в каждом столбце, который ей принадлежит. Таким образом, мы можем использовать только эти три строки и соответствующие столбцы для полного покрытия матрицы.

Answer 2

Для создания случайной булевской матрицы размером 8 строк и 10 столбцов, можно использовать язык программирования Python. Вот пример кода, который создаст такую матрицу:

import random

matrix = [[random.choice([True, False]) for _ in range(10)] for _ in range(8)]

В этом коде мы используем вложенные списки для создания матрицы. Внешний список представляет строки матрицы, а внутренние списки представляют значения в каждой строке. Мы используем функцию `random.choice()` для случайного выбора значения True или False для каждой ячейки матрицы.

Теперь, чтобы найти безизбыточное покрытие этой матрицы с использованием алгоритма Закревского, мы можем применить следующий подход:

1. Найдите столбец с наименьшим количеством единиц (min_col). 2. Добавьте этот столбец в безизбыточное покрытие (cover). 3. Удалите все строки, содержащие единицы в этом столбце из матрицы. 4. Повторяйте шаги 1-3, пока все строки не будут удалены из матрицы.

Вот пример кода, который реализует этот алгоритм:

def zakrevsky_algorithm(matrix):
    cover = []
    while matrix:
        min_col = min(range(len(matrix[0])), key=lambda x: sum(row[x] for row in matrix))
        cover.append(min_col)
        matrix = [row for row in matrix if not row[min_col]]
    return cover

Вы можете вызвать эту функцию, передав ей созданную ранее матрицу, чтобы найти безизбыточное покрытие:

cover = zakrevsky_algorithm(matrix)

В результате выполнения этого кода, переменная `cover` будет содержать список столбцов, которые образуют безизбыточное покрытие для данной матрицы.

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