Учебное пособие. Новосиб. гос. ун-т. — Новосибирск : РИЦ НГУ, 2014.
— 95 с. — ISBN 978-5-4437-0275-9.
Учебное пособие содержит материал по разделу основного курса
«Исследование операций», читаемого авторами на двух потоках
механико-математического факультета Новосибирского госуниверситета
и посвященного методам поддержки принятия оптимальных решений.
Пособие содержит необходимые определения, утверждения, алгоритмы,
примеры и упражнения. Пособие включает в себя разделы по синтезу
остовных деревьев и деревьев Штейнера, а также по построению
оптимальных путей и контуров.
Предназначено для студентов механико-математического факультета
НГУ, а также для всех, кто желает освоить курс самостоятельно.
Введение
Построение остовных деревьев
Минимальное остовное дерево. Алгоритмы Прима, Краскала, Борувки
Остовные деревья и их приложения
Примеры и упражнения Задачи построения кратчайших путей
Алгоритм Дейкстры
Алгоритм Беллмана – Форда
Алгоритм Флойда – Уоршелла
Примеры и упражнения Задача Штейнера
Постановки задачи Штейнера и ее сложность
Приближенные алгоритмы
Некоторые задачи синтеза сетей, использующие деревья Штейнера
Примеры и упражнения Задача коммивояжера
Вычислительная сложность
Конструктивные алгоритмы
Нижние оценки
Локальный поиск
Метаэвристики
Упражнения
Библиографический список
Минимальное остовное дерево. Алгоритмы Прима, Краскала, Борувки
Остовные деревья и их приложения
Примеры и упражнения Задачи построения кратчайших путей
Алгоритм Дейкстры
Алгоритм Беллмана – Форда
Алгоритм Флойда – Уоршелла
Примеры и упражнения Задача Штейнера
Постановки задачи Штейнера и ее сложность
Приближенные алгоритмы
Некоторые задачи синтеза сетей, использующие деревья Штейнера
Примеры и упражнения Задача коммивояжера
Вычислительная сложность
Конструктивные алгоритмы
Нижние оценки
Локальный поиск
Метаэвристики
Упражнения
Библиографический список