Курсовая: Поиск кротчайших путей по алгоритму Флойда - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Поиск кротчайших путей по алгоритму Флойда

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 414 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

- 22 - Министерство образования и науки Российской Федерации Воронежский Институт Высоких Технологий Факультет Информационных технологий Курсовая работа По дисциплине “ Дискретная математика ” По теме : “ Поиск кротчайших путей по а лгоритм у Флойда ” Выполнил: Студент группы ИН-044 Саунин А .В. Руководитель: доцент Белецкая С.Ю. Воронеж 200 7 Содержание Введение 1. Сведения о графах 2. Внутреннее представление графов 3. Основные понятия 4. Алгоритм Флойда 5 . Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин 6 . Задача Флойда 7 . Описание программы Поиск кратчайших путей. 8 . Листинг программы Заключение Список литературы Введение Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др. 1. Сведения о графах В теории графов существуют специфические методы решения экстре мальных задач. Один из них основан на теореме о мак симальном потоке и минимальном разрезе, утверждаю щей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V , равен минималь ной пропускной способности разрезов, разделяющих вершины U и V . Были построены различные эффективные алгоритмы нахождения макси мального потока. Большое значение в теории графов имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конеч ным множеством вершин и ребер, как правило, пробле ма существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение мно гих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допусти мых вариантов. Однако таким способом удается ре шить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, на ходящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока. Результаты и методы теории графов применяются при реше нии транспортных задач о перевозках, для нахож дения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управ лении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в пост роении различных дискретных устройств, в програм мировании и т. д. Граф G (рис.1) задается множеством точек ( вершин ) х 1 , х 2 ,..., х n . (которое обозначается через Х) и множеством линий ( ребер ) а 1 , а 2 ,...,а m . (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами , и граф с такими ребрами называется ориентированным графом, (рис.2). Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой. Если ребра не имеют ориентации, то граф называется неориентированным (рис 3), (двухстороннее движение). В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х 1 ,х 3 ) относится к дуге а 1 . Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рис. 2: Г (х 1 )= х 2 , х 3 , т.е. вершины х 2 и х 3 являются конечными вершинами дуг, у которых начальной вершиной является вершина х 1 . На рис. 3: Г (х 1 )= х 2 , х 4 , х 5 , (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.) Путем (или ориентированным маршрутом ) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Так, на рис. 5 последовательности дуг а 6 , а 5 , а 9 , а 8 , а 4 . (1) а 1 , а 6 , а 5 , а 9 . (2) а 1 , а 6 , а 5 , а 9 , а 10 , а 6 , а 4 . (3) являются путями. Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а 6 в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет. Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер д 1 , д 2 ,..., д q , в которой каждое ребро а q за исключением первого и последнего ребер, связано с ребрами а i-1 и а i+1 своими концевыми вершинами. Последовательности дуг: д 2 , д 4 , д 8 , д 10 , (4) д 2 , д 7 , д 8 , д 4 , д 3 , (5) д 10 , д 7 , д 4 , д 8 , д 7 , д 2 . (6) в графе, изображенном на рис. 5, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х 2 , х 5 , х 4 , х 3 , х 5 , х 6 . Иногда дугам графа приписываются числа, называемые весом, стоимостью , или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами . А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным . При рассмотрении пути µ представленного последовательностью дуг ( д 1 , д 2 ,..., д q ), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е. Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости/длины), задаваемые матрицей С=[c ij ]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s x до заданной конечной вершины t x, при условии, что такой путь существует t R(s) (здесь R(s)-множество, достижимое из вершины s.) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi- некоторая его вершина, то, двигаясь от s к х i , обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым ( ) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса. Следующие задачи являются непосредственными обобщениями сформулированной выше задачи о кратчайшем пути. 1)Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами х i X. 2)Найти кратчайшие пути между всеми парами вершин. Почти все методы, позволяющие решить задачу о кратчайшем (s-t)-пути, дают также (в процессе решения) и все кратчайшие пути от s к х i . Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами. С другой стороны, задача №1 может быть решена либо n-кратным применением алгоритма задачи №2, причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма. Наиболее распространенные методы их решения – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе). 2 . Внутреннее представление графов Существуют различные способы внутреннего представления графов в оперативной памяти ЭВМ, в том числе в виде списков (массивов) вершин и ребер, списков (массивов) смежности, матриц смежности, а также в виде комбинаций этих структур хранения. Выбор внутреннего представления оказывает решающее влияние на эффективность выполнения различных операций над графами и во многом определяет "технологию" использования той или иной библиотеки в прикладных программах. Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек. Списки вершин и ребер Граф представляется в виде двух списков, один из которых содержит указатели на его вершины, второй - на ребра (как всегда, каждое ребро хранит в себе указатели на инцидентные ему вершины). Данная структура хранения обеспечивает эффективное добавление в граф вершин и ребер, а также итерацию по вершинам и ребрам. В то же время, это представления неудобно, когда необходимо определить ребра, инцидентные заданной вершине графа. Списки смежности Граф представляется списком входящих в него вершин. В свою очередь, каждая вершина содержит список инцидентных ей ребер (или списки входящих и исходящих дуг в случае орграфов). Данное представление обеспечивает эффективное добавление в граф вершин и ребер, итерацию по вершинам графа и доступ к ребрам, инцидентным заданной вершине, но не поддерживает итерацию по ребрам графа. Матрицы смежности Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин). Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее "дорогой" операцией при использовании динамических массивов является добавление элемента, поскольку в худшем случае для этого требуется выделить новый блок памяти увеличенного размера, скопировать содержимое старого блока памяти в новый и освободить старый блок, причем, по крайней мере, этап копирования имеет сложность O(n). В то же время, в среднем операция добавления вершин (ребер) в AGraph выполняется более эффективно. Это достигается за счет того, что при увеличении размера динамического массива (вектора) в библиотеке Vectors память выделяется сразу для нескольких элементов, поэтому в большинстве случаев операция добавления элемента не требует фактического изменения размера вектора. 3. Основные понятия . Граф без циклов называется ациклическим или лесом. Связный ациклический граф называется деревом. Если G-лес , то каждая его компонента является деревом. Остов графа – это дерево, являющееся остовным подграфом. Остовной подграф – это подграф, множество вершин которого совпадает с множеством вершин графа. Любой связный граф имеет остов . Обратно, если граф имеет остов, то он – связный. Если граф имеет циклы , то, последовательно удаляя ребра из циклов до получения ациклического подграфа, получим остов. Причем, удаление ребра из цикла графа не нарушает его связности, т.к. такие ребра не являются мостами. Ребро x и вершина v называются покрывающими друг друга, если они инцидентны. Множество вершин, покрывающих все ребра, называется вершинным покрытием графа. Множество ребер, покрывающих все вершины, называется реберным покрытием графа. Представляет интерес наименьшие по числу вершин и ребер покрытия. Если ребрам графа приписаны веса, то можно ставить вопрос о реберном покрытии, имеющем наименьший суммарный вес. Постановка задачи. Пусть G=(V,X)-связный взвешенный граф. Обозначим c ij =c(v i ,v j ) вес ребра v i ,v j . Требуется найти остов, имеющий наименьшую сумму весов ребер. Пример. Алгоритм решения. 1. Включить в остов одну произвольную вершину w. Пример. 2. Рассмотреть все вершины v j , еще не принадлежащие остову. Если вершина v j не смежна вершине w, принадлежащей остову, то она получает метку [0;М], где М- бесконечно большое число. Если вершина v j имеет смежную вершину w,которая принадлежит остову, то вершина получает метку [a ;b ], где a=номер вершины w; b = c(w,v j ); Пример. 3. Из всех вершин, не принадлежащих еще остову, выбираем вершину V* с минимальным значением b и включаем ее в остов вместе с ребром (v,V*), где v- вершина, номер которой совпадает со значением метки a вершины V*. Пример. 4. Если число вершин, принадлежащих остову, равно числу вершин графа, то кратчайший остов найден, задача решена. Пример. Иначе – перход к шагу 5. Пример. 5. Корректируем метки вершин v j , которые еще не принадлежат остову и смежны вершине V*: если b j > c(V*,v j ), то b j = c(V*,v j ) a j = V*, если b j <= c(V*,v j ), то метка вершины не изменяется. После окончания помечивания – переход к пункту 3. Пример. Пример. Задание. Пункт 1 . Пункт 2. Пункт 3. Пункт 4. Пункт 5. Результат. 4 . Алгоритм Флойда Присвоить c ij =0 для всех i=1,2,...,n и c ij = , если в графе отсутствует дуга (x i x j ). Присвоение начальных значений. Шаг 1. присвоить k=0; Шаг 2. k=k+1. Шаг 3. Для всех i<>k, таких, что c ik <> , и для всех j<>k, таких, что c ik <> , с ij = [min[c ij , (c ik + c kj )]. (9) Проверка на окончание. Шаг 4. Если k=n, то матрица [с ij ] дает длины всех кратчайших путей. Остановка. Иначе перейти к шагу 2. На практике часто требуется найти не только кратчайший путь, но также второй, третий и т. д. кратчайшие пути в графе. Располагая этими результатами, можно решить, какой путь выбрать в качестве наилучшего. Для решения этой задачи нужно воспользоваться методом Йена (1971г.). Для которого: t-k-й кратчайший путь от s к t, где -соответственно 2-я, 3-я,…, qk-я вершины k-го кратчайшего пути. P i k - "отклонение от пути P k-1 в точке i" т. е. P i k -кратчайший из путей, совпадающих с P i k-1 от s до i-й вершины, а затем идущий к вершине, отличной от (i+1)-х вершин тех (ранее уже построенных) кратчайших путей P i (j=1,2,…,k-1), которые имеют те же самые начальные подпути от s к i-й вершине, не проходящему ни через одну из вершин s, x 2 k-1 , x 3 k-1 ,..., x i k-1 участвующих в формировании первой части пути P i k . Отсюда следует, что путь P i k будет являться простой цепью (путь, в котором каждая вершина используется не более одного раза.). Первый подпуть s, x 2 k , x 3 k ,..., x i k (совпадающий с s, x 2 k-1 , x 3 k-1 ,..., x i k-1 ) пути P i k называется его корнем и обозначается R i k , а второй подпуть x i k ,...,t пути P i k называется ответвлением и обозначается через S i k . Алгоритм начинает работу с нахождения P 1 с помощью алгоритма Дейкстры. Этот путь помещается в список L 0 (который должен содержать k-е кратчайшие пути). В общем случае для нахождения P k нужно уже иметь кратчайшие пути P 1 ,P 2 , P k-1 . 5 . Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин Процедура находит пути минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент w i j равен весу ребра соединяющего i -ую и j -ую вершины. При этом полагаем, что W[i,i]=0 для всех i . Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи. Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный ( W[i,j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым) Алгоритм Флойда предполагает последовательное преобразование матрицы весов W . В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов: D 0 =W d m+1 [i,j]=min d m [i,j], d m [i,(m+1)] + d m [(m+1),j] , где i<>j; d m+1 [i,i]=0. преобразование проделывается для m=1..n , где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное d m [i,m]+d m [m,i] для какого-нибудь i , то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима. На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i , если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса. Заметим, что если граф неориентированный, то W а также все матрицы получаемые в результате преобразований симметричны и следовательно достаточно вычислять только элементы расположенные выше главной диагонали. 6 . Задача Флойда Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров. Инициализация: 1. Построим матрицу D 0 размерности |V| x |V|, элементы которой определяются по правилу: 1. d ii 0 = 0; 2. d ij 0 = Weight(v i , v j ), где i<>j, если в графе существует ребро (дуга) (v i , v j ); 3. d ij 0 = бесконечность , где i<>j, если нет ребра (дуги) (v i , v j ). 2. m:=0. Основная часть: 1. Построим матрицу D m+1 по D m , вычисляя ее элементы следующим образом: d ij m+1 =min d ij m , d i(m+1) m + d (m+1)j m , где i<>j; d ii m+1 =0 (*). Если d im m + d mi m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v i ; ВЫХОД. 2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D |V| равны длинам кратчайших путей между соответствующими вершинами; Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов p ij =i. Каждый раз, когда на шаге (1) значение d ij m+1 будет уменьшаться в соответствии с (*) (т.е. когда d i(m+1) m + d (m+1)j m
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Ты чего в универе не был?
- А зачем? Сегодня же 42-ое августа.
- Сегодня 11 сентября.
- Не говори так...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru