Поиск оптимального пути в динамически изменяющемся графе
Авторы: Пастухова Ю.Г., Фатеева Т.А., Затонский А.В.
Источник:
Публикация [Перейти]
Целью работы
является нахождение
оптимального
пути в графе, веса ребер которого изначально известны с определенной
вероятностью, за ограниченное время, с условием возвращения в точку
начала
движения.
В соответствии с
целью работы были
сформулированы следующие основные задачи:
1. реализация
поиска оптимального
пути на
каком-либо языке программирования;
2. в нашем случае
понятие
оптимального пути
включает в себя не только поиск кратчайшего пути, но и обход вершин с
максимальными весами;
3. применение
алгоритма Дейкстры и
усовершенствование этого алгоритма в плане временного ограничения, а
также
дополнение его условием возвращения в точку начала движения;
4. добавление в
программу функции
графического изображения.
Практическая
значимость работы
подтверждается
возможностью использования данного проекта в следующих сферах.
1. Рогейн или
спортивное
ориентирование. При
ограниченных возможностях участника (он или перемещается, или
разрабатывает
оптимальный маршрут) и неопределенности состояния трассы проект дает
возможность
провести имитационное моделирование прохождения дистанции и
статистическими
методами построить оптимальную стратегию.
2. Схема движения
дежурного
транспорта
предприятия. Появляется возможность составления оптимального графика
движения с
учетом величины и вероятности задержек дежурной бригады на
осматриваемых
объектах. Аналогичной является задача осмотра объектов экипажем службы
безопасности при визуальной охране.
3. План
распределения машин по мере
поступления заявок в таксопарке, с учетом местонахождения такси.
Вероятность
поступления заявок на перевозки, определяемая распределением населения
по
территории города, наличием и циклами суточной активности посещаемых
объектов,
позволяет на основе результатов имитационного моделирования перевозок
динамически распределять свободные машины такси по городу, чтобы
минимизировать
их простои.
Из дискретной
математики, в
частности, теории
графов, известны следующие аналоги задачи, для которых разработаны
методы
решения:
- задача
о Кенигсбергских мостах;
- задача
о трех домах и трех колодцах;
- задача
о четырех красках.
Граф представляет
собой множество
точек
плоскости,
называемых вершинами, и множество
направленных отрезков,
соединяющих все или некоторые из
вершин и называемых дугами. Математически граф можно
определить как пару множеств.
Т.к. в нашей
задаче из каждой вершины
можно
попасть во все другие, то граф является полным.
Маршрутом
в графе называется
чередующаяся
последовательность вершин и ребер
в которых любые
два соседних
элементов
инцидентны. Маршрут в нашем графе должен быть замкнутым, т.е. 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