Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 23 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

25
существуют два равных по длине кратчайших маршрута. Согласно
0
7 это
маршруты
5;1
0
5,1
=
μ
и .6)( ,5;4;1)5;4(4;1
0
5,1
0
5,1
0
5,1
=
⎟
⎠
⎞
⎜
⎝
⎛
′
==∪=
′
μμμ
LL
Так как 53
≠
=
l
, то согласно
−
0
8
0
10
начинается новый цикл (4
=
t
),
в ходе которого и будет построен искомый кратчайший маршрут
3,6,4,1
0
3,1
=
μ
(см. табл. 7; 8).
Циклический алгоритм достаточно прост, что обеспечивает решение
задач больших размеров ( 1000>n ) за приемлемое для практических целей
время.
2.4. Оценка эффективности алгоритма
Основными показателями метода, характеризующими его
возможности для решения задач данного класса, обычно являются
точность решения задачи, требуемые при этом объём вычислений и объём
оперативной памяти.
Несмотря на эвристическую основу эстафетного метода, анализируя
его вычислительную схему, можно убедиться, что на каждом шаге
процесса она приводит, по крайней мере, к одному кратчайшему
маршруту. Действительно, из табл. 1 видно, что от УИ
1
A никакой другой
маршрут не может быть короче, чем
34;1
0
4,1
==
μ
.
1
На шаге 2
=
t
оставшиеся гонцы достигнут пунктов
5
A ,
6
A
соответственно в моменты времени 6 и 8, а гонцы, стартовавшие из
4
A с
задержкой в
3
0
4,1
=L ед., придут соответственно к тем же пунктам в
моменты 3 + 3 = 6 и 3 + 2 = 5, при этом первым прибудет лидер
6,4
Л из
группы 4=i в пункт
6
A , т.к. из всех указанных времен его время
минимально (численно оно равно длине очередного кратчайшего
маршрута 5
0
6,1
=L , 6,4,1
0
6,1
=
μ
). Вводя понятие «лидер», мы получаем
возможность сократить количество элементарных операций и число
записей (табл. 7; 2=
t
). Удаляя из табл. 1 столбец, соответствующий
концевому пункту
l
A найденного кратчайшего маршрута, сокращаем
объём вычислений в дальнейшем.
Таким образом, путём введения
единой шкалы измерения времени
(длины пути) лидеров обеспечивается прямое сравнение их времен. Это
гарантирует точность решения и отсеивание доминируемых маршрутов.
1
Предполагается, что матрица с не содержит отрицательных элементов.

Страницы