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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

96
:1
=
t
⎯
→
⎯
52 ►
(
)
2;5
1
,
1
2,5
==⇒
lk
πμμ
, ( 2
1
=j )3=≠
l
, (6.3)
где в кружках записаны номера вершин; под дугой указана её пропускная
способность 28
2,5
=
с ; ► – знак прекращения процесса;
t
j – номер
конечной вершины (пункта) маршрута, полученного при оценке
1
3,5
π
.
Поскольку при данной оценке маршрута
t
lk,
μ
не существует, то
необходимо улучшить оценку, уменьшив её значение.
Так как значения оценок принадлежат множеству значащих элементов
матрицы
с , то в качестве новой оценки
1
,
+
t
lk
π
можно взять элемент
t
lkij
c
,
π
< , ближайший к
t
lk,
π
. В данном случае в качестве такой оценки
следовало бы взять
27
5,2
2
3,5
== c
π
, однако путём построения маршрутов
можно убедиться, что при оценках
}2427{
2
2,6
÷=
π
маршрута, отличного от
(6.3), получено не будет. Для задач больших размеров это может привести
к существенному увеличению объема вычислений, поэтому рассмотрим
более эффективный подход к определению очередной оценки,
существенно уменьшающий число итераций.
Поскольку уменьшение оценки
t
lk,
π
ведет к увеличению количества
«рабочих» элементов, то необходимо обеспечить их появление, прежде
всего
в строках матрицы с , номера которых соответствуют элементам
построенного на основе оценки
1
3,5
π
маршрута. Это обеспечит
возможность продления маршрута и его разветвления, увеличивая при
этом вероятность достижения нужного пункта
3=
l
. В
рассматриваемом примере новую оценку
2
3,5
π
следует искать в строках,
номера которых
i
образуют построенный маршрут
=
t
I
{
t
jk
t
ii
,
|
μ
∈ },
=
1
I
{2;5}
в соответствии с формулой
t
Ii
t
lk
∈
+
= max
1
,
π
{
t
Ij∈
max {
ij
c }},
t
t
I
I
I
=
,
=
I
{ };1 ni = , (6.4)
где
t
I
– дополнение к множеству
t
I
;
I
– полное множество индексов.
28

Страницы