Методы оптимизации. Примеры и задачи

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

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

учебное пособие
Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 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.	Упражнения
Библиографический список