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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

65
В соответствии с полученной упорядоченной последовательностью
(
j
), по табл. 20
1
находится первый кратчайший маршрут (исходный пункт
1=
k
):
3,4,1
0
3,1
=
μ
. (4.21)
Из (4.21) видно, что попутно и по кратчайшему маршруту будет
доставлен груз
3
4
=a ед. в пункт
4
A . Следовательно, в соответствии с
установленной последовательностью (
j
) очередной груз из пункта
3
A
[см. формулу (4.21)] следует доставить в пункт
2
A . Соответствующий
кратчайший маршрут
0
2,3
μ
определяется из табл. 20: 2;3
0
2,3
=
μ
.
Соединение двух кратчайших маршрутов позволяет записать
начальную часть цикла, найденную за два шага процесса:
2,3,4,12;33,4,1
0
2,3
0
3,12,1
=∪=∪=
μμμ
. (4.22)
Два других кратчайших маршрута, также найденные по табл. 20
(
5;2
0
5,2
=
μ
, 1,4,2,5
0
1,5
=
μ
), в соединении с (4.22) образуют цикл, который
и является решением задачи:
1,,,5,2,3,4,11,4,2,55;22,3,4,1
0
1
42=∪∪=
μ
. (4.23)
Такое же решение было получено модифицированным методом
расширения цикла (табл. 21 и (4.14)).
Примечание. По табл. 20 можно убедиться, что решение (4.23)
удовлетворяет обоим необходимым условиям оптимальности:
любая смежная пара элементов образует кратчайший маршрут;
любой из повторяющихся элементов совместно со смежными также
образует кратчайший маршрут.
Подтверждение эффективности принципа убывания веса на двух
рассмотренных примерах не может являться достаточным условием для
утверждения о его справедливости в общем
случае. Более того, удалось
сформулировать такой пример, при котором указанное правило приводит к
явно неоптимальному решению. Такой контрпример представлен графом
1
Табл. 20 построена на основании табл. 18 (эстафетный метод).

Страницы