Алгоритми пошуку покриття безлічі

Практична робота №5.

Тема:  Алгоритми пошуку покриття безлічі.

Ціль: Засвоєння методів і алгоритмів повного перебору й  скорочення перебору при знаходженні покриттів.

 Постановка завдання.

Нехай [pic 1]- опорна безліч. Є безліч підмножин [pic 2] безлічі В. [pic 3] Кожній підмножині [pic 4]  зіставлена  число [pic 5], називане ціною. Безліч [pic 6] називається рішенням завдання про покриття або просто покриттям, якщо виконується умова [pic 7], при цьому ціна  [pic 8]. Термін покриття означає, що сукупність безлічей [pic 9]  містить  всі елементи безлічі[pic 10] В, тобто “покриває” безліч В.

Визначення 3.1. 1.  Безнадлишковим  називається покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Інакше -  покриття збиткове.

Визначення 3.1. 2. Покриття Р називається мінімальним, якщо його ціна   [pic 11]  - найменша серед всіх покриттів даної задачі.

Визначення 3.1. 3. Покриття Р називається найкоротшим, якщо l – найменше серед всіх покриттів даної задачі.

Теорема 3.1. 1. Мінімальні й найкоротші покриття - безнадлишкові.

              Є наступні варіанти формулювання завдання про покриття.

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

2. Потрібно знайти тільки безнадлишкові покриття. Не існує простого й ефективного алгоритму, не потребуючої побудови всіх надлишкових покриттів; добре, якщо зменшується їхня кількість. Використається граничний перебір або розкладання по стовпці в таблиці покриттів (ТП).

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

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

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

1. Алгоритм повного перебору. Заснований на методі впорядкування перебору підмножин безлічі А.

2. Алгоритм граничного перебору по ввігнутій безлічі. Заснований на однойменному методі скорочення перебору.

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

4.   Алгоритм скорочення ТП. Заснований на методі побудови циклічного залишку ТП, покриття для якого далі будується методами граничного перебору або розкладання по стовпці.

Наближене рішення завдання про покриття засновано на наступному міркуванні. Якщо навіть скорочений перебір приводить до дуже трудомісткого процесу рішення, то для відповіді доводиться відмовлятися від гарантій побудови оптимального рішення      (мінімального або найкоротшого); однак доцільно одержати не самий гірший результат – хоча б безнадлишкове покриття, що задовольняє необхідній  умові [pic 12].

При цьому, на шкоду якості, можна значно спростити процес рішення. Алгоритм побудови покриття, близького до найкоротшого, заснований на методі мінімального стовпця - максимального рядка. Нижче розглядаються згадані алгоритми ( за винятком алгоритму розкладання по стовпці ).

Таблиця  покриття.

Зручним і наочним поданням вихідних даних і їхніх перетворень у завданні про покриття є таблиця покриття. Таблиця покриття – це матриця Т відносини  приналежності  елементів безлічей [pic 13] опорній безлічі В. Стовпці матриці Т зіставлені елементам безлічі В, рядка – елементам безлічі  А: [pic 14].

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

Приклад 3.2. 1. Деякий   письменник   випустив   безліч   збірників [pic 15], що містить у сукупності  вся  безліч[pic 16] його творів ( таблиця 3.2. 1.). Кожний збірник [pic 17] містить деяка підмножина творів з У [pic 18] и має деяку ціну [pic 19]. Необхідно знайти таку безліч [pic 20] збірників, щоб у їхній  сукупності втримувалися всі твори даного автора [pic 21] й щоб при цьому ціна [pic 22] такого повного зібрання творів була найменшої, або кількість l збірників бути мінімальним.