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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

14
В [5] рассматривается матричный подход к решению задачи поиска
кратчайшего маршрута. При этом в основу решения положено
использование двойственного симплексного метода решения задачи
линейного программирования (ЛП), поэтому естественным является
вопрос, задаваемый автором в [1; c. 81]: «Не будет ли это стрельбой из
пушки по воробьям?».
Известны и другие подходы к решению задачи поиска кратчайшего
маршрута
, однако и там остаются нерешёнными некоторые вопросы,
особенно в задачах больших размеров [6].
Краткий обзор проблемы, связанной с поиском кратчайшего
маршрута, позволяет сделать вывод о том, что она ещё не решена в
достаточно полной мере, и необходим дальнейший анализ, позволяющий
расширить возможности по решению задач больших размеров.
Формальную постановку будет удобно
записать в комбинаторном виде как
задачу минимизации целевой функции (2.1) на множестве
нескалярных
переменных
lk,
μ
:
,min)(
,
,
),(
,,
lk
lk
ji
ijlklk
cLL
μ
μ
μ
→
=
=
∑
∈
(2.1)
{
}
,;2
,
r
rn
kl kl
μμ
∈==1
,
где
−
r
возможное количество номеров промежуточных вершин в кортеже
lk,
μ
)2,0( −= nr .
Упрощение записи формальной постановки задачи по сравнению с её
записью в форме задачи математического программирования [5] получено
за счёт перехода от скалярных переменных к более сложным нескалярным
переменным
r
lk,
μ
, что позволяет предложить эффективный метод
решения поставленной задачи.
2.2. Эстафетный метод построения кратчайшего пути на графе
В основу эстафетного метода [3] положена следующая физическая
интерпретация поиска кратчайшего маршрута от вершины
k
A к
l
A .
Из узла-источника
k
A (рис. 1; табл. 1) по всем возможным
направлениям одновременно в момент
0=
c
k
T стартуют гонцы,
двигающиеся с
одинаковой единичной скоростью. Первым к некоторой
вершине прибудет тот гонец из данной группы (
лидер), у которого
расстояние до вершины будет меньше, чем у других. Момент прибытия
при этом будет численно равен длине пути, т.к. скорость равна единице.

Страницы