Алгоритми покриття.. Пример задачи о покрытии Предположим, что организации нужно нанять переводчиков французского, немецкого, греческого, итальянского, - презентация

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

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

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

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

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

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

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

8 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 не является покрытием, то выполняем п Заканчиваем построение всех безызбыточных покрытий. Алгоритм граничного перебора по вогнутому множеству

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

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

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

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

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