8.5.3. Точный метод

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

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

1. Если столбец k имеет единицы везде, где имеет единицы столбец l, то столбец k можно удалить. Любая строка, покрывающая столбец l, покрывает также столбец k. Поэтому при поиске покрытия столбец k можно не рассматривать. Достаточно, чтобы в покрытие была включена какая-либо из строк, покрывающих столбец l.

2. Если строка i имеет единицы везде, где имеет единицы строка j, то строку j можно удалить. Действительно, пусть в некотором кратчайшем покрытии имеется строка j. Очевидно, данное покрытие останется кратчайшим, если в нем строку j заменить строкой i.

Продемонстрируем описанный процесс на матрице из предыдущего примера:

.

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

.

После удаления строк В₁, В₂ и В₈ согласно второму правилу редукции матрица Х будет иметь следующий вид:

.

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

.

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

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

а₆ –––В₆––– а₂ –––В₃––– а₄ –––В₄––– а₇ –––В₅–––

––––В₇––– а₈ –––В₄––– решение

–––В₂–––

Рис. 8.1. Дерево поиска кратчайшего покрытия

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