Лекции по параллельным вычислениям. Гергель В.П - 102 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

102
Далее полагают
i
i
,GG,
1
1
1
,
m,i,TT
i
i
1
2
2
и
ищут наименьшее значение
m,...,j,tt
j
i
1
1
, такое, что
nrt,,...,F
m
111
. (8.1)
Если такое значение не находится, то n решение задачи.
Если существует
t , удовлетворяющее (8.1), выделяют множество операто-
ров
r,...,,A
j
1 , для которых
jjj
tt
11
.
Заметим, что множество
A является подмножеством некоторого полного мно-
жества ВНО.
Затем вводят очередную комбинацию nr
связей, так чтобы длина кри-
тического пути в изменившемся при этом графе
G
не превысила T. Если та-
кая комбинация найдена, значение счетчика числа итераций увеличивают на
единицу:
, запоминают новые значения
i1
T
i2
и вновь ищут
наименьшее значение
t , удовлетворяющее (8.1) (если же искомой комбинации
связей не существует, либо все они уже испытаны, напротив, значение счетчика
числа итераций уменьшают на единицу:
, вводят очередную комбина-
цию nr
и также ищут наименьшее значение
t ).
Если при уменьшении индекса числа итераций оказывается, что
, т.е.
на первом же шаге не подтверждается предположение, что n решение задачи,
полагают
, вновь задают значения
i
i
,GG,
1
1
1
,
TT
i
i
2
2
. m,i 1 и повторяют поиск наименьшего значения
t , удовле-
творяющего (8.1).
Подчеркнем, что построение графа
' '
, ,
G X P
Г
по описанной схеме явля-
ется достаточным для решения задачи 1. Действительно, предположим внутри
каждого полного множества ВНО с числом операторов
n
r
в соответствии с

Страницы