Задачи о наименьшем покрытии

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

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

На первом этапе находят одно из допустимых решений, а на втором оно проверяется на оптимальность. Если текущее решение не оптимально, то возвращаются на первый этап, где формируют новое допустимое решение, иначе алгоритм заканчивает работу (рис. 3.5).

Рис. 3.5

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

Строки, содержащие единицу в столбцах, имеющих индекс и метку, считаются покрытыми.

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

Алгоритм ветвей и границ для решения задачи о наименьшем покрытии в табличной форме состоит из следующих шагов.

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

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

3. Проверяется, если число столбцов L1 текущего решения больше или равно числу столбцов L0 предыдущего решения, то переходят к п. 4, иначе, если не все строки покрыты, возвращаются к п.1. (Первоначально L0 приравнивают к числу столбцов в матрице покрытий.) Если же L1<L0 и все строки покрыты, то формирование очередного допустимого решения закончено. В этом случае запоминают номера и число помеченных столбцов и переходят к проверке решения на оптимальность.

4. Проверяется, помечен ли столбец, включенный в решение последним. Если помечен, то метка с него снимается (соответствующие строки считаются непокрытыми), и переходят к п. 2. Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс.

5. Проверяется наличие столбцов с индексами. Если таких нет, то исследуемое решение оптимально, иначе возвращаются на п.4.