Методы оптимизации на графах с векторными весами ребер
Описание
Пособие посвящено важному подклассу задач динамического программирования – задачам поиска оптимальных путей на графах. Для скалярных постановок рассмотрены два метода – рекуррентных уравнений Беллмана (применительно к задачам на графах) и метод Дейкстры, а также их связь с принципом Беллмана в форме достаточного условия. Далее задачи обобщаются на случай векторных весов ребер, вводятся понятия оптимальности по Парето и Слейтеру. Изучаются свойства скаляризованных задач, порождаемых двумя типами сверток – линейной и Гермейера, а также использование сверток при решении многокритериальных задач в сочетании с методами рекуррентных уравнений и Дейкстры. Описан метод построения множества эффективных путей, не использующий сверток. Для численных экспериментов представлена учебно – исследовательская программная лаборатория «Поиск оптимальных путей на графах с векторными весами ребер». Учебно-методическое пособие предназначено для студентов ННГУ, обучающихся по направлениям подготовки 01.03.02 «Прикладная математика и информатика» и 02.03.02 «Фундаментальная информатика и информационные технологии»
