Задачи о покрытии множеств. Поиск минимальных разбиений, страница 2

Итак, пусть А = {a₁,a₂,a₃,a₄,a₅,a₆,a₇}, B={b₁,b₂,b₃,b₄,b₅,b₆}={a, b, с, d, е, f}. Обозначая строки матрицы С номерами элементов множества А, положим

Отобразим производимый перебор последовательностью значений, принимаемых переменным множеством В*. Представим номер старшего элемента в этом подмножестве из В значением индекса j. Например, если В* ={b₁ , b₃ , b₆}, то j=6. Другой индекс i, значениями которого также служат номера элементов из В, используем для выбора подмножества Bi = {b_i , b_i+1 , … , b_m} из множества B = { b₁ , b₂ , … , b_i , b_i+1 , … , b_m}. Представляя формулой i:=j операцию присвоении индексу i значения индекса j, сформулируем алгоритм перебора.

1. i:= 0. Множество В* приравниваем пустому множеству ф.

2. Добавляем в В* младший из тех элементов множества B_i+1 , которые не покрываются множеством В*, i := j Если В* не покрывает множество А, переходим к началу п. 2. В противном случае текущее значение множества В* включаем в результативное множество Q.

3. i := j. Удаляем из В* элемент b_j . Если В*UB_i+1 покрывает множество А, переходим к п. 2. Иначе, если В* не пустое множество, переходим к началу п. 3, в противном случае реализация алгоритма завершается.

Заметим, что в получаемом с помощью описанного алгоритма множестве Q будут содержаться все простые покрытия множества A, но, может быть, не только они. Поэтому требуется дополнительный анализ покрытий на простоту.

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

(знаком + отмечены те из найденных покрытий, которые оказываются простыми).

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

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

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

Каждый столбец c^j этой матрицы задает элемент b_j , множества В = {а, Ь, с, .., i}, т. е. некоторое подмножество из множества А = {a₁ , a₂ , … , a₁₀}, которое можно использовать в качестве элемента покрытия. Каждая строка с_i задает аналогичным образом некоторое подмножество B_i из множества В и представляет одно из предъявляемых к покрытию требований:в покрытие должен войти по крайней мере один из элементов подмножества B_i . Если это подмножество содержит лишь один элемент (в строке только одна единица), включение этого элемента становится обязательным, в противном случае допустим выбор, тем более ограниченный, чем меньше единиц в рассматриваемой строке.

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

В подготовленном примере этот алгоритм приводит к начальному выбору строки 6 (первой по порядку среди минимальных строк) и столбца f, после чего из матрицы удаляются столбец f  и строки 1, 3, 6, 9 и она сокращается до