Файл: Л. К. Радченко навигационная картография новосибирск сгугиТ 2017.pdf

50

51
Термин «граф» впервые ввел в 1936 г. венгерский математик Денеш
Кениг. Графами были названы схемы (рис. 11), состоящие из точек и со- единяющие эти точки отрезков прямых или кривых.
Рис. 11. Примеры графов
С графами в обычной жизни мы сталкиваемся постоянно, сами того не замечая. Например, графом является схема линий метрополитена.
Точками на ней представлены станции, а линиями – пути движения по- ездов.
Любого человека интересует происхождение своей семьи. Вопрос создания родословной решается индивидуально, так вот исследуя свою родословную, мы строим так называемое генеалогическое древо. И это древо тоже является графом.
Теория графов способствует решению задач, сформулированных в различных областях знаний: в автоматике, математике, экономики, элек- тронике, физике, химии и др. С помощью графов изображаются схемы до- рог, трубопроводов любого назначения, решаются различные прикладные
ГИС-задачи.
5.2.
Основные понятия теории графов
Схема, состоящая из «изолированных» вершин, называется нулевым графом (рис. 12).

52
Рис. 12. Нулевой граф
Графы, в которых не построены все возможные ребра, называют- ся неполными графами (рис. 13).
Рис. 13. Неполный граф с пятью вершинами
Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки, – ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволи- нейными (рис. 14), длины отрезков и расположение точек произвольны.
Рис. 14. Все три фигуры изображают один и тот же граф
На рис. 15 изображен граф, в котором каждая из всех вершин смежна.
Этот граф является полным графом.

53
Рис. 15. Полный граф
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно:
n(n – 1)/2.
На рис. 15 ребра, превращающие граф в полный граф, изображены прерывистыми линиями, совокупность вершин графа с этими ребрами на- зывается дополнением графа. Вершинами могут служить объекты любой природы: населенные пункты, задвижки трубопроводов, элементы блок- схем алгоритмов и т. д.
Под ребрами могут подразумеваться дороги между двумя соседними городами, трубопроводы от задвижки до следующей задвижки, линии электропередачи от подстанции к потребителю. Любую систему улиц в городе можно представить в виде графа. Здесь вершины выступают в роли перекрестков. Ребро и любая из его двух вершин называются инцидент-
ными. Под степенью вершины подразумевается количество инцидентных ей ребер. Так, степень всех вершин графа, изображенного на рис. 15, равна 4.
Изолированные вершины – это такие вершины, которые не имеют ин- цидентных ребер, т. е. их степень нулевая. Из всего этого следует, что изолированные вершины недостижимы их любых других вершин. Вися- чие вершины – это такие вершины, которые имеют только одно инци- дентное ребро.
Изолированная вершина графа имеет степень 0, а висячая — степень 1.
Маршрут графа – это чередующаяся последовательность вершин и ребер. Эта последовательность начинается и кончается вершиной, в кото- рой каждое ребро инцидентно двум вершинам. В графах можно выделить

54 различные маршруты. Маршрут является замкнутым (циклом), если его начальная и конечная вершины совпадают. Если все ребра различны, то маршрут называется цепью (рис. 16).
Рис. 16. Замкнутый граф
Маршрут называется простой цепью, если все его вершины и ребра различны. Одна вершина достижима из другой, если между ними проло- жен маршрут. Граф считается связным, если каждая его вершина дости- жима из любой другой.
Графы подразделяются по способу «визуализации» связей между оп- ределенными объектами. Связи эти могут быть «направленными», как, например, в генеалогическом древе, или «ненаправленными» (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выде- ляют два основных типа графов: ориентированные (или направленные) и неориентированные.
Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентиро- ванным графом (рис. 17).
Рис. 17. Ориентированный граф

55
Если ребра не имеют ориентации, граф называется неориентирован- ным (рис. 18).
Рис. 18. Неориентированный граф
5.3.
Маршрутизация
Десять-пятнадцать лет назад главным помощником при планировании маршрута был атлас автомобильных дорог. В настоящее время, собираясь в путь, мы используем навигационные приложения, и «умные» алгоритмы сами строят для нас наилучший маршрут. Различные навигационные при- ложения помогают нам планировать поездки, прокладывать кратчайшие пути, выбирать маршруты и транспорт. Выбирать маршрут можно в соот- ветствии с определенными требованиями пользователя:
– кратчайшее расстояние до пункта назначения;
– с учетом категорийности дорог;
– с учетом водных переправ, туннелей, железнодорожных переездов;
– с учетом загруженности трафика;
– с учетом предпочтений пользователя на маршруте.
Главные составляющие маршрутизации – это дорожный граф и алго- ритм, рассчитывающий маршрут.
Маршрутизация по автомобильным дорогам получила соответствую- щее название – автомобильная, она работает по заранее созданному графу дорог. Ее главным недостатком является то, что невозможно проложить маршрут к объекту, рядом с которым нет поблизости дорог. Но в некото- рых научных статьях [28] встречается информация о разработках маршру- тизации, предназначенной для пешеходов или вездеходного и вьючного транспорта. Актуальность создания маршрутизации для этих пользовате-

56 лей очень высока. Решением в данном случае является создание навига- ционной карты, содержащей плотную сеть узлов и ребер, составляющих граф возможных маршрутов, где каждое ребро учитывает объекты и усло- вия местности, через которые они проложены (растительность, рельеф, наличие и качество объектов дорожной сети). Параметры ребер учитыва- ются при построении маршрутов по ним.
5.4.
Дорожный граф
Дорожный граф – это тематический слой, содержащий всю сеть до- рог. Он состоит из множества фрагментов, которые обязательно состыко- ваны между собой. Каждый фрагмент содержит информацию о своем уча- стке дороги: географические координаты, среднюю скорость, с которой автомобили обычно едут на этом участке, и другие параметры. Помимо семантической информации, дорожный граф содержит и топологическую, а именно: способ соединения с соседними участками, направление движе- ния, есть ли на данном участке поворот направо или налево, возможен ли поворот в обратную сторону и т. д.
Дорожный граф навсегда сделать нельзя, так как транспортная систе- ма города постоянно меняется, появляются новые дороги и развязки, ме- няется направление движения. Там, где недавно был поворот, может из- мениться дорожная ситуация, и все это отразится на знаках дорожного движения и на самом движении. Поэтому навигационные приложения вы- нуждены регулярно обновлять данные.
В нашей стране в соответствии с приказом Министерства экономи- ческого развития Российской Федерации от 1 октября 2010 г. № 464 «Об утверждении порядка создания, обновления, использования, хранения и распространения цифровых навигационных карт» к дорожному графу предъявляются следующие требования:
– дорожный граф создается в виде связного полного графа. При соз- дании графа дорог используются топологически связанные ребра (кото- рые должны соответствовать на местности осевым линиям дорог или осевым линиям проезжих частей дорог) и вершины, геометрические и семантические свойства которых описывают расположение проезжих

57 частей улично-дорожной сети (улицы, дороги, внутриквартальные про- езды), их характеристики, элементы организации дорожного движения;
– при формировании дорожного графа его вершины на местности должны соответствовать: точкам пересечения осевых линий, располо- женных на одной по высоте уровне дорог или осевых линий проезжих частей таких дорог; расположенным на дорогах или их проезжих частях долговременным преградам, препятствующим проезду транспортных средств; пересечению линии уреза воды на водоемах и линии маршрута при движении через разводные мосты и паромные переправы. В случае, если дороги или их проезжие части находятся на разных уровнях по вы- соте, вершина дорожного графа, соответствующая их пересечению, не образуется;
– при создании дорожного графа его ребро соответствует осевой ли- нии проезжей части дороги в случаях: если проезжие части дороги раз- делены физическим разделителем (барьер, ограждение, газон, отделен- ные барьером от проезжей части дороги трамвайные пути); если проез- жие части дороги разделены двойной сплошной линией дорожной раз- метки. В указанных случаях в местах, где возможен разворот, ребра, со- ответствующие различным направлениям движения, соединяются до- полнительным ребром дорожного графа с одновременным образованием дополнительных вершин;
– при построении дорожного графа ребрам должны присваиваться следующие атрибуты: направление движения (одностороннее, двусто- роннее, запрет проезда); информация об ограничениях дорожного дви- жения (минимальное и максимальное ограничение скорости движения, ограничение нагрузки на ось, ограничение высоты, ограничение длины, ограничение ширины); уровень расположения дороги (проезжей части дороги) по высоте (обозначается целыми числами, в том числе отрица- тельными, принимая уровень дороги, находящейся на поверхности зем- ли, за 0); ограничение возможности проезда по времени (сезонность, ин- тервал времени суток); классификация дороги в соответствии с Прави- лами классификации автомобильных дорог в Российской Федерации и их отнесение к категориям автомобильных дорог, утвержденными По- становлением Правительства Российской Федерации от 28 сентября

58 2009 г. № 767 «О классификации автомобильных дорог в Российской
Федерации»; назначение автомобильных дорог в соответствии с основ- ными показателями транспортно-эксплуатационных характеристик и по- требительских свойств (съезд, автострада, железнодорожный переезд, мостовые сооружения, автодорожные тоннели); наименование улицы, на которой расположена дорога; альтернативное наименование улицы, на которой расположена дорога (при наличии); материал покрытия дороги
(проезжей части дороги);
– дорожный граф должен содержать информацию о дате и способе получения данных об организации дорожного движения (камерально- полевые изыскания). Отклонение местоположения ребра дорожного графа не должно превышать 15 м от фактического местоположения соответст- вующей осевой линии дороги (проезжей части дороги) на местности.
5.5.
Задача о кратчайшем пути
Задача о кратчайшем пути (shortest path problem) – задача поиска са- мого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь. Задача о кратчайшем пути является одной из важнейших классических задач тео- рии графов.
Значимость данной задачи определяется ее различными практически- ми применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин высту- пают перекрестки, а дороги являются ребрами, которые лежат между ни- ми. Сумма расстояний всех дорог между перекрестками должна быть ми- нимальной, тогда найден самый короткий путь.
Существуют различные постановки задачи о кратчайшем пути.
1. Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начи- нается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).

59 2. Задача о кратчайшем пути между заданной парой вершин. Требует- ся найти кратчайший путь из заданной вершины u в заданную вершину v.
3. Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра.
Таким образом, задача находит практическое применение в большом ко- личестве областей (информатика, экономика, география и др.).
Так как существует множество разных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска крат- чайшего пути на графе:

алгоритм Дейкстры, который находит кратчайший путь от одной из вершин графа до всех остальных.

алгоритм Беллмана – Форда находит кратчайшие пути от одной вершины графа до всех остальных.

алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе;

алгоритм Флойда – Уоршелла находит кратчайшие пути между всеми вершинами ориентированного графа;

алгоритм Джонсона находит кратчайшие пути между всеми пара- ми вершин ориентированного графа;

алгоритм Ли (волновой алгоритм) основан на методе поиска в ши- рину; находит путь между вершинами s и t графа (s не совпадает с t), со- держащий минимальное количество промежуточных вершин (ребер). Ос- новное применение – трассировка электрических соединений на кристал- лах микросхем и на печатных платах;

поиск кратчайшего пути на основе алгоритма Килдала.