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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

35
2,3,2
1
2
=
μ
(2º). Полученное решение
422,4,6,5,3,1,2
5
2
=L
, проходя
цепочку 8º+, 9º–, 11º–, 12º, заменяет прежнее лучшее решение 62
5
1
=L на
42
5
2
=L (12º).
Далее выполняется переход 10º к очередному варианту –
3,4,3
1
3
=
μ
,
(2º). Полученный третий вариант решения
423,1,2,4,6,5,3
5
3
=L совпадает
(табл. 12) с лучшим (11º+). Это решение записывается как оптимальное
(13º).
Примечание. Если бы очередной начальный вариант
1
2
μ
, как и
1
1
μ
, дал бы ошибочное решение 62
5
2
=L , совпавшее с первым, то
полученный согласно 11º+ результат также был бы ошибочным.
Такой случай наиболее возможен, если вероятность
1
P низка и,
следовательно, вероятность получения подряд двух неверных
решений
()
2
1
1 P− велика. Снизить вероятность ошибочного решения
можно заменой начального значения
∞
=
0
L
на лучшее решение,
полученное из ряда m вариантов. Приняв, например, 2,0
1
=P при
10=m , согласно (2.8) почти достоверно можно утверждать, что
лучший из этих 10 вариантов – оптимальный.
Другой способ снижения вероятности получения ошибочного
решения состоит в прекращении процесса не после однократного, а
после, например, двукратного совпадения лучших вариантов.
Указанные доработки не повлияют существенно на порядок и объем
вычислений.
Как и большинство неформальных
(эвристических) методов, метод
расширения цикла также является приближенным. Полагая, что выбор
начального цикла для вычисления оптимального гамильтонова (полного)
цикла равновероятен, оценим относительную статическую погрешность
метода расширения цикла ε по данным табл. 12 для одного произвольно
взятого начального цикла:
(
)
(
)
127,0
4215
442621
1
0
01
=
⋅
⋅−
=
−
=
∑
=
−
b
N
l
n
l
b
L
LL
N
ε
(12,7%),
где
2
nb
CN =
– общее количество возможных вариантов; l – номер варианта.
Если снять жесткое условие об однократности включения номера
вершины в цикл, то в ряде случаев некоторого улучшения полученного
решения можно добиться путем проверки и выполнения
первого
необходимого условия оптимальности: расстояние между любой парой
смежных вершин
(i,j) в решении равно длине кратчайшего маршрута
между ними
.

Страницы