Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Кратчайшие пути




Поиск путей в графе

Оптимизационные задачи на графах

Большое количество практических задач формулируются как задачи поиска фрагментов графа или каких-то его характеристик, причем существует множество вариантов решения. Каждое решение оценивается числом, и среди множества решений нужно найти такое, для которого оценка имеет экстремальное значение - минимальное или максимальное. Чаще всего в качестве оценок используется сумма весов дуг или ребер, входящих в решение, - тогда оценка называется аддитивной, или произведение весов - тогда говорят о мультипликативной оценке. Наиболее часто ограничиваются случаем, когда веса дуг являются неотрицательными целыми числами.

Пусть в графе заданы две вершины a н и a к, названные соответственно начальной и конечной. Выделим несколько задач, связанных с поиском путей в графе:

- найти путь между начальной и конечной вершиной. Эта задача называется задачей поиска пути в лабиринте;

- найти минимальный путь между заданными вершинами;

- найти максимальный путь;

- найти цикл Эйлера.

 

Рассмотрим задачу поиска минимального пути между двумя заданными вершинами a н и a к в графе при условии, что каждой дуге (i,j) сопоставлен вес ci,j -неотрицательное число и оценка аддитивна. Если веса обозначают длину дуги, то задача формулируется как задача нахождения кратчайшего пути между заданными вершинами.

Рассмотрим классический алгоритм решения этой задачи - алгоритм Дейкстры, в основе которого лежит следующий

тезис Дейкстры: если кратчайший путь проходит через вершину ai, то длина части пути от a н до ai должна быть минимально возможной.

Алгоритм представим следующей последовательностью шагов.

1. Начальные присваивания. Каждой вершине, кроме начальной, сопоставим вес l(ai), равный бесконечности, назовем этот вес временным. Начальной вершине сопоставим вес, равный нулю: l(aн) = 0, назовем этот вес постоянным, вершину a н назовем текущей и обозначим как p.

2. Обновление весов. Всем вершинам, связанным с текущей по исходящим дугам и имеющим временные веса, изменим веса по правилу l(аi) =min (l(аi),l(p) p,j)

3. Смена текущей вершины. Среди вершин с временной оценкой найдем вершину с минимальным весом и назовем ее текущей, а ее вес - постоянным. Если это есть вершина a к, то перейдем к пункту 4, иначе -
к пункту 2.

 

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

 

Пример. Заданный граф приведен на рис. 2.4. Ход решения представим таблицей 2.2.

Выполняя шаг 4 алгоритма, выделим путь 12-9-6-3-2-1. Но существует еще один путь той же длины-12-9-8-5-4-1, так как для вершины 9 имеем два одинаковых по длине пути к началу, проходящих через вершины 8 и 6.

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

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 551; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.