8.5.2. Приближенные методы решения задачи

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

,

первой для включения в формируемое решение жадный алгоритм выберет строку В₁, после чего для покрытия оставшихся столбцов должны быть включены в решение обе строки В₂ и В₃. Кратчайшее же покрытие данной матрицы составляют только две строки – В₂ и В₃.

Более близкое к кратчайшему покрытие получается чаще всего с помощью «минимаксного» алгоритма. Он представляет собой многошаговый процесс, на каждом шаге которого выбирается столбец с минимальным числом единиц и из покрывающих его строк для включения в решение выбирается та, которая покрывает максимальное число непокрытых столбцов. Пусть, например, задана матрица

.

Одним из столбцов с минимальным числом единиц является столбец а₆. Из покрывающих его строк максимальное число столбцов покрывает строка В₆. Включим эту строку в решение и удалим ее и столбцы, которые она покрывает, в результате чего получим

.

Из оставшихся столбцов минимальное число единиц имеет столбец а₁₀. Покрывающие его строки В₄ и В₉ имеют одинаковое число единиц, т. е. одинаковое число покрываемых ими, но еще не покрытых столбцов. Включаем в решение первую по порядку строку В₄ и получаем матрицу

.

В полученной матрице столбцом с минимальным числом единиц является столбец а₂, а из покрывающих его строк строка В₇ имеет максимальное число единиц. Включение этой строки в решение завершает процесс, в результате которого полученным покрытием является {B₄, B₆, B₇}. Как будет показано ниже, это решение является точным.