Навигация
Алгоритм нахождения длиннейшего пути в графе
32842
знака
5
таблиц
1
изображение
4. Алгоритм нахождения длиннейшего пути в графе
4.1 Математическое описание задачи и методов её решения
Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х1,…, Хn}), и множества связей в парах вершин, которые называются дугами, или ребрами ((Хi, Хj) Î G) в зависимости от наличия или отсутствия направленности связи.
Ребром называются две встречные дуги (Хi, Хj) и (Хj, Хi). На графе они изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей.
Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.
Две вершины, являющиеся концевыми для некоторого ребра или некоторой дуги, называются смежными. Соответственно этот граф может быть представлен матрицей смежности либо матрицей инцидентности.
Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: «1» ставится в случае если вершина vi, инцидентна ребру uj; «0» – в противном случае.
Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.
Путь из начальной вершины хн к кончиной вершине хк – последовательность дуг, начинающаяся в вершине хн Î Х, заканчивающаяся в вершине хк Î Х, и такая, что конец очередной дуги является началом следующей: (хн, хi1) (хi1, хi2) (хi2… хik) (хik, xk) = (xн, хк).
Элементарный путь – путь, в котором вершины не повторяются.
Простой путь – путь, в котором дуги не повторяются.
Маршрут – последовательность ребер, составляющих, как и путь, цепочку.
Длина пути взвешенного графа определяется как сумма весов – его дуг. Если граф не взвешен, то можно считать веса дуг равными 1.
Кратчайшим путем между выделенной парой вершин хн и хк называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.
При построении длиннейшего пути рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполненных циклов. Длиннейший путь между хн и хк – путь, имеющий наибольшую длину среди всех возможных путей между этими вершинами.
Таким образом, нахождение длиннейшего пути – это поиск множества вершин, составляющих этот путь.
Волновой алгоритм получил свое название из-за того, что сам принцип его функционирования основан на «испускании волны,» какого-либо гипотетического возмущения по результатам которого имеется возможность судить о количестве смежных с выделенной вершин, а так же о расстоянии (длине дуги) до каждой из них.
Очевидно, что к каждой вершине могут идти от вершины X н несколько путей, суммы длин дуг по разным путям различны. При поиске длиннейшего пути следует выбирать максимальную сумму. Волны распространения веса по разным путям доходят до каждой вершины последовательно, при очередной волне необходимо оставить либо старый вес вершины, либо заменить его на новый (больший). Поэтому при расчете веса вершины X i за счет волны, подошедшей к ней по дуге (X j, X i), производится вычисление веса V i по формуле V i =max (V i, V j + l ji).
Веса вершин в процессе распространения волны могут меняться неоднократно. При каждом изменении веса V i вершины это увеличение веса необходимо передать вершинам исхода X i, т.е. необходимы специальные средства, отражающие факты получения вершиной нового веса и передачу его другим вершинам. В качестве такого средства используется массив номеров вершин, получивших новый вес (при каждом изменении веса номер вершины включается в этот массив, если его там не было, при передачи веса исключается).
4.2 Словесное описание алгоритма и его работы
1. Все вершины графа получают веса V i=0, номер вершины X н заносится в массив М номеров вершин, изменивших вес. Остальные вершины X i не попадают в массив М.
2. Если массив М пуст, выполняется п. 3, иначе выбирается с исключением из его очередная вершина X i и пересчитываются веса вершин, принадлежащих исходу G (X i) вершины X i:
Если вес V j изменяется, то номер j включается с приведением подобных в М. Снова выполняется п. 2.
3. Если вес 
, то делается вывод, что пути из вершины X н к вершине X k не существует, иначе выполняется процедура выделения дуг, двигаясь в обратном порядке проверяем выполняется ли условие X i – X j = l ij, для входов 
вершины X i, если оно выполняется, то вершина X j и дуга l ij выделяются.
4. После выделения дуг строятся длиннейшие пути, длины которых равны V k.
При построении длиннейших путей рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполнения циклов.
4.3 Структуры данных
Из самой структуры алгоритма очевидно, что для его функционирования необходимы:
1. Массив В-массив дуг-связностей в ячейках с номерами i, j которого будет находиться вес соответствующей дуги l ij.
2. Массив М – массив изменивших свой вес вершин.
3. Массив Е – массив содержащий значения весов и состояний вершин.
4. Массив Р – массив содержащий выделенные дуги.
5. Ряд индексных переменных необходимых для перемещения по массивам В, Е, Р, а также содержащие индекс текущей вершины, и ряд буферных переменных необходимых для текущих арифметических и циклических операций (все индексы должны быть целочисленного типа).
Похожие работы
... 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути. 3) (Y mod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер. 2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР 2.1 Математическое описание задачи Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию. Сортировка используется для ...
... распределения материальных благ и развития промышленного производства (сельского хозяйства, здравоохранения, связи и т. п.). Рис. 8.3. Структура системы управления общественным производством В реализации задачи инновационный менеджмент занимает специфическую и важную роль в установлении критериев и путей развития. 1 – Сбор данных и выделение ошибок. 2 – Анализ последствий ...
... телеги, микропроцессорные системы и т.д. В данном дипломном проекте поставлена задача оптимизировать сборку телеги, а также выявить экономический эффект за счет инноваций технологии и экономии ресурсов. Рассмотрим основные составляющие телеги: - Полка ТМ.201.01.03 – 24 шт. – Лист Б-О-ПН-2,0 ГОСТ 19903-74/12Х18Н10Т ГОСТ 5582-75; - Заглушка ТМ.201.01.09 – ...
... руководителя. Большое внимание следует уделять мотивации управленческого труда. 56. Организационно-распорядительные методы управления (Или административные). С их помощью осуществляются регулирующие функции гос-ва. Основаны на исполнении обязательных предписаний и рекомендаций, позволяют оперативно воздействовать на ход событий в процессе упр-я, ср-во волевого и конкретного воздействия ( ...
0 комментариев