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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

26
Объём вычислений зависит от конкретной топологической структуры
матрицы
с, поэтому заранее дать оценку требуемого числа элементарных
операций сравнения (
c
N
) и сложения (
+
N
) не представляется возможным.
Получим оценку числа элементарных операций
сверху, полагая, что
матрица
c заполнена полностью, кроме элементов главной диагонали
(
1=
ϕ
). Будем также считать, что строится всё множество кратчайших
маршрутов
и что на каждой из 1
−
n итераций определяется только один
кратчайший маршрут.
Требуемые количества операций сравнения и сложения на каждом
шаге процесса, получаемые путём непосредственного подсчёта в
соответствии со схемой алгоритма эстафетного метода, приведены в
табл. 10.
Общее число операций
1
тогда будет равно:
[]
,1,06/)2)(1(1)1(
3
1
1
nnnntttnN
n
t
c
≤−−=−+−−=
∑
−
=
(4>n ), (2.6)
,25,02/)2)(1()1(
2
1
1
nnntN
n
t
<−−=−=
∑
−
=
+
(n > 3). (2.7)
Таблица 10
t
c
t
N
+
t
N
t
I
1
2
−
n
0 1
2
1)3(2
+
−
n
1 2
3
2)4(3
+
−
n
2 3
… … … …
t
1)1(
−
+
−
− tttn
1
−
t t
… … … …
1−n 20
−
+
n 2
−
n 1
−
n
Чтобы приблизить оценку сверху
c
N
к реальному значению
c
N
,
предположим, что величина
c
N
пропорциональна коэффициенту полноты
ϕ
1
, тогда окончательно получим
.6/)2)(1( −−⋅== nnnNN
c
c
ϕϕ
(2.8)
1
Например, при
5,0
=
ϕ
и равномерном расположении элементов
ij
с
в матрице c
(шахматная доска!) ясно, что число сравнений уменьшится вдвое.

Страницы