Назад в библиотеку

          Поиск оптимального пути в динамически изменяющемся графе

Авторы: Пастухова Ю.Г., Фатеева Т.А., Затонский А.В.

Источник: Публикация [Перейти]

Целью работы является нахождение оптимального пути в графе, веса ребер которого изначально известны с определенной вероятностью, за ограниченное время, с условием возвращения в точку начала движения.

В соответствии с целью работы были сформулированы следующие основные задачи:

1. реализация поиска оптимального пути на каком-либо языке программирования;

2. в нашем случае понятие оптимального пути включает в себя не только поиск кратчайшего пути, но и обход вершин с максимальными весами;

3. применение алгоритма Дейкстры и усовершенствование этого алгоритма в плане временного ограничения, а также дополнение его условием возвращения в точку начала движения;

4. добавление в программу функции графического изображения.

Практическая значимость работы подтверждается возможностью использования данного проекта в следующих сферах.

1. Рогейн или спортивное ориентирование. При ограниченных возможностях участника (он или перемещается, или разрабатывает оптимальный маршрут) и неопределенности состояния трассы проект дает возможность провести имитационное моделирование прохождения дистанции и статистическими методами построить оптимальную стратегию.

2. Схема движения дежурного транспорта предприятия. Появляется возможность составления оптимального графика движения с учетом величины и вероятности задержек дежурной бригады на осматриваемых объектах. Аналогичной является задача осмотра объектов экипажем службы безопасности при визуальной охране.

3. План распределения машин по мере поступления заявок в таксопарке, с учетом местонахождения такси. Вероятность поступления заявок на перевозки, определяемая распределением населения по территории города, наличием и циклами суточной активности посещаемых объектов, позволяет на основе результатов имитационного моделирования перевозок динамически распределять свободные машины такси по городу, чтобы минимизировать их простои.

Из дискретной математики, в частности, теории графов, известны следующие аналоги задачи, для которых разработаны методы решения:

Граф представляет собой множество точек плоскости, называемых вершинами, и множество направленных отрезков, соединяющих все или некоторые из вершин и называемых дугами. Математически граф можно определить как пару множеств.

Т.к. в нашей задаче из каждой вершины можно попасть во все другие, то граф является полным.

Маршрутом в графе называется чередующаяся последовательность вершин и ребер v0, e1, v1,e2, v2, …, ek, vk,

в которых любые два соседних элементов инцидентны. Маршрут в нашем графе должен быть замкнутым, т.е. v0 = vk – выполняется условие возвращения в точку начала движения.

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведем наиболее часто используемых представлений с указанием характеристики n(p,q) – объема памяти для каждого представления p, (q – число ребер):

представление графа с помощью квадратной булевой матрицы M : array [1..p, 1..p] of 0..1, отражающей смежности вершин, которая называется матрицей смежности, для которойn(p,q)=O(p2).

представление графа с помощью матрицы инциденций, для которой n(p,q)=O(p× q).

представление графа с помощью списка смежности, причем для ориентированных графов n(p,q)=O(p+q).

представление графа с помощью массива дуг и для массива ребер (или дуг), n(p,q)=O(2q).

Обход графа – это некоторое систематическое перечисление его вершин (и/или ребер). Длиной пути называется сумма длин дуг, входящих в этот путь. Наиболее часто на практике встает задача отыскания кратчайшего пути. Существуют два классических алгоритма ее решения.

Алгоритм Флойда находит все кратчайшие пути между всеми парами вершин в (ор) графе. В этом алгоритме для хранения информации о двух путях используется матрица H[1..p, 1..p], где, если k – первая вершина, достигаемая на кратчайшем пути из i в j; 0, если пути из i в j нет.

Вход: матрица C[1..p,1..p] длин дуг.

Выход: матрица Т[1..p,1..p] длин путей и матрица H[1..p,1..p] самих путей.

 

for i from 1 to p do

for j from 1 to p do

T[i,j]:= C[i,j] { инициализация }

if C[i,j] = ∞ then

H[i,j]:= 0 { нет дуги из i в j }

else

H[i,j]:= j { есть дуга из i в j }

end if

end for

end for

for i from 1 to p do

for j from 1 to p do

for k from 1 to p do

if i≠j&T[j,i]≠∞&i≠k&T[i,k]≠∞&(T[j,k]=∞VT[j,k]>T[j,i]+T[i,k])

then

H[j,k]:=H[j,i] { запомнить новый путь }

T[j,k]:=T[j,i]+T[i,k] { и его длину }

end if

end for

end for

for j from 1 to p do

if T[j,j]<0 then

stop { нет решения: вершина j входит в цикл отрицательной длины }

end if

end for

end for

 

Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в  графе, если длины дуг неотрицательны.

Вход: орграф G(V,E), заданный матрицей дуг С:array[1..p,1..p] of real; s и t – вершины графа.

Выход: векторы T:array[1..p] of real; и H:array[1..p] of 0..p. Если вершина v лежит на кратчайшем пути от s к t, то T[v] – длина кратчайшего пути от s к v; H[v] – вершина, непосредственно предшествующая v на кратчайшем пути.

 

for v from 1 to p do

T[v]:=∞ { кратчайший путь неизвестен }

X[v]:=0 { все вершины не отмечены }

end for

H[s]:=0 {s ничего не предшествует }

T[s]:=0 { кратчайший путь имеет длину 0…}

X[s]:=1 {… и он известен }

v:=s { текущая вершина }

M: { обновление пометок }

for Г(v) do

if X[u]=0&T[u]>T[v]+C[v,u] then

T[u]:=T[v]+C[v,u] { найден более короткий путь из s в u через v }

H[u]:=v { запоминаем его }

end if

end for

t:= ∞; v:=0

{ поиск конца кратчайшего пути }

for u from 1 to p do

if X[u]=0&T[u]<t then

v:=u;t:=T[u] {вершина v заканчивает кратчайший путь из S }

end if

end for

if v=0 then

stop { нет пути из s в t}

end if

if v=t then stop { найден кратчайший путь из s в t }

end if

X[v]:=1 { найден кратчайший путь из s в v }

goto M

 

В настоящее время в среде Borland C++ Builder 6 реализоваy алгоритм поиска кратчайшего пути в графе, веса ребер которого заранее известны с определенной вероятностью. Исходными данными является массив расстояний между парами вершин графа (весов ребер), массив вариаций весов и стоимость вершин.

Путем имитационного моделирования определяется оптимальный путь обхода. Для обхода применяется вариант алгоритма Дейкстры, в котором реальный вес всех ребр, инцидентных вершине, определяется в момент прихода в вершину с учетом их начального веса и пределов стохастической неопределенности весов. Критерием оптимальности является соотношение весов пройденных ребер к стоимости вершин, задачей оптимизации его минимизация. Таким образом, достигается эффективность в смысле прохождения наибольшей суммы вершин за минимальное (или ограниченное) время, находящееся в корреляции с весом ребра.

 

Дальнейшая разработка заключается в дополнении программы временными ограничениями и другими необходимыми условиями, а также графическим изображением графа с выделенным оптимальным путем.

Библиографическая ссылка

1. Пастухова Ю.Г., Фатеева Т.А., Затонский А.В. ПОИСК ОПТИМАЛЬНОГО ПУТИ В ДИНАМИЧЕСКИ ИЗМЕНЯЮЩЕМСЯ ГРАФЕ // Фундаментальные исследования. – 2007. – № 12 – стр. 435-438