Алгоритм граничного перебора по вогнутому множеству. Цель занятия по данной теме – освоение методов и алгоритмов полного перебора и сокращения перебора при нахождении покрытий

АЛГОРИТМЫ ПОКРЫТИЯ

 

Цель занятия по данной теме – освоение методов и алгоритмов полного перебора и сокращения перебора при нахождении покрытий.

 

2.1. Постановка задачи покрытия

 

Пусть B= { b₁,...,b_n } – опорное множество. Имеется множество A, состоящее из m подмножеств (A ={A ₁,..., A_m }) множества В таких, что . Каждому подмножеству сопоставлено число c_i, называемое ценой. Множество P= { }(k_j Î{1 ,..., m}, l £ m, k - номер варианта выборки подмножеств) называется решением задачи о покрытии или просто покрытием, если выполняется условие

, (2.1)

при этом цена .

Термин покрытиеозначает, что совокупность множеств содержит все элементы множества В, т.е. “покрывает” множество В.

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

Определение 2.2. Покрытие Р называется минимальным, если его цена – наименьшая среди всех покрытий данной задачи.

Определение 2.3. Покрытие Р называется кратчайшим, если l – наименьшее среди всех покрытий данной задачи.

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

Теорема 2.1. Минимальные и кратчайшие покрытия – безызбыточны.

Удобным и наглядным представлением исходных данных и их преобразований в задаче о покрытии является таблица покрытий. Таблица покрытий – это матрица Т отношения принадлежности элементов множеств опорному множеству В; столбцы матрицы Т сопоставлены элементам b_j множества В, строки – элементам A_i множества А:

. (2.2)

Нули в матрице Т не проставляются.

Пример 2.1. Некоторый писатель выпустил множество сборников A= { A₁,..., A₇ }, содержащее в совокупности все множество B= { b₁,..., b₉ } его сочинений (табл. 2.1). Каждый сборник содержит некоторое подмножество сочинений из В и имеет некоторую цену . Необходимо найти такое множество P= { } (i_j Î{1,...,7}, l £7) сборников, чтобы в их совокупности содержались все сочинения данного автора и чтобы при этом либо цена такого полного собрания сочинений была наименьшей, либо количество l сборников было наименьшим.

Таблица 2.1

T	b1	b2	b3	b4	b5	b6	b7	b8	b9	c
A1
A2										2,5
A3
A4										1,5
A5
A6
A7

 

На языке отношения принадлежности задача о покрытии формулируется как задача построения таких подмножеств строк таблицы покрытия (ТП), чтобы в совокупности строк, входящих в , во всех столбцах были “1” (единицы в некотором столбце могут повторяться). Такое подмножество строк ТП называется покрытием.

Возможным решением примера 2.1 будут следующие множества:

;

;

; .

Имеются следующие варианты формулировки задачи о покрытии.

1. Требуется найти все покрытия. Для решения задачи необходимо выполнить полный перебор всех подмножеств множества А.

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

3. Требуется найти одно безызбыточное покрытие. Решение задачи основано на сокращении ТП.

Задачи о покрытии могут быть решены точно (при небольшой размерности) либо приближенно.

Для нахождения точного решения используются следующие алгоритмы.

1. Алгоритм полного перебора. Основан на методе упорядочения перебора подмножеств множества А.

2. Алгоритм граничного перебора по вогнутому множеству. Основан на одноименном методе сокращения перебора.

3. Алгоритм разложения по столбцу ТП. Основан на методе сокращения перебора, который состоит в рассмотрении только тех строк ТП, в которых имеется “1” в выбранном для разложения столбце.

4. Алгоритм сокращения ТП. Основан на методе построения циклического остатка ТП, покрытие для которого далее строится методами граничного перебора либо разложения по столбцу.

Приближенное решение задачи о покрытии основано на следующем соображении. Даже сокращённый перебор приводит к очень трудоёмкому процессу решения, поэтому для получения ответа приходится отказываться от гарантий построения оптимального решения (минимального либо кратчайшего); однако при этом целесообразно получить не самый худший результат – хотя бы безызбыточное покрытие, удовлетворяющее необходимому условию (2.1). Тогда, в ущерб качеству, можно значительно упростить процесс решения.

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

Ниже рассматриваются упомянутые алгоритмы (за исключением алгоритма разложения по столбцу).

2. 2. Алгоритм полного перебора

 

Будем считать, что подмножества пронумерованы и таким образом упорядочены. Естественный метод перебора всех подмножеств строк таблицы покрытий строится так: пустое подмножество строк, подмножества из одной строки, из двух строк,…, из всех строк, т.е. всего подмножеств:

.

Словесное описание алгоритма:

0. Текущее подмножество ;

1. i=i+1. Запоминаем множество , как очередное построенное подмножество ;

2. Находим наибольший номер j элемента ;

2.1. Если j ¹ n (n - количество подмножеств ), то переходим к п.3;

2.2. Если j = n, то удаляем из и если , то заканчиваем построение; если – находим наибольший номер j элемента и удаляем из .

3. j=j+1. Вводим в элемент . Переходим к п.1.

Алгоритм граничного перебора по вогнутому множеству

 

Данный алгоритм основан на генерации подмножеств и их целенаправленном отборе.

Алгоритм генерации подмножеств должен гарантировать, что при его последовательном применении можно построить, начиная с некоторого начального подмножества, все возможные подмножества; при этом не должно быть повторений и должен существовать критерий окончания перебора. В п.2.2 упорядочение перебора произведено сначала по числу i элементов, а затем для фиксированного i – по лексикографическому правилу относительно номеров подмножеств.

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

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

Теорема 2.2. Если P покрытие, то и P’, P’ Ê P, тоже покрытие, т.е. множество всех возможных покрытий вогнуто.

Безызбыточные покрытия – это граница вогнутого множества всех покрытий, поэтому модифицированный алгоритм носит название “Алгоритм граничного перебора по вогнутому множеству”.

Словесное описание алгоритма:

0. Текущее подмножество D ={ A₁ }, i=0. Выполняем п.4;

1. Находим наибольший номер j элемента в подмножестве D.

1.1. Если j ¹ n и – не покрытие, то выполняем п.3.

1.2. Если j ¹ n и – покрытие, то выполняем п.2.

1.3. Если j = n, то удаляем из , и если , то выполняем п. 5, иначе – снова находим наибольший номер j элемента в D и выполняем п.2.

2. Удаляем элемент из .

3. j=j+1. Вводим элемент в D.

4. Выясняем, является ли покрытием.

4.1.Если очередное построение в – покрытие, то удаляем по очереди из ранее построенных покрытий те, которые поглощают , т.е. избыточные покрытия, соответственно уменьшая i каждый раз на 1, и запоминаем D как покрытие Переходим к п.1;

4.2. Если построение в D не является покрытием, то выполняем п.1;

5. Заканчиваем построение всех безызбыточных покрытий.

Из полученных безызбыточных покрытий можно выбрать покрытия с минимальным количеством строк (кратчайшее покрытие) либо покрытие с минимальной ценой (минимальной покрытие) в соответствии с (2.2).

2.4. Алгоритмы, использующие сокращение таблицы покрытий

Теорема 2.3. (о ядре). Если в столбце таблицы покрытий содержится единственная единица, то строка, содержащая эту единицу, входит во все покрытия и называется ядерной.

Множество ядерных строк заранее выделяется и запоминается для введения во все покрытия. Ядерные строки из ТП удаляются и вычеркиваются все покрытые ими столбцы, т.е. вычеркиваются все столбцы, в которых есть 1 в ядерных строках.

Теорема 1.4. (о б антиядре). Если после удаления ядерных строк и покрытых ими столбцов в какой-либо строке не останется 1, то этa строка не входит ни в одно безызбыточное покрытие. Такие строки называются антиядерными и вычеркиваются из ТП без запоминания.

Определение 2.4. Вектор поглощает вектор , E ³ F, если для всех компонент этих векторов можно одновременно записать . В противном случае векторы называются несравнимимы.

Пример 2.2. Пусть заданы два вектора E=(1,1,0,1), F=(0,1,0,1). Сравнивая их поэлементно (например, слева направо), заключаем, что E ³ F.

Теорема 2.5 (о поглощающих столбцах). В ТП могут быть вычеркнуты все поглощающие столбцы (рассматриваемые как векторы) без ущерба для построения всех безызбыточных покрытий.

Теорема 2.6 (о поглощаемых строках при поиске одного кратчайшего покрытия). Если при решении задачи о покрытии достаточно гарантировать получение хотя бы одного кратчайшего покрытия, то можно удалить все поглощаемые строки.

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

Используя теоремы 2.3 - 2.7, упрощаем ТП. При этом возможны два исхода.

1. ТП после упрощения становится пустой (вычеркнуты все столбцы). В этом случае множество ядерных строк - требуемое покрытие.

2. Остаток ТП более не упрощается приёмами из теорем 2.3 - 2.7. Получаем циклический остаток (ЦО) таблицы покрытий. Покрытие ЦО таблицы можно строить методами граничного перебора либо разложения по столбцу.

Полное решение (покрытие исходной таблицы) состоит из ядерных строк и строк покрытия ЦО.

Расмотрим варианты алгоритма построения ЦО для ТП.