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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

79
5.2. Решение тестового примера задачи коммивояжера
модифицированным методом расширения цикла
Для решения задачи коммивояжера модифицированным методом
расширения цикла эстафетным методом (раздел 2) получено все
множество кратчайших маршрутов, записанное в совмещенной матрице
(табл. 31). Длина маршрута определена по формуле (2.1), а
среднее
расстояние между смежными объектами в цикле (
ij
ε
– удельное
расстояние) – по формуле
jinL
ijijij
≠
∀
= ,/
ε
, (5.1)
где
ij
n – количество активных (не включенных ранее в цикл) номеров
пунктов.
Вычисления по модифицированному методу расширения цикла
приведены в табл. 33. Они начинаются с начального цикла
1;1
1
=
Н
μ
. В
интервал (1;1) последовательно включается каждый из элементов
1
G∈
γ
,
при этом элемент
γ
с граничными элементами интервала связывается
кратчайшими маршрутами, что отмечается точками, стоящими между
соответствующими элементами. Кратчайшие маршруты выбираются из
табл. 31. Например, для
Н
r
1
,2 ,1
μγ
== имеем
1,6,,11,6,22;1121
0
1,2
0
2,1
1
2=∪=∪=⋅⋅=⋅⋅
−
μμγ
rr
jj ,
что и записано в графе 4 табл. 33 (строка 1), где включаемые в цикл
элементы выделены жирным шрифтом.
Величина приращения цикла ),(
γδ
r
t
, получаемая при этом,
вычисляется по формуле (5.2) [см. также (3.7)] по числовым данным
табл. 30, 31.
Минимум удельного расстояния ),(
1
γε
r соответствует (табл. 33)
текущему циклу, записанному в строках 1 и 5 (графа 4), для которого
5)2;1(
1
=
ε
. Необходимо проверить, существует ли среди приведенных
найденных циклов (строки 1 – 5) такой, что превосходит цикл
1,6,2,1,
5)2;1( =
ε
, то есть такой, для которого выполняются условия
доминирования (4.33).
В графе 7 ближайшим к
ε
(1;2) =
ε
(1;6) = 5 значением является
ε
(1;4) = 9. Соответствующий ему цикл 1,4,1 не включает в себя все
элементы цикла
1,6,2,1, то есть условия (4.33) не выполняются.

Страницы