Ерзин, А. И.
Задачи маршрутизации : учеб. пособие / А. И. Ерзин, Ю. А. Кочетов;
Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 2014. – 95 с.ISBN 978-5-4437-0275-9Учебное пособие содержит материал по разделу основного курса «Исследование операций», читаемого авторами на двух потоках механико-математического факультета Новосибирского госуниверситета и посвященного методам поддержки принятия оптимальных решений. Пособие содержит необходимые определения, утверждения, алгоритмы, примеры и упражнения. Пособие включает в себя разделы по синтезу остовных деревьев и деревьев Штейнера, а также по построению оптимальных путей и контуров.Предназначено для студентов механико-математического факультета
НГУ, а также для всех, кто желает освоить курс самостоятельно.ББК В173
УДК 519.8Введение
Глава
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. Упражнения
Библиографический список
