ЛЕКЦИЯ 13. Курс: Проектирование систем: Структурный подход Каф. Коммуникационные и системы, Факультет радиотехники и кибернетики Московский физико-технический институт (университет) / Марк Ш. ЛЕВИН Институт проблем передачи информации, РАН Окт. 1, 2004 ПЛАН: 1.Базовые задачи комбинаторной оптимизации: *задача о рюкзаке, *схемы решения для многокритериальной задачи о рюкзаке, *блочная задача о рюкзаке. 2.алгоритмы: *типы решений (точные, приближенные), *типы алгоритмов (полиномиальные и переборные алгоритмы), 3.Сложность задач. 4.Глобальные подходы и локальные премы

Задача о рюкзаке max m i=1 c i x i s.t. m i=1 a i x i b x i {0, 1}, i = 1, …, m Возможные дополнительные ограничения m i=1 a ik x i b k, k = 1, …, l... 1 i m (индекс) a 1 a i a m (требуемый ресурс) c 1 c i c m (полезность/прибыль) x 1 x i x m (Булева переменная)

Алгоритмы для задачи о рюкзаке 1.Упорядочение по невозрастанию c i / a i (алгоритм Данцига, эвристика) 2.Метод ветвей и границ 3.Динамическое программирование (точное решение) 4.Динамическое программирование (схема приближенного решения) 5.Вероятностные методы 6.Гибридные схемы

Простые версии задачи о рюкзаке 1. c i = c o (равные полезности) 2. a i = a o (равные требуемые ресурсы) Полиномиальный алгоритм: 1. Упорядочение по неубыванию a i 2. Упорядочение по невозростанию c i

«Расширенные» версии задачи о рюкзаке 1.Задача о рюкзаке с целевой функцией на min 2.Задача о рюкзаке с несколькими рюкзаками 3.Задача о рюкзаке с дополнительными структурными (логическими) ограничениями на элементах (например, различные виды деревьев) 4.Многокритериальная задача о рюкзаке 5.Задача о рюкзаке с «размытыми» параметрами

Эвристическая схема для многокритериальной версии задачи о рюкзаке АЛГОРИТМИЧЕСКАЯ СХЕМА (случай линейного ранжирования): ШАГ 1.Многокритериальное ранжирование элементов (получить линейное ранжирование) ШАГ 2.Последовательный отбор элементов (лучший элемент, следующий элемент, и т.д.) После каждого отбора: тестирование ограничения по ресурсу ( b ). Если ограничение не выполняется, то необходимо исключить последний отобранный элемент и СТОП. Иначе: ШАГ 2. СТОП. Линейное ранжирование Отбор & тестирование (Шаг 2)

Эвристическая схема для многокритериальной версии задачи о рюкзаке АЛГОРИТМИЧЕСКАЯ СХЕМА (случай группового ранжирования): ШАГ 1.Многокритериальное ранжирование элементов (получить групповое ранжирование) ШАГ 2.Последовательные отбор элементов (элементы «лучшей» группы, элементы следующей группы и т.д.) После каждого отбора: тестирование ограничения по ресурсу ( b ). Если ограничение не выполняется, то ШАГ 3. Иначе: ШАГ 2. ШАГ 3. Решение для последней анализируемой группы специального случая задачи о рюкзаке (с равными полезностями) как последовательный отбор элементов из списка (невозростание по a i ). Здесь ограничение следующее: b - (i Q ) a i (где Q – множество отобранных элементов из предыдущих групп) СТОП. Отбор & тестирование (Шаг 2) Групповое ранжирование Отбор & тестирование (Шаг 2) Ограничение не выполняется, идти к Шагу 3

Блочная задача о рюкзаке max m i=1 qi j=1 c ij x ij s.t. m i=1 qi j=1 a ij x ij b qi j=1 x ij 1, i = 1, …, m x ij {0, 1}, i = 1, …, m, j = 1, …, qi... J 1 J i J m... i | J i | = qi, j = 1, …, qi

Алгоритмы для блочной задачи о рюкзаке (как для задачи о рюкзаке) 1.Упорядочение по невозростанию of c ij / a ij (эвристика) 2.Метод ветвей и границ 3.Динамическое программирование (точное решение) 4.Динамическое программирование (приближенная схема решения) 5.Вероятностные методы 6.Гибридные схемы

Иллюстрация для динамического программирования «Пространство» (область) поиска Точка НАЧАЛО Точка КОНЕЦ Последовательное построение решения: 1.От точки НАЧАЛО к точке КОНЕЦ 2.От точки КОНЕЦ к точке НАЧАЛО

Иллюстрация сложности задач комбинаторной оптимизации Полиномиально решаемые задачи NP-трудные задачи Полиномиаль- но, прибли- женно решаемые задачи Задача о рюкзаке Блочная задача о рюкзаке Квадратичная задача о назначении Задача морфологической клики Задача о клике Задача коммивояжера

Классификация алгоритмов ТОЧНОСТЬ РЕЗУЛЬТАТА (решение): 1.Точное решение 2.Приближенное решение (для наихудшего случая): *ограниченная ошибка (абсолютная), *ограниченная ошибка (относительная), *др. 3.Приближенное решение (статистически) 4.Эвристика (без оценок точности) ПО СЛОЖНОСТИ ПРОЦЕССА РЕШЕНИЯ (например, число шагов): 1.Полиномиальные алгоритмы (по длине входа, например: O(n log n)), O(n), O(1), O(n 2 ) 2.Полиномиальные приближенные схемы (для заданной точности / ограниченной ошибки, например: O(n 2 / ) где [0,1] - относительная точность по целевой функции) 3.Статистически «хорошие» алгоритмы (статистически полиномиальные) 4.Переборные алгоритмы... БАЗОВЫЕ АЛГОРИТМИЧЕСКИЕ РЕСУРСЫ: 1.Число шагов (вычислительные операции) 2.Требуемый объем памяти 3.Требуемой число взаимодействия со специалистом (оракулом) (для получения дополнительной информации) 4.Требуемые коммуникации между процессорами (для многопроцессорных алгоритмов)

Глобальные подходы и локальные приемы ГЛОБАЛЬНЫЕ ПОДХОДЫ: 1.Разбиение на подзадачи 2.Декомпозиция (расширение «хорошего» локального решения и др.) (например: динамическое программирование, метод ветвей и границ) 3.Сеточный подход с удалением «плохих точек» 4.Приближенные (аппроксимационные) подходы (т.е., аппроксимация исходной задачи или ее частей на основе более простой «конструкции») ЛОКАЛЬНЫЕ ПРИЕМЫ: 1.Локальная оптимизация как улучшение решения или его части 2.Вероятностные шаги 3. «Жадные» алгоритмы (выбор простого / близкого / и т.д.) 4.Рекурсия

Иллюстрация улучшения решения (локальная оптимизация) Точка НАЧАЛО Точка КОНЕЦ... ЛОКАЛЬНОЕ УЛУЧШЕНИЕ ИСХОДНЫЙ МАРШРУТ