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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

34
интервалом
t
r
, в который был включен номер вершины
t
j
на
предыдущем шаге (см. t = 2). Расход памяти ОЗУ при этом
увеличится, т.к. придется сохранять приращения
t
δ
от предыдущего
шага.
После пересчета текущих величин (пункт 6º) осуществляется
переход к очередному шагу цикла (пункт 7º) и проверяется, закончено ли
формирование цикла. Если цикл еще не закончен (пункт 8º –, т.е.
≠
t
G
∅
или 1−≤ n
t
), то процесс продолжается (переход к 3º). В противном случае
(8º +, =
t
G
∅, т.е. 1−> n
t
) полученный k-й вариант решения
1−n
k
L по длине
цикла сравнивается с предыдущим. Если он хуже предыдущего (9º +), то
назначается k + 1-й исходный вариант (пункт 10º), и весь цикл расчетов
повторяется. Пункты алгоритма (9º – 12º) позволяют улучшить решение и
повысить его достоверность. Действительно, анализируя табл. 12, в
которой записана динамика полученного решения (3.3) и решений при
всех возможных 15
2
=
n
C начальных циклах
1
(элементы
t
j , включаемые в
цикл на
t
-м шаге, выделены жирным шрифтом), можно видеть, что
оптимальные решения в зависимости от начального цикла появляются с
некоторой частотой 73,015/11
1
=
=P . Следовательно, вычисляя
последовательно m вариантов с различными начальными циклами, можно
с вероятностью
(
)
m
m
PP
1
11 −−=
(3.4)
утверждать, что лучший из них является оптимальным.
При
3=m
для
73,0
1
=P вероятность
m
P близка к единице ( 98,0
3
≈P ).
Этот результат подтверждается данными табл. 12: практически любая
тройка случайно выбранных вариантов будет содержать хотя бы один
оптимальный.
Поскольку априори вероятность
1
P неизвестна, то в алгоритме (рис. 3)
реализована следующая схема останова процесса решения: процесс
прекращается после появления варианта,
совпадающего с лучшим к
этому времени вариантом, хранящимся в ОЗУ ЭВМ (12º). В соответствии с
этим правилом для полученного решения (3.3) будем иметь
∞=≤=
0
5
1
62 LL (9º–) и
∞
≠
62 (11º–), поэтому вместо ∞=
0
L в ОЗУ
записывается 62
5
1
=L ,
5
1
μ
(3.3) (12º). Вычисляются номер очередного
варианта начального цикла (10º) и исходные данные нового цикла –
1
Исходные циклы
),,(
1
kjk
μ
и
),,(
1
jkj
μ
приводят к одному и тому же решению, т.к. они
равносильны перестановке интервалов, что на решение не влияет.

Страницы