- •Учреждение образования «высший государственный колледж связи»
- •Конспект лекций
- •Литература
- •Часть первая экономико-математические методы и модели Тема 1. Метод математического моделирования в экономике
- •Тема 2. Модель межотраслевого баланса
- •Тема 3. Задачи многокритериальной оптимизации
- •Тема 4. Элементы теории матричных игр
- •4.1 Парные матричные игры с нулевой суммой
- •4.2 Статистические игры. Критерии для принятия решений
- •Тема 5. Сетевые методы планирования и управления.
- •5.1 Общие понятия моделей спу
- •5.2 Правила построения сетевых графиков
- •Тема 6. Сетевые модели задач динамического программирования. Нахождение кратчайшего маршрута.
- •6.1 Основные понятия сетевых моделей
- •6.2 Матричный способ задания сетей
- •6.3 Задача о кратчайшем пути
- •Часть вторая эконометрика Тема 7. Предмет эконометрики
- •Тема 8. Корреляционный метод анализа связей. Модели парной регрессии
- •Тема 9. Корреляционный метод анализа связей. Модели множественной регрессии
- •Тема 10. Модели временных рядов
- •Содержание
6.3 Задача о кратчайшем пути
Одной из наиболее важных оптимизационных задач на сети является задача нахождения цепи, соединяющей два узла – исходный узел S и узел назначения Т, которая имеет минимальную возможную длину. Алгоритм нахождения кратчайшего пути для сетей без циклов предложен Дейкстрой в 1959г. и считается одним из наиболее эффективных. Он основан на приписывании узлам либо временных, либо постоянных пометок и имеет рекурсивный характер. Все вычисления выполняются с использованием информации об уже определенных на предшествующих шагах кратчайших расстояниях.
Для заданного узла j через обозначим оценку длины кратчайшей цепи из исходного узла S в этот узел. Если эта оценка не может быть улучшена, то она называется «постоянной пометкой» и обозначается . В противном случае она называется «временной пометкой». Обозначим через y номер вершины, получившей постоянную пометку последней. Алгоритм состоит из трех шагов.
Шаг 1. Всем узлам, кроме исходного, приписываются временные пометки, равные , т.е. . Исходному узлу приписывается постоянная пометка, равная нулю, т.е. и .
Шаг 2. Рассматриваем все вершины j, смежные с последней получившей постоянную пометку вершиной и имеющие временные пометки. Сравниваем величину временной пометки с суммой величины последней постоянной пометки и длины дуги , ведущей изy в рассматриваемую вершину. Временной пометке рассматриваемого узла присваиваем минимальное значение из двух сравниваемых величин:
.
Среди всех временных пометок выбираем минимальную (пусть это пометка вершины ) и делаем ее постоянной, т.е. и . Кроме того, помечаем дугу , ведущую в выбранную на данном этапе вершину. Если все временные пометки равны бесконечности, т.е. , то в исходном графе отсутствует путь из S в эти вершины и вычисления заканчиваются. Шаг 3. Если последняя постоянная пометка приписана узлу Т , то алгоритм завершает работу: кратчайший путь из вершины S в узел назначения Т найден. Иначе повторяем шаг 2.
В процессе решения помеченные дуги образуют в исходном графе ориентированное дерево кратчайших путей с корнем в вершине S – т.е. путь от вершины S до любой вершины, принадлежащей дереву, – кратчайший. Кроме этого, если вершина y принадлежит кратчайшему пути из S в j, то часть этого пути, заключенная между у и j, является кратчайшим путем из вершины у в j.
Алгоритм Дейкстры может быть выполнен непосредственно на сети.
Пример. Сеть дорог с двухсторонним движением задана матрицей расстояний в км (матрицей весовых коэффициентов). Необходимо найти для данной сети дорог самый короткий маршрут из пункта 1 в пункт 10.
Узлы |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
3 |
4 |
0 |
0 |
9 |
0 |
0 |
2 |
3 |
0 |
0 |
2 |
9 |
8 |
8 |
0 |
3 |
4 |
0 |
0 |
0 |
6 |
7 |
0 |
7 |
4 |
0 |
2 |
0 |
0 |
5 |
0 |
1 |
0 |
5 |
0 |
9 |
6 |
5 |
0 |
0 |
6 |
8 |
6 |
9 |
8 |
7 |
0 |
0 |
0 |
0 |
6 |
7 |
0 |
8 |
0 |
1 |
6 |
0 |
0 |
2 |
8 |
0 |
0 |
7 |
0 |
8 |
6 |
2 |
0 |
Решение
Схематически сетевая модель задачи изображена на рис. 6.3 в виде неориентированной сети.
Рис. 6.3 Сетевая модель задачи.
Продемонстрируем работу алгоритма Дейкстры, отмечая временные и постоянные пометки непосредственно в узлах сети. Для этого каждый узел изобразим в виде овала и разделим его на три части следующим образом
Шаг 1. Исходному узлу приписываем постоянную пометку, равную нулю, т.е. и . Всем остальным узлам, приписываем временные пометки, равные , т.е. , j=2,…,8. Отметим это на сети:
Шаг 2. Узлы 2, 3 и 6 смежные с последним, получившим постоянную пометку узлом 1. Новые значения временных пометок этих узлов будут:
Минимальной временной пометкой является пометка узла 2, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу .Отметим это на сети:
Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.
Шаг 2. Узлы 4, 5, 6 и 7 смежные с последним, получившим постоянную пометку узлом 2. Новые значения временных пометок этих узлов будут:
Минимальной временной пометкой является пометка узла 3, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу .Отметим это на сети:
Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.
Шаг 2. Узлы 5, 6 и 8 смежные с последним, получившим постоянную пометку узлом 3. Новые значения временных пометок этих узлов будут:
Минимальной временной пометкой является пометка узла 4, т.к. поэтому она становится постоянной. Подчеркиваем ее и Помечаем дугу .Отметим это на сети:
Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.
Шаг 2. Узлы 5 и 7 смежные с последним, получившим постоянную пометку узлом 4. Новые значения временных пометок этих узлов будут:
Минимальной временной пометкой является пометка узла 7, т.к. она становится постоянной. Подчеркиваем ее и Помечаем дугу .Отметим это на сети:
Шаг 3. Поскольку узел 8 не помечен постоянной пометкой, переходим к шагу 2.
Шаг 2. Узлы 5 и 8 смежные с последним, получившим постоянную пометку узлом 7. Новые значения временных пометок этих узлов будут:
Минимальной временной пометкой является пометка узла 8, т.к. она становится постоянной. Подчеркиваем ее и Помечаем дугу .Отметим это на сети:
Шаг 3. Поскольку узел 8 помечен постоянной пометкой, то алгоритм завершает работу: кратчайший путь из узла 1 в узел назначения 8 найден.
Построенное дерево кратчайших путей состоит из дуг (1,2), (1,3), (2,4), (4,7), (7,8) (они помечены на последней сети). Кратчайший путь от узла 1 до узла 8 составляет 8 км, т.к. постоянная пометка этого узла и состоит из дуг (1,2), (2,4), (4,7), (7,8).