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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

133
Из (2) видно, что совместно с включенным в интервал (3;6) номером
γ = 7 вошел также номер j = 9, т.е. вошло два
активных (не включенных
ранее) нóмера: n
1
(1;7) = 2, {γ
1
} = {7;9} (табл. 3, строка 1). Далее
вычисляется удельный прирост длины цикла (3.9):
(
)
(
)
(
)
ttt
ε r, γ = δ r, γ /n r, γ , ε
1
(1;7) = 363/2=181.
Вычисление приращений (2) соответствует пункту 4
0
метода
расширения цикла (рис. 3). Структура алгоритма остается такой же и для
модифицированного МРЦ, если учесть, что дополнительно в 4
0
следует
вычислить и величину
(
)
t
ε r, γ . В строках 2 – 24 (табл. 3) записаны те же
величины для других сочетаний r и γ.
Минимальному значению
1
ε соответствует включение элемента γ
1
= 9
в интервал r
1
= 5 (
(
)
1
5;9 15ε = ), (рис. 3, 5
0
). Далее выполняется пересчет (6
0
)
текущих величин, новые значения которых записаны в строке 25 табл. 3.
Если еще не все индексы
t
γ G
∈
включены в цикл (-8
0
, т.е. G
t+1
≠∅), то
итерация повторяется (t = 2). Исходная информация записана в строке 25 и
снова выполняются 3 – 6
0
. В рассматриваемом примере величины
(
)
t+1
δ r, γ
изменятся только для интервалов, смежных с включенным номером γ
1
= 9
(в строке 25 включенный элемент выделен жирным шрифтом). В строках
26 – 31 записаны результаты для новых интервалов ({r}={5;6}). Для
неизменившихся интервалов используется ранее полученная информация,
скорректированная в связи с исключением элемента j
1
= 9 из правого
столбца табл. 3. Исключение индекса j = 9 из правого столбца приведет к
исключению строк 3, 7, 11, 15, 19, 23. Элементы
(
)
1
ε r, γ в строках 1, 14, 16,
18, 20 увеличатся в связи с уменьшением значения
(
)
(
)
t+1 t
nr,γ <n r,γ .
Новые значения удельных приращений находятся по рекуррентной
формуле
() ()
(
)
t
t+1 t
t+1
nr,
γ
ε r, γ = ε r, γ .
n
При выполнении 5
0
(вместо
2
δ используется
7
ε ) на шаге t = 2
минимальным оказывается элемент
2
ε (1;10) = 127, при этом в интервал
r = 1, (3;6) войдут все оставшиеся элементы (табл. 3, строка 4), и процесс
построения цикла при данном начальном цикле (k = 3) закончится. В
строке 32 записано полученное решение. Это решение сравнивается с
предыдущим, и если оно дает худший результат (+9
0
), то формируется
новый начальный цикл (10
0
) и т.д., до получения совпадающего решения
(+11
0
), что и является условием окончания процесса. Учитывая

Страницы