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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

61
табл. 22 (для удобства вычислений принято ja
j
=
j
∀
, что, однако, не
снижает общности рассмотрения). Семейство кратчайших маршрутов и
их длин, вычисленное эстафетным методом (раздел 2), записано в табл.
23. Процесс решения модифицированным методом расширения цикла,
промежуточные данные и результаты решения представлены в табл. 24.
На первом шаге транзитных элементов не появилось, и проводить
дополнительных проверок не потребовалось. Вариант, помещенный в
строке
2, потребовал минимальных удельных энергозатрат (3,28)3(
1
=
ε
)
и явился исходным для шага 2
=
t
(табл. 24).
На втором шаге появились транзитные элементы. Все проверяемые
элементы оказались элементами кратчайших маршрутов, поэтому
дополнительных проверок не потребовалось (прочерки в графах 5, 7).
На шаге 3=
t
оказалось, что участки 3,2,6 (стрóки 14, 15) и 3,2,6
•
(стрóки 17, 18) не являются кратчайшими маршрутами (табл. 23).
Изъятие средних элементов (2 и
•
2) из соответствующих маршрутов
привело к уменьшению энергозатрат, значения которых записаны в
указанных строках рубрики 5.
Все элементы вошли в цикл (
=
4
G ∅) – процесс окончен.
Полученное решение
3
1
μ
улучшить какими-либо способами не удалось,
соответствующий ему маршрут проходит через указанные пункты
(рис. 1).
4.4. Решение обобщенной задачи коммивояжера
методом последовательного наращивания цикла
Анализ процесса решения модифицированным методом расширения
цикла подводит к выводу: использование таблицы кратчайших маршрутов
(табл. 23) при формировании цикла приводит к тому, что получаемое
решение (цикл) по существу является сочленением некоторой
упорядоченной совокупности кратчайших маршрутов. Действительно, для
полученного в табл. 24 решения имеем
)1,3,();(),4,3,()
,4,1()1,3,,,4,3,,4,1(
0
1
225566256 ∪∪∪==
μ
. (4.20)
Сочленяемые маршруты (табл. 23) являются кратчайшими. Возникает
вопрос: нельзя ли, не прибегая к довольно громоздкому
модифицированному методу расширения цикла, непосредственно с
помощью табл. 23 построить цикл путем его последовательного
наращивания некоторыми кратчайшими маршрутами? Каким принципом
следует руководствоваться при выборе сочленяемых маршрутов и

Страницы