Презентація на тему Алгоритми покриття
Подібні презентації
Презентація на тему: "Алгоритми покриття.. Приклад завдання про покриття Припустимо, що організації потрібно найняти перекладачів французької, німецької, грецької, італійської" - Транскрипт:
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-х вивчених алгоритмів!