Название: Элементарные решения неэлементарных задач на графах. Учебное пособие
Автор: Берзин Е.А.
Издательство: Тверь: ТГТУ
Год: 2005
Формат: djvu
Страниц: 136
Размер: 5,92 Мб
Язык: Русский
Методы и алгоритмы, представленные в пособии, позволяют эффективно решать ряд оптимизационных задач на графах, имеющих прикладную направленность в экономике и технике. К таким задачам относятся: задача о кратчайшем пути; задача коммивояжера и ее обобщение; задача о пропускных способностях сетей; об оптимальном размещении баз, обслуживающих пунктов. Базовым методом, положенным в основу остальных методов, является эстафетный метод построения кратчайшего маршрута на графе. Он дает точное решение и требует минимального объема вычислений. Разработанные методы и алгоритмы являются новыми и позволяют решать задачи больших размеров. Для их использования не требуется специальной математической подготовки, что делает их удобными для студентов при освоении специальных дисциплин в технических вузах, а также для научных работников при решении сложных оптимизационных задач на графах элементарными методами.
Введение
1. Некоторые понятия теории графов
2. Задача о кратчайшем пути на графе
3. Классическая задача коммивояжера и ее решение методом расширения цикла
4. Обобщенная задача коммивояжера
5. Сравнительная оценка рассмотренных методов решения задач коммивояжера
6. Пропускная способность сети
7. Поиск особых точек на графе
Заключение
Приложение 1. Определение пропускной способности сети методом Форда-Фалкерсона и методом улучшения оценок
Приложение 2. Решение задачи коммивояжера размера 10 х 10 модифицированным методом расширения цикла
Библиографический список.
|
Навигация
Вход на сайт
Реклама
Элементарные решения неэлементарных задач на графах 
