ВУЗ:
Составители:
Рубрика:
138
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ .................................................................................................................... 6
ПРИНЯТЫЕ ОБОЗНАЧЕНИЯ ................................................................................................ 7
ВВЕДЕНИЕ ............................................................................................................................... 8
1. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ................................................................. 10
1.1. Основные понятия и определения.................................................................................................... 10
2. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА ГРАФЕ .............................................................. 13
2.1. Постановка задачи................................................................................................................................ 13
2.2. Эстафетный метод построения кратчайшего пути на графе ..................................................... 14
2.3. Алгоритм эстафетного метода (ЭМ)................................................................................................ 21
2.4. Оценка эффективности алгоритма................................................................................................... 25
Выводы ........................................................................................................................................................... 27
3. КЛАССИЧЕСКАЯ ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ РЕШЕНИЕ МЕТОДОМ
РАСШИРЕНИЯ ЦИКЛА
........................................................................................................ 28
3.1. Постановка классической задачи коммивояжёра ( 1
=
ϕ
)....................................................... 28
3.2. Метод расширения цикла, алгоритм, пример вычисления и эффективность алгоритма ... 30
3.3. Модифицированный метод расширения цикла, примеры вычислений
и эффективность метода
............................................................................................................................. 38
Выводы ........................................................................................................................................................... 45
4. ОБОБЩЕННАЯ ЗАДАЧА КОММИВОЯЖЕРА ............................................................... 47
4.1. Постановка обобщенной задачи коммивояжера........................................................................... 47
4.2. Алгоритм решения обобщённой задачи коммивояжера
методом расширения цикла при полной матрице расстояний (φ = 1) и пример расчёта
.......... 48
4.3. Модифицированный метод расширения цикла
и решение обобщенной задачи коммивояжера..................................................................................... 55
4.4. Решение обобщенной задачи коммивояжера методом
последовательного наращивания цикла
................................................................................................. 61
Выводы ........................................................................................................................................................... 74
5. СРАВНИТЕЛЬНАЯ ОЦЕНКА РАССМОТРЕННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ
КОММИВОЯЖЕРА
................................................................................................................ 75
5.1. Решение тестового примера задачи коммивояжера
методом расширения цикла....................................................................................................................... 75
5.2. Решение тестового примера задачи коммивояжера
модифицированным методом расширения цикла
................................................................................ 79
5.3. Решение тестового примера задачи коммивояжера
комбинированным методом расширения цикла
................................................................................... 82
5.4. Решение тестового примера задачи коммивояжера методом
последовательного наращивания цикла
................................................................................................. 82
5.5. Решение тестового примера обобщенной задачи коммивояжера
методом последовательного наращивания цикла
................................................................................ 85
5.6. Решение тестового примера обобщенной задачи коммивояжера
методом расширения цикла
....................................................................................................................... 87
5.7. Решение тестового примера обобщенной задачи коммивояжера
модифицированным методом расширения цикла
................................................................................ 88
Выводы ........................................................................................................................................................... 93
6. ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ.......................................................................... 93
6.1. Построение маршрута с максимальной пропускной способностью
методом улучшения оценок
...................................................................................................................... 93
6.2. Определение максимальной пропускной способности сети ..................................................... 99
Выводы ......................................................................................................................................................... 107
