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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

46
начального цикла
H
k
μ
при этом могут быть использованы циклы,
образованные двумя кратчайшими маршрутами (
H
kjk
H
k
⋅⋅
=
μμ
, например
H
131 ⋅⋅
μ
, табл. 15).
При определении кратчайшего гамильтонова пути также может быть
применен метод расширения цикла, при этом начальный путь
H
lk
,
μ
также
может быть записан как
H
ljk
⋅⋅
μ
.
При снятии ограничения об однократности включения каждой
промежуточной вершины в кратчайший цикл (путь) его длина, как
правило, уменьшается. Квазигамильтонов цикл (путь)
1
при этом может
быть найден методом расширения цикла с последующим улучшением на
основе проверки необходимого условия оптимальности [см. (3.5), (3.6)].
Для решения может быть использован и модифицированный метод
расширения цикла, при этом необходимость в проверке указанного
условия оптимальности отпадает.
2. При полной (
1=
ϕ
) и симметрической матрице с существует, как
минимум, два оптимальных решения классической задачи коммивояжера,
различающихся только ориентацией дуг в гамильтоновом цикле. При
неполной матрице смежности с (1
<
ϕ
) решение, как правило, одно и может
быть получено только модифицированным методом расширения цикла.
3. Решение, содержащее в себе повторяющиеся элементы, может быть
использовано для получения решения задачи о двух и более (в
зависимости от числа повторяющихся элементов) коммивояжерах.
Так, например, из решения (3.12) имеем
⎩
⎨
⎧
==
==
⇒=
.133,6,4,1,3,234,1,3,2,5,4
,183,2,5,4,3,84,3,6,4
311,,2,5,,,6,,1
22
11
LL
LL
L 3434 (3.13)
И в первом и во втором случае оба коммивояжера вместе могут
выходить только из пунктов A
3
или A
4
, что, однако, не исключает
возможность выхода каждого коммивояжера из любого пункта, входящего
в его маршрут. Из (3.13) следует, что суммарная длина пути обоих
коммивояжеров остается такой же, что и при одном, однако в первом
варианте оба будут на месте через 23 ед. времени, а во втором – через
18 ед., если полагать, что скорости
их перемещения постоянны и
одинаковы.
По аналогии с 1-м выводом (раздел 2), если решение задачи для
одного коммивояжера оптимально, то и разбиение большого цикла
1
Так именуется гамильтонов цикл (путь), свободный от ограничения об однократности
включения вершин.

Страницы