Сравнительный анализ эффективности «классической» версии динамического программирования при поиске глобально оптимального решения зад
Автор: georgii988 • Февраль 26, 2020 • Реферат • 777 Слов (4 Страниц) • 475 Просмотры
Задание на выпускную квалификационную работу (диссертацию) магистратуры ИВТ по профилю АСУ на 2018/2020 гг.
Научный руководитель | Студент |
Гроппен В. О. | Савлаев Георгий Вартанович |
- Название и содержательная постановка задачи.
1.1. Название: Сравнительный анализ эффективности «классической» версии динамического программирования при поиске глобально оптимального решения задачи о ранце, и его композитной версии, использующей для вычисления верхних оценок целевой функции технологию линейного программирования и переиндексацию переменных в порядке убывания отношения Сi/ai.
1.2. Исходные данные:
Применительно к задаче о ранце – 4 типа исходных данных:
- коэффициенты целевой функции (стоимость предметов, укладываемых в ранец);
- коэффициенты ограничения (объем предметов, укладываемых в ранец);
- объем ранца;
- булевы переменные.
Применительно к алгоритму, реализующему динамическое программирование применительно к задаче о ранце:
- дерево поиска;
- куст дерева поиска, высота которого определяет число одновременно вводимых в базис переменных;
- используемые методы вычисления оценок;
- используемые методы отсечения бесперспективных векторов переменных;
- время поиска решения.
- Формальная постановка задачи
- Обозначения.
Применительно к задаче о ранце:
Сi - i - й коэффициент целевой функции;
ai - i - й коэффициент ограничения;
b - объем ранца;
zi - i-я булева переменная.
Применительно к алгоритму, реализующему фронтальный спуск по дереву ветвлений:
G(X, U) - дерево поиска;
G’ (X’, U’) - куст дерева поиска, высота h которого определяет число 2h одновременно вводимых в базис переменных;
T - время поиска решения.
- Формальная постановка задачи
- Формальная постановка задачи о ранце
[pic 1]
- Вычисление нижней оценки величины F частичного плана
[pic 2]
- Вычисление упрощенной верхней оценки величины F частичного плана
Верхняя оценка величины F при условии, что в базис введено подмножество Z’ϵ Z переменных ниже определяется выражением:
[pic 3]
где I(Z’) обозначает множество индексов введенных в базис булевых переменных; I(Z) – множество индексов всех булевых переменных решаемой задачи.
- Вычисление уточнённой верхней оценки величины F частичного плана
[pic 4]
[pic 5]
- Аналитическая зависимость времени поиска решения от размерности задачи о ранце
Время решения в этом случае определяется двумя факторами – затратами времени на вычисление оценок t1 и на их сравнение t2 на каждой итерации. Найти аналитические зависимости верхней границы времени поиска решения методом динамического программирования от размерности задачи о ранце.
...