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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

27
Оценка
+
N
от коэффициента
ϕ
практически не зависит. Согласно
(2.8) и (2.7) для решенного примера (
0,4и6
=
=
ϕ
n ) оценки соответственно
равны 8=
c
N
и 8=
+
N
, что несколько отличается от реальных значений
(табл. 5; 7 ,11 ==
+
NN
c
). По мере увеличения размера n матрицы c
следует ожидать, что вследствие действия закона больших чисел
[10; с. 52], [11] расхождение в оценках будет уменьшаться.
Требуемый объем вычислений при построении конкретного маршрута
0
,
lk
μ
также оценится по (2.6) и (2.7), при этом степень полинома
уменьшится на 1 единицу, если появление пункта
l
A
равновозможно на
каждой итерации (рис. 2;
0
8).
Степень полинома в (2.6), (2.7) увеличится на 1 единицу при поиске
множества кратчайших маршрутов для всех сочетаний ),(
l
k
, nlk ,1, = .
Требуемый объём памяти ОЗУ в основном будет определяться числом
значащих элементов матрицы
c (для каждого элемента должны отводиться
ячейки для хранения трёх чисел ( jic
ij
,, )). Часть памяти выделяется для
алгоритма и хранения получаемых результатов (табл. 3).
Выводы
1. Если маршрут
0
,
lk
μ
является кратчайшим, то и маршрут от любой
его вершины до любой из последующих вершин также является
кратчайшим
, что следует из предположения об обратном. Действительно,
если длину какого-то из частных маршрутов удастся уменьшить, то
уменьшится и длина маршрута
0
,
lk
μ
, что противоречит условию.
2. Из первого вывода следует, что кратчайший маршрут можно
рассматривать как сплайн кратчайших маршрутов. Обратное неверно,
например:
122,5,4,3,62;55,4,3,6(
=
=∪ LL , однако 42;6
=
L – кратчайший
маршрут (табл. 9).
3. В кратчайший маршрут ни одна вершина не может быть включена
более одного раза, т.е. кратчайший маршрут –
элементарный путь (иначе
длину кратчайшего маршрута можно было бы уменьшить, что
противоречит определению кратчайшего маршрута).
4. В кратчайший маршрут ни одна дуга не включается более одного
раза, т.е. кратчайший маршрут –
простой путь [1; с. 13].
5. С несущественными изменениями эстафетный метод может быть
применён для построения запасного маршрута, кратчайшего из оставшихся
после построения основного кратчайшего маршрута.
6. Если совместно с матрицей
расстояний
ij
c=c задана и матрица

Страницы