Новосибирский государственный университет
Кафедра теоретической кибернетики
|
А.
И.
Ерзин учебное пособие
Полный текст книги Marshrut_problem.pdf (1, 023 Mb)
|
Учебное пособие содержит материал по разделу основного курса «Исследование операций», читаемого авторами на двух потоках механико-математического факультета Новосибирского госуниверситета и посвященного методам поддержки принятия оптимальных решений. Пособие содержит необходимые определения, утверждения, алгоритмы, примеры и упражнения. Пособие включает в себя разделы по синтезу остовных деревьев и деревьев Штейнера, а также по построению оптимальных путей и контуров.
Предназначено для студентов механико-математического факультета НГУ, а также для всех, кто желает освоить курс самостоятельно.
Глава 1.
1.1.
Минимальное остовное дерево. Алгоритмы Прима, Краскала, Борувки
1.2.
Остовные деревья и их приложения
1.3.
Примеры и упражнения
Глава 2.
Задачи построения кратчайших путей
2.1.
Алгоритм Дейкстры
2.2.
Алгоритм Беллмана – Форда
2.3.
Алгоритм Флойда – Уоршелла
2.4.
Примеры и упражнения
Глава 3.
Задача Штейнера
3.1.
Постановки задачи Штейнера и ее сложность
3.2.
Приближенные алгоритмы
3.3.
Некоторые задачи синтеза сетей, использующие деревья Штейнера
3.4.
Примеры и упражнения
Глава 4.
Задача коммивояжера
4.1.
Вычислительная сложность
4.2.
Конструктивные алгоритмы
4.3.
Нижние оценки
4.4.
Локальный поиск
4.5.
Метаэвристики
4.6.
Упражнения
Авторы:
Адиль Ильясович Ерзин,
Юрий Андреевич Кочетов
Институт математики им. С.Л. Соболева СО РАН,
Новосибирский государственный университет
Редакция 11.06.2014