Алгоритм решения задачи

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

Нахождение приближенного решения

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

- на первом шаге выделяется столбец, содержащий наибольшее число единиц (если таких несколько, то берется любой из них), и в матрице вычеркиваются (считаются покрытыми) все строки, содержащие единицу в выделенном столбце;

- на k-м шаге выполняются те же действия над матрицей, полученной (в результате вычеркивания строк) на предыдущем шаге.

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

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

Oпределение оптимального решения