Новосибирский государственный университет
Кафедра теоретической кибернетики

Thin_Red_and_BlueA205.gif (1558 bytes)

А. И. Ерзин
Ю. А. Кочетов

Задачи маршрутизации

учебное пособие
Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 2014. – 95 с.

 

 

 

Полный текст книги   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