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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

30
3.2. Метод расширения цикла, алгоритм, пример вычисления
и эффективность алгоритма
Суть метода расширения цикла состоит в следующем. Вначале по
определенным правилам формируется
начальный цикл
1
k
μ
, и далее в ходе
решения последовательно в промежутки между вершинами текущего
цикла
t
k
μ
по определенным правилам включаются другие вершины графа,
еще не вошедшие в текущий цикл
t
k
μ
. Процесс заканчивается после
включения всех вершин в цикл (1
−
=
n
t
).
Правила формирования начального цикла и включения в него вершин
определяют степень эффективности получаемого решения и требуемый
объем вычислений. Наиболее простая версия метода расширения цикла
состоит в следующем.
Между начальным и конечным номерами вершин (k = l) включается
номер j – любой из множества
{
}
t
n
t
jG
1−
=
оставшихся вершин
(
)
t
Gj ∈ .
Сформированный таким образом начальный цикл
kjk
k
,,
1
=
μ
не
исключает возможность получения оптимальной последовательности
номеров в конечном цикле
1
. Правило включения очередной вершины (ее
номера) в некоторый из промежутков текущего цикла состоит в том, что
увеличение длины цикла δ
t
, получаемое на t-м шаге принудительного
включения номера вершины
А
j
, должно быть минимальным.
Приращение δ
t
k,j,i
, получаемое при пробном включении j между
номерами вершин А
k
и А
i
, вычисляется по формуле
. ,
,,
t
kijikj
t
ijk
Gjccc ∈−+=
δ
(3.1)
Первые два числа – это длина полученного ломаного маршрута между
вершинами A
k
и A
i
, а с
ki
– длина прежнего пути между этими же
вершинами дуги. Если
0
,,
<
t
ijk
δ
, то обходной путь короче, чем
прямой – с
ki
– длина цикла уменьшится.
На t-м шаге процесса текущий цикл будет содержать t + 1
промежутков (интервалов) для пробного включения очередного номера
t
Gj ∈ . Для каждого интервала по формуле (3.1) потребуется вычислить
n – 1 – t членов. Следовательно, для получения решения всего потребуется
вычислить N членов (3.1):
()()
3
2
1
2,0)3)(2)(1(
6
1
11 nnnnttnN
n
t
⋅<+−−=+⋅−−=
∑
−
=
.
1
Если в начальный цикл включить номера сразу двух вершин, то их очередность может
оказаться не такой, как в оптимальном цикле, а следовательно, решение уже не может быть
точным.

Страницы