Задачи маршрутизации: учебное пособие

Ерзин, А. И. Задачи маршрутизации : учеб. пособие / А. И. Ерзин, Ю. А. Кочетов ; Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 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. Упражнения Библиографический список