Алгоритми покриття.

Пример задачи о покрытии Предположим, что организации нужно нанять переводчиков французского, немецкого, греческого, итальянского, испанииского, русского и китайского языков на английский и что имеется пять кандидатур А, В, С, D и Е. Каждая кандидатура владеет только некоторый собственным подмножеством из указанного выше множества языков и требует вполне определенную зарплату. Необходимо решить, каких переводчиков (с указанных выше языков на английский) надо нанять, чтобы затраты на зарплату были наименьшими. Это задача о наименьшем покрытии.

Математическое описание задачи Пусть - опорное множество. Имеется множество подмножеств Каждому подмножествусопоставлено число, называемой ценой. Множество называется решением задачи о покрытии, или просто покрытием, если выполняется условие При этом цена Термин «покрытие» означает, что совокупность множеств содержит все элементы множества В, т.е. «покрывает» множество B.

Определения и теоремы Безизбыточным называется покрытие, если при удалении из него хотя бы одного элемента оно перестает быть покрытием. Иначе – покрытие избыточно. Покрытие Р называется минимальным, если его цена наименьшая среди всех покрытий данной задачи. Покрытие Р называется кратчайшим, если l – наименьшее среди всех покрытий данной задачи. Минимальные и кратчайшие покрытия – безызбыточны.

Формулировки задачи о покрытии 1. Требуется найти все покрытия. Для решения задачи необходимо выполнить полный перебор всех подмножеств множества А. 2. Требуется найти только безызбыточные покрытия. Не существует простого и эффективного алгоритма, не требующего построения всех избыточных покрытий. (Используется граничный перебор либо разложение по столбцу в ТП). 3. Требуется найти одно без избыточное покрытие. Решение задачи основано на сокращении таблицы. Задачи о покрытии могут быть решены точно (при небольшой размерности) либо приближенно.

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

Составление таблицы покрытий

0. Создаем текущее подмножество Переход к п.4; 1. Находим наибольший номер j элемента в подмножестве D; 1.1 Если j не равен т и D – не покрытие, то выполняем п.3; 1.2 Если j не равен т и D – покрытие, то выполняем п.2; 1.3 Если j=m, то удаляем Ат из D, и если D = 0, то выполняем п.5, иначе – снова находим наибольший номер j элемента в подмножестве D и выполняем п.2; 2. Удаляем элемент Аj из D. 3. j:=j+1. Вводим элемент Аj в D. 4. Выясняем является ли D покрытием: 4.1 Если очередное построение в D – покрытие, то удаляем из ранее построенных покрытий те, которые поглощают D (избыточные покрытия), соответственно сокращая i и запоминаем D как покрытие. Переходим к п Если D не является покрытием, то выполняем п Заканчиваем построение всех безызбыточных покрытий. Алгоритм граничного перебора по вогнутому множеству

Теорема о ядре. Если в столбце таблицы покрытий содержится единственная 1, то строка, содержащая эту 1, входит во все покрытия и называется ядерной. Множество ядерных строк заранее выделяется и запоминается. Ядерные строки из таблицы удаляются и вычеркиваются все покрытые ими столбцы. Сокращение таблицы покрытий Теорема об анти ядре. Если после удаления ядерных строк и покрытых ими столбцов в какой либо строке не останется 1, то такая строка не входит ни в одно без избыточное покрытие. Такие строки называются антиядерными и вычеркиваются из таблицы покрытий без запоминания. Определение. Вектор поглощает вектор если для любых компонент этих векторов можно записать:

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

Алгоритм сокращение таблицы покрытий 0. Считаем исходную таблицу покрытий текущей, а множество ядреных строк – пустым. 1. Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем: вычеркиваем ядерные строки и все столбцы, покрытые ими; 2. Вычеркиваем антиядерные строки; 3. Вычеркиваем поглощающие столбцы; 4. Вычеркиваем поглощаемые строки веса которых не меньше весов соответствующих поглощающих строк; 5. Если в результате выполнения п.1-4 текущая таблица покрытий изменилась, то снова выполняем п.1, иначе преобразование заканчиваем.

Алгоритм минимального столбца - максимальной строки 1. В текущей таблице выделяется столбец с наименьшим числом единиц. 2. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие. 3. Таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу. 4. Если в таблице есть не вычеркнутые столбцы, то переходим к пункту 1, иначе – покрытие построено.

Задание !!! Предположим, что организации нужно нанять переводчиков французского, немецкого, греческого, итальянского, испанииского, русского и китайского языков на английский и что имеется пять кандидатур А, В, С, D и Е. франц. немец. греч. итал. испании. русск. кит. з/пз/п A B C D E Необходимо решить, каких переводчиков (с указанных выше языков на английский) надо нанять, чтобы затраты на зарплату были наименьшими. Каждая кандидатура владеет только некоторый собственным подмножеством из указанного выше множества языков и требует вполне определенную зарплату. Задачу решить, используя каждый из 3-х изученных алгоритмов!