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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

108
7. ПОИСК ОСОБЫХ ТОЧЕК НА ГРАФЕ
7.1. Поиск точек с минимальной суммарной длиной маршрутов
Под особой точкой на графе будем иметь в виду точку,
расположенную в вершине или на ребре (дуге) графа и удовлетворяющую
заданным требованиям. Подобные требования возникают при решении
различных практических задач. Например, интерес может представлять
выбор места размещения базы (склада), сумма расстояний от которой до n
потребителей будет минимальной. При этом, как правило
, возникает
необходимость учета существующей дорожной сети, потребностей
клиентов (ожидаемые грузопотоки) и прочих факторов.
Другой класс задач подобного рода связан с выбором таких точек и их
количества, при которых время достижения любого пункта на графе не
будет превышать заданной величины (размещение пунктов скорой
помощи, пожарных команд и т.д.).
Список подобного
рода задач, возникающих на практике, можно
найти в [2,14], а также ознакомиться с некоторыми подходами к их
решению.
Рассмотрим решение некоторых
минисуммных задач [2],
простейшую из которых можно представить как поиск точки
x
на графе,
сумма расстояний от которой до каждой из вершин графа минимальна.
Формальную постановку такой задачи можно записать в виде
(7.1)
(
)
(
)
1,,
=
∈ RMAGx , (7.2)
где точка
x
лежит на одной из вершин или граней графа
G
;
0
,
jx
μ
–
кратчайший маршрут от точки
x до точки
j
A ;
(
)
0
,
0
,
jxjx
LL
μ
= – длина
маршрута
0
,
jx
μ
;
R
– заданное количество точек.
В основу решения положен
метод перемещений [18]. Суть метода
заключается в следующем.
Смещение точки
x
на величину
x
Δ
в одном направлении (точка
x
лежит на грани графа
G
) приводит к увеличению длин маршрутов к
каждому из некоторой совокупности
1
n пунктов и к уменьшению длин
2
n
маршрутов к остальным
12
nnn
−
= пунктам (вершинам графа). Если при
этом
(
)
1212
, nnnxnx >
Δ
>
Δ , (7.3)
()
0
, μ min,
,
1
n
LR
xj
j
Σ
=→
∑
=
x
õ

Страницы