освіти та науки Росії
Федеральне державне автономне освітній заклад
вищої професійної освіти
«ПІВДЕННИЙ федеральний університет»
ІНЖЕНЕРНА ТЕХНОЛОГІЧНА АКАДЕМІЯ В м. Таганрог
(ТРТІ Південного федерального університету)
Факультет АВТОМАТИКИ І ОБЧИСЛЮВАЛЬНОЇ ТЕХНІКИ
РЕФЕРАТ
з навчальної дисципліни
«Теорія прийняття рішень»
на тему
«Завдання упаковки в контейнери»
Виконала: студентка гр. А - 31,
Панченко О.Л.
Перевірив: Грищенко А. С.
Таганрог, 2014
Введення
У теорії складності обчислень <# «justify">" Наступний відповідний» (NF), «Перший відповідний» (FF), «Найкращий відповідний» (BF), On-line, з обмеженим доступом до контейнерів, «Перший підходящий з впорядкуванням» (FFD), A? .
Роботу алгоритмів розглянемо далі.
1. Завдання упаковки в контейнери
Дано: безліч предметів L={1, ..., n} і їх ваги wi? (0,1), i? L.
Знайти: розбиття множини L на мінімальне число m підмножин B1, B2, ..., Bm таке, що
Множини Bj називають контейнерами.
Требуется упакувати предмети в мінімальне число контейнерів.
Завдання NP-важка і часто виникає в додатках.
.1. Алгоритм «Наступний відповідний» (NF)
У довільному порядку пакуємо предмети за наступним правилом.
Перший предмет поміщаємо в першу контейнер.
На k-му кроці намагаємося помістити k-й предмет в поточний контейнер.
Якщо предмет входить, то поміщаємо його і переходимо до наступного кроку, інакше поміщаємо предмет в новий контейнер.
Т=О (n), П=О (1), якщо не вважати місце для вихідних даних.
Теорема (L)? 2OPT (L).
Доказ. Нехай
Так як будь-які два послідовні контейнера містять предмети сумарним вагою не менше одиниці, то NF (L) < 2? W? .
Крім того, OPT (L)? ? W? , Звідки і слід потрібне.
Приклад.
Зауваження. NF (L)? 2OPT (L) - 1 для всіх L.
Нехай алгоритм A для безлічі L породжує A (L) контейнерів і
Для завдання на мінімум гарантована відносна точність RA для алгоритму A визначається як RA? inf {r? 1 | RA (L)? r для всіх L}.
Визначення. Асимптотична гарантована відносна точність для алгоритму A визначається як
? inf {r? 1 |? N> 0 таке, що RA (L)? r для всіх L з OPT (L)? N}.
1.2. Алгоритм «Перший відповідний» (FF)
У довільному порядку пакуємо предмети за наступним правилом.
