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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

121
()
х
x
min
0
,
1
max, →
⎭
⎬
⎫
⎩
⎨
⎧
≤≤
=
jx
L
nj
R
m
L
, (7.14)
(
)
1,,
=
∈
RMAGx ,
где
0
, jx
L – кратчайший путь от точки x до пункта
(
)
njA
j
,1= ;
()
MAG , –
граф дорожной сети.
В отличие от предыдущих двух задач оптимальная точка
x может
находиться и на дуге (ребре) графа. Например, на графе с двумя
вершинами точка
x будет находиться в середине ребра, соединяющего
вершины. На неориентированном графе в виде разностороннего
треугольника точка
x будет находиться около вершины, к которой
прилегают две
меньшие стороны треугольника, в точке, делящей сумму
меньших сторон пополам.
В общем случае
()
3>n определение оптимального положения точки
x рассматриваемым методом смещений также начинается с вычислений
совмещенной матрицы кратчайших маршрутов (табл. 48). В каждой строке
k
i = определяется наиболее длинный маршрут (табл. 48, столбец
max
k
L ):
{
}
m
jkjk
jk
nj
k
jnkLLL
mm
,,,1,max
0
,
0
,
0
,
1
max
μ
⇒===
≤≤
, (7.15)
где
m
j – номер концевого пункта
m
j
A
наиболее длинного маршрута.
Номер пункта
1
k
i = начального размещения точки x определяется из
условия
{
}
10
,
0
,
1
1
0
,
1
maxminmin kiLLL
mm
jk
jk
nj
nk
jk
k
=⇒==
⎭
⎬
⎫
⎩
⎨
⎧
≤≤
≤≤
. (7.16)
Таким пунктом для рассматриваемого примера (табл. 47) является
пункт
⎟
⎠
⎞
⎜
⎝
⎛
=
6
16
kA . Дальнейшая оптимизация возможна путем смещения
точки
x от пункта
6
1
A
A
k
=
по начальной дуге (6;4) маршрута
0
1,6
0
,
1
μμ
=
m
jk
. Условие (7.15) разбивает множество
номеров пунктов на
две группы:
{} { }
mm
j 5,4,1= – номера концевых пунктов тех маршрутов,
длина которых убывает (индекс m) при смещении точки
x по начальной
дуге (ребру) маршрута (7.15);
{
}
{
}
6,3,2=
B
j – множество номеров пунктов,

Страницы