ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Инженерно-экономический факультет

Кафедра вычислительной техники и информационных технологий

ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

Зав. кафедрой, профессор, д.т.н.

А. Г. Пимонов « » 2007 г.

Лопатин Артем Алексеевич

РАЗРАБОТКА, АНАЛИЗ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

АЛГОРИТМОВ ПОИСКА И ОПТИМИЗАЦИИ МАРШРУТОВ

ДВИЖЕНИЯ В УЛИЧНО-ДОРОЖНОЙ СЕТИ ГОРОДА

Дипломная работа Научный руководитель, профессор, д.т.н. А. Г. Пимонов Исполнитель, студ. гр. ПИ021 А. А. Лопатин Электронная версия дипломной работы помещена в электронную библиотеку Файл:

Администратор:

Кемерово –

РЕФЕРАТ

Дипломная работа, 35 стр., 24 рис., 18 источников, 1 приложение.

АЛГОРИТМЫ НА ГРАФАХ, ПОИСК ПУТЕЙ, ОПТИМИЗАЦИЯ, БАЗА ДАННЫХ,

ПРОГРАММИРОВАНИЕ, ГЕОИНФОРМАЦИОННАЯ СИСТЕМА.

Объект исследования – алгоритмы поиска путей на графах.

Цель работы – создание геоинформационной системы поиска и оптимизации маршрутов движения в улично-дорожной сети города.

Методы и технологии разработки – анализ алгоритмов поиска на графах, системный анализ улично-дорожной сети города; технология автоматизированных баз данных, визуальное и объектно-ориентированное программирование.

Результаты работы – выполнен обзор существующих программных реализаций геоинформационных систем, проведен анализ алгоритмов поиска на графах и способов представления графов и информационных системах.

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

Область применения – разработанная геоинформационная система может быть использована для поиска и оптимизации маршрутов движения (в том числе и многопунктовых) в улично-дорожной сети города; для поиска допустимых и оптимальных маршрутов передвижения в сети горных выработок в случае возникновения аварийных ситуаций;

для оптимизации маршрутов авиаперелетов, пассажирских и грузовых автоперевозок.

Дальнейшее расширение возможностей геоинформационной системы может быть осуществлено за счет реализации работы с результатами поиска (формирование и экспорт в различные форматы найденных маршрутов движения, расчет затрат на горючесмазочные материалы и техническое обслуживание транспортных средств при постоянных автоперевозках по найденным маршрутам), добавления дополнительных атрибутов дорог и формирования на их основе новых критериев поиска (качество дорожного полотна и количество полос движения; удобство, время и средняя скорость передвижения).

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ

1.1 Основы геоинформатики

1.2 Классификации

1.3 Области применения

1.4 Обзор существующих программных реализаций

1.4.1 ГИС-редактор «City Explorer»

1.4.2 Городская информационная система ДубльГИС

1.4.3 ГИС «Открытый город»

1.4.4 Электронная справочная система города Калуги

1.4.5 Справочник метро «PMetro»

2 АЛГОРИТМЫ НА ГРАФАХ

2.1 Основы теории графов

2.2 Маршруты, пути, циклы, расстояния

2.3 Представление графов в информационных системах

2.4 Поиск на графах, кратчайшие пути

2.4.1 Поиск в глубину

2.4.2 Поиск в ширину

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

2.4.4 Алгоритм Дейкстры поиска кратчайшего пути

2.4.5 Алгоритм обхода препятствий А*

2.5 Генетический алгоритм

2.5.1 Естественный отбор в природе

2.5.2 Понятие и особенности генетического алгоритма

2.5.3 Алгоритм решения задачи коммивояжера

3 ГЕОИНФОРМАЦИОННАЯ СИСТЕМА ПОИСКА И ОПТИМИЗАЦИИ МАРШРУТОВ..

3.1 Среда и средства разработки

3.2 Структура данных

3.3 Программная реализация алгоритмов на графах

3.4 Основные возможности

3.4.1 Начало работы

3.4.2 Создание нового проекта

3.4.3 Работа с картой

3.4.4 Поиск оптимального маршрута движения

3.4.5 Поиск оптимального многопунктового маршрута

3.5 Перспективы развития и использования

3.5.1 Работа с результатами поиска

3.5.2 Дополнительные критерии оптимизации

3.5.3 Различные области использования графов

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А СПИСОК ФАЙЛОВ НА КОМПАКТ-ДИСКЕ

ВВЕДЕНИЕ

Дорожная отрасль является одной из важнейших отраслей экономики любой промышленно развитой страны. Недаром автомобильные дороги называются «кровеносной системой» любого государства. Они играют огромную социально-экономическую роль в жизни современного общества. В Российской Федерации в силу огромной пространственной протяженности территории транспортные издержки существенно больше среднемировых показателей. Автомобильные дороги являются очень капиталоемкими, но в тоже время и очень рентабельными сооружениями. Известно, что каждый рубль, вложенный в автомобильные дороги, в перспективе многократно (в 3–5 раз) возвращается в различных других отраслях экономики за счет снижения транспортных (логистических) издержек, снижения аварийности, повышения подвижности населения [1].

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

Таким образом, основной целью данной работы является создание геоинформационной системы поиска и оптимизации маршрутов движения в улично-дорожной сети города.

Для достижения этой цели были поставлены и решены следующие задачи:

1) выполнить обзор существующих программных реализаций геоинформационных систем;

2) проанализировать алгоритмы поиска на графах и способы представления графов в информационных системах;

3) провести системный анализ улично-дорожной сети города;

4) спроектировать базу данных для хранения информации об основных элементах улично-дорожной сети города;

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

Дипломная работа состоит из введения, трех глав, заключения, списка использованных источников и приложения.

Первая глава работы посвящена общим вопросам геоинформатики и анализу существующих программных реализаций геоинформационных систем.

Во второй главе рассмотрены теоретические основы дипломной работы. Проанализированы алгоритмы поиска на графах и способы представления графов и информационных системах.

Третья глава является описанием спроектированной базы данных и разработанной геоинформационной системы поиска и оптимизации маршрутов движения в уличнодорожной сети города.

1 ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ

Геоинформационная система (ГИС) – это информационная система, предназначенная для сбора, хранения, обработки, отображения и распространения данных, а также получения на их основе новой информации и знаний о пространственнокоординированных объектах и явлениях [3]. Основной особенностью ГИС, отличающей ее от других информационных систем, является то, что все моделируемые в ГИС объекты и явления имеют пространственную привязку, позволяющую анализировать их во взаимосвязи с другими пространственно-определенными объектами. ГИС кардинально отличаются от большинства других информационных систем тем, что вся информация в них очень наглядно представляется в виде электронных карт, позволяя человеку получать новые знания.

Первые ГИС появились в 60-х годах ХХ века в Канаде, США и Швеции. Они имели существенные программные и технические ограничения. В течение следующих 20 лет, вплоть до 80-х годов, проходило становление геоинформатики как науки, отрабатывались методологические подходы к созданию ГИС, создавался математический аппарат, разрабатывались модели данных и алгоритмы их обработки. В 80-х годах начинается стремительное распространение компьютерной техники с одновременным увеличением быстродействия и возможностей. Всё это приводит к переходу геоинформатики на новый уровень [2, 3].

Первоначально термин ГИС расшифровывался как географическая информационная система. Однако сейчас такой термин считается неверным, так как в настоящее время геоинформационные системы решают самые разные задачи в различных отраслях экономики.

Главным отличием электронных карт ГИС от бумажных карт является то, что в ГИС карта не является обычной статической картинкой. Каждый условный знак, изображенный на карте ГИС, соответствует некоторому объекту, который можно проанализировать, например, получить дополнительную (неграфическую) информацию из базы данных (БД). То есть, одной из базовых функций ГИС является получение информации по выбранному на карте объекту. Так, например, в ГИС, выбрав здание на карте города, можно получить детальную информацию о нем: адрес, этажность и пр.

В основе ГИС лежит концепция послойной организации пространственных данных:

однотипные данные на земной поверхности группируются в слои. Совокупность всех слоев образует карту. Деление объектов на слои производится так, чтобы объекты одного слоя были общей природы происхождения (дороги, реки, здания) и имели одинаковую топологическую структуру и размерность (описание объекта точками, линиями или полигонами). Большое количество слоев создавать нежелательно: нет смысла создавать отдельные слои для дорог с различным типом покрытия, лучше сделать один слой с дорогами, и у каждого объекта (дороги), указать тип покрытия. В ГИС выделяют несколько основных слоев, например:

1) Слой рек. На карте города реки обычно представляются в виде многоугольников, на крупномасштабных картах (картах области, страны) – с помощью ломаных.

2) Слой деревьев. Деревья можно представить в ГИС в виде точечных объектов или многоугольников, окаймляющих сплошные зоны лесопарковых насаждений.

3) Слой автомобильных дорог. В зависимости от решаемых задач автомобильные дороги могут быть представлены в виде осевых линий, либо в виде многоугольников, точно описывающих проезжую часть. В некоторых случаях имеет смысл иметь два отдельных слоя для осевых линий дорог и для проезжих частей.

4) Слой зданий. Здания представляются в виде многоугольников, описывающих контур здания на уровне земли. В атрибутах зданий обычно указывают тип здания (жилое, промышленное, коммерческое), адрес, высоту, количество этажей и пр.

Деление данных на слои позволяет работать в ГИС только с теми данными, которые необходимы для решения поставленных задач. В самом простом случае можно «выключить» те слои, которые нам не нужны, и увидеть на карте оставшиеся [1]. Таким образом, изображение на карте ГИС всегда соответствует некоторому набору данных, хранящемуся в БД. При этом всегда можно перейти от условного знака на экране к объекту в базе данных и получить требуемую информацию. А также и наоборот, найдя по некоторому критерию объект в БД, можно посмотреть его расположение на карте.

В настоящее время геоинформационными системами называют различные информационные системы, решающие широкий круг задач. В связи с этим существует несколько классификаций, позволяющих более полно понять сущность ГИС [3].

1) Виды ГИС по пространственному охвату:

• глобальные (планетарные);

• субконтинентальные;

• национальные (государственные);

• региональные (областные, краевые, республиканские);

• субрегиональные (районы внутри регионов);

• локальные (городские);

• ультралокальные (отдельные ограниченные территории).

2) Виды ГИС по используемой модели данных:

• векторные ГИС работают с различными моделями данных, а также иногда с триангуляционными моделями поверхностей;

• растровые ГИС позволяют работать только с растровыми моделями данных;

• гибридные совмещают в себе возможности векторных и растровых ГИС.

3) Виды ГИС по компьютерной платформе, на базе которой они функционируют:

• Настольные ГИС. К этой категории относятся большинство известных ГИС.

Как правило, используемые в них данные сохраняются в локальных файлах.

• Клиент-серверные ГИС. В этих системах пространственные данные хранятся полностью в базе данных сервера. Этот сервер обычно является высокоуровневой надстройкой над некоторой промышленной системой управления базами данных (СУБД типа Microsoft SQL Server, Oracle, DB2, Sybase и др.).

• ГИС для интернета. Такие системы бывают двух видов: а) самостоятельные программы, обеспечивающее полные функции HTTP-сервера, либо б) наборы программных компонент (обычно ActiveX-объектов), которые могут быть интегрированы в существующий Html-код и произвольным образом настроены. Первый подход позволяет очень быстро выполнить публикацию карт в интернете, а второй подход более гибок.

Следует заметить, что термином ГИС называются очень многие и разные информационные системы. Этим словом описывают как собственно прикладные программы для различных отраслей, так и сами инструментальные ГИС, на основе которых создаются конкретные отраслевые системы.

ГИС применяются в различных областях деятельности человека и помогают решать разнообразные задачи [1, 3]:

• управление (федеральное, региональное, муниципальное, корпоративное);

• землепользование (земельные кадастры, инвентаризация земельных участков, межевание земель);

• управление недвижимостью (кадастр недвижимости);

• градостроительство (генеральные планы развития, дежурные планы, планирование развития);

• архитектура (проектирование генеральных планов, ландшафтное проектирование);

• бизнес (оценка инвестиций и планирование бизнеса);

• инженерные сети (управление и эксплуатация городских, поселковых и корпоративных инженерных сетей: электрических, водопроводных, тепловых, • инженерно-геодезические изыскания (ввод и обработка данных геодезических изысканий, уравнивание геодезических сетей);

• инженерно-геологические изыскания (ввод и обработка данных по геологическим колонкам);

• геология (моделирование геологических пластов; обработка данных бурения, • картография (составление географических и топографических карт);

• проектирование и строительство (проектирование автомобильных и железных дорог, генеральных планов, электрических и трубопроводных сетей);

• экстренные службы (диспетчеризация выездов милиции, пожарных, скорой медицинской помощи, службы спасения);

• ГИБДД (управление инженерным обустройством автомобильных дорог:

светофорами, знаками и др.; диспетчеризация выездов);

• транспорт (управление и эксплуатация автомобильных и железных дорог;

управление речными, морскими и воздушными перевозками);

• логистика (планирование и управление транспортными перевозками);

• оборона (планирование войсковых операций, тыловое обеспечение);

• чрезвычайные ситуации (анализ и предсказание чрезвычайных ситуаций, планирование и осуществление мероприятий по ликвидации последствий);

• экология (оценка и прогнозирование воздействия на окружающую среду);

• метеорология (предсказание погоды, управление сетью метеорологических • недропользование (управление месторождениями полезных ископаемых);

• природопользование (управление природными ресурсами);

• нефтегазовая отрасль (управление нефтегазодобычей, управление промысловыми площадками, управление магистральными трубопроводами);

• демография и статистика (демографический и статистический анализ);

• навигация (навигация на местности и выбор маршрутов движения).

1.4 Обзор существующих программных реализаций City Explorer представляет собой профессиональную полнофункциональную ГИС для создания, редактирования и анализа цифровых карт. Система включает в себя редактор векторной графики, СУБД, редактор условных знаков (для точек, линий и полигонов).

Также среди ее стандартных возможностей – полный набор функций для редактирования карт и нанесения объектов, различные виды поиска, маршрутизатор, обращение к внешним БД, встроенный язык VBA, возможность подключения растровых данных и разработки своих модулей расширения на основе СОМ технологий [4].

Возможности редактирования:

• определение прав отдельных пользователей;

• создание собственных слоев картографических данных;

• редактирование метаданных;

• редактирование объектов данных;

• создание расширений функциональности системы и дополнительных модулей.

City Explorer является платным программным обеспечением (ПО), стоимость одной лицензии – 16 800 рублей.

1.4.2 Городская информационная система ДубльГИС Информационная система ДубльГИС – современная замена бумажным картам и справочным службам. Все версии ДубльГИС выходят ежемесячно и распространяются бесплатно. Электронные карты городов ДубльГИС создаются профессиональной картографической службой по актуальным спутниковым снимкам (данные дистанционного зондирования спутников Iconos и Quickbird). Для уточнения карты проводится объезд территории города [5] (рис. 1.1).

Возможности ДубльГИС позволяют:

• найти на карте любой из объектов: дом по адресу, улицу, жилой массив, район, железнодорожную станцию, станцию • получить информацию о находящихся в • измерить расстояние между объектами или оценить длину определенного • распечатать фрагменты карты вместе с информацией о выбранных зданиях;

• делать собственные пометки на плане Раздел «Транспорт» в справочниках ДубльГИС включает информацию по коммерческим и мунициРис. 1.2 – Схема маршрута пальным маршрутам наземного транспорта (автобусы, троллейбусы, трамваи, маршрутные такси) (рис. 1.2).

Возможности:

• просмотр схемы маршрутов на карте города;

• поиск остановки городского транспорта на карте и просмотр соответствующих номеров маршрутов;

• поиск вариантов проезда между двумя выбранными остановками с учетом пересадок и пеших переходов между близкорасположенными остановками.

Открытый город – электронная схема нескольких городов России, объединенная с телефонным справочником организаций. Информация в справочнике, а также схематическая информация обновляется ежемесячно. Программа распространяется бесплатно [6].

Возможности программы «Открытый город»

совпадают с возможностями рассмотренной ранее программы ДубльГИС. Существуют лишь незначительные различия в интерфейсе. В ГИС «Открытый город» заложены карты следующих городов: Кемерово (рис. 1.3), Новокузнецк, Прокопьевск, Междуреченск, Осинники, Мыски, Новосибирск, Красноярск, Абакан, Канск, Барнаул, Томск, Омск, Комсомольскна-Амуре, Усть-Каменогорск.

1.4.4 Электронная справочная система города Калуги Эта система имеет много общего с рассмотренными выше программами: ДубльГИС и «Открытый город», однако она значительно превосходит их по предоставляемым возможностям. К основным положительным моментам электронной справочной системы города Калуги можно отнести:

• расположение объектов на схеме по • поиск домов по адресу, предприятий – • возможность выбора объекта на карте и получения информации о нем (рис. 1.4);

• вычисление расстояний и площадей • определение кратчайших транспортных возможности позволяют осуществлять с ее помощью следующие мероприятия:

• контроль за состоянием зданий и • контроль за транспортной системой города;

• мониторинг социально-экономической обстановки в городе в динамическом • анализ чрезвычайных ситуаций и катастроф;

• экологический мониторинг территории города.

PMetro – это справочник метро Москвы и других городов. Он отображает схему метро города (а для некоторых городов и схему электропоездов) и позволяет найти кратчайшие пути между станциями [8] (рис. 1.6).

Отличительные особенности программы:

• наличие схемы метро более • возможность масштабирования, сглаживания изображения;

обязательных и нежелательных транспорте, проходящем рядом со наземного транспорта (автобусов, с пересадками между различными поддержки и транслитерации;

• доступность всех данных для Рис. 1.7 – 3D-схема Московского • наличие 3D-схемы (рис. 1.7).

2 АЛГОРИТМЫ НА ГРАФАХ

Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Термин «граф» неоднозначен. Это легко заметить, сравнивая приводимые в разных книгах определения. Однако во всех этих определениях есть кое-что общее. В любом случае граф состоит из двух множеств – множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет [9].

Графом G мы будем называть пару (V(G), E(G)), где V(G) – непустое конечное множество элементов, называемых вершинами, а E(G) – конечное множество неупорядоченных пар элементов из V(G), называемых ребрами [10]. Мы будем рассматривать только конечные графы, то есть такие, у которых оба множества конечны. Вершины и ребра графа будем называть его элементами. Множество вершин графа G будем обозначать через VG, множество ребер – EG, число вершин – n(G), число ребер – m(G).

Ориентированным графом (орграфом) называется пара G=(V, E), где V – конечное множество, E – множество упорядоченных пар различных элементов из V [9]. В дальнейшем термин «граф» будем употреблять в смысле «обыкновенный граф», а рассматривая другие типы графов, будем специально это оговаривать.

Примеры графов легко найти в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы – в этих случаях графы возникают естественно и видны «невооруженным глазом».

Немало поводов для появления графов и в Рис. 2.2 – Представления куба математике. Наиболее очевидный пример – любой в виде графа многогранник в трехмерном пространстве. Вершины и ребра многогранника можно рассматривать как вершины и ребра графа. При этом мы не обращаем внимание на расположение элементов многогранника в пространстве, оставляя лишь информацию о том, какие вершины соединены ребрами [9] (рис. 2.2).

Если в графе имеется ребро e=(a,b), то говорят, что вершины a и b смежны в этом графе, ребро e инцидентно каждой из вершин a, b, а каждая из них инцидентна этому ребру. Множество всех вершин графа, смежных с данной вершиной a, называется окрестностью этой вершины и обозначается через V(a). Число вершин, смежных с вершиной a, называется степенью вершины a и обозначается через deg(a). Вершину степени 0 называют изолированной. Граф называют регулярным степени d, если степень каждой его вершины равна d.

Маршрут в графе – это последовательность вершин x1, x2… xn, такая, что для каждого i=1, 2… n1 вершины xi и xi+1 соединены ребром. Эти n1 ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число n1 называют длиной маршрута. Говорят, что, если маршрут соединяет вершины xi и xn, то они называются соответственно началом и концом маршрута, вершины x2…xn называются промежуточными.

Маршрут называется замкнутым, если x1=xn.

Путь – это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.

Цикл – это замкнутый путь. Цикл x1, x2… xn-1, x1 называется простым, если все вершины x1, x2… xn-1 попарно различны [9].

Установим некоторые простые свойства маршрутов.

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

2) Если в графе степень каждой вершины не меньше 2, то в нем есть цикл. Доказательство этих свойств можно найти в [9].

Расстоянием между двумя вершинами графа называется наименьшая длина пути, соединяющего эти вершины. Расстояние между вершинами a и b обозначается через d(a,b).

Если в графе нет пути, соединяющего a и b, то расстояние между ними считается бесконечным. Функция d(a,b) обладает следующими свойствами:

1) d(a,b)0, причем d(a,b)=0 тогда и только тогда, когда a=b;

2) d(a,b)=d(b,a);

3) d(a,b)+d(b,c)d(a,c) (неравенство треугольника).

Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через ecc(a). Таким образом, ecc(a)=max d(a,x). Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим эксцентриситетом – периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа и обозначается rad(G), а величина наибольшего – диаметром и обозначается diam(G). Наименьший диаметр имеет полный граф (граф, все вершины которого попарно смежны) – его диаметр равен 1 [9].

Для ориентированного графа можно определить два типа маршрутов:

1) неориентированный маршрут – это чередующаяся последовательность x1, e1, x2, e2… ek-1, xk вершин и ребер графа, такая, что для каждого i=1, 2… k1 выполняется одно из двух: ei=(xi, xi+1) или ei=(xi+1, xi);

2) маршрут называется ориентированным (или ормаршрутом), если ei=(xi, xi+1) для каждого i.

Таким образом, при движении вдоль неориентированного маршрута в орграфе ребра могут проходиться как в направлении ориентации, так и в обратном направлении, а при движении вдоль ормаршрута (или просто маршрута) – только в направлении ориентации.

Это различие очевидным образом распространяется на пути и циклы, так что в орграфе можно рассматривать пути и орпути, циклы и орциклы. Определимся, что маршрут соединяет вершины xi и xk, а ормаршрут ведет из xi в xk.

2.3 Представление графов в информационных системах При создании различных информационных систем, связанных с атласами автомобильных дорог, схемами маршрутов передвижения, техническими схемами устройств, организационными схемами управления, с решением задач сетевого планирования неизбежно приходится иметь дело с графами. Графы позволяют решить множество задач: найти оптимальный маршрут на карте дорог; рассчитать максимальное время выполнения проекта (критический путь); определить, сколько элементов должно выйти из строя, чтобы отказал весь механизм и т. д.

Граф обычно изображают как множество точек на плоскости (вершин графа), соединенных линиями (ребрами графа). Очевидно, что это представление не подходит для решения задач с помощью компьютера. Выбор соответствующей структуры данных для представления графов оказывает принципиальное влияние на эффективность алгоритмов [11]. Проанализируем несколько способов представления графов. Для определенности условимся, что рассматривать будем только неориентированные графы (для орграфов рассуждения будут аналогичными).

суждения будут аналогичными).

Еще раз вспомним несколько определений из основ теории графов. Граф есть некоторое множество вершин и некоторое множество ребер, соединяющих пары различных вершин [12]. Две вершины называются смежными, если есть ребро, соединяющее их. Такое ребро называется инцидентным данным вершинам.

Для примера возьмем конкретный граф. Пусть он состоит из 5 вершин (пронумеруем их от 1 до 5), Рис. 2.3 – Представление связанных 7 ребрами (обозначим их как «р1» «р7») графа на плоскости (рис. 2.3).

представления этого графа в информационных способом представления служит матрица инциденций. Это матрица A с n строками, соответствующими ребрам [11]. Ячейка матрицы содержит 1, если вершина и ребро матрицы инцидентны (рис. 2.4). Матрица инциденций является одним из самых неудачных способов представления графа в информационной системе. Для хранения такой матрицы (размерность n m) необходимо достаточно много памяти, причем большой объем занят нулями.

И ответы на простые вопросы – «Смежны ли вершины x и y?», «Какие вершины смежны с вершиной х?» – требуют, в худшем случае, перебора ется матрица смежности, определяемая как матрица B=[bij] размера n n, где bij=1, если существует ребро, идущее из вершины i в вершину j [11] (рис. 2.5). Пре- Рис. 2.5 – Представление графа имущество матрицы смежности – это то, что за один в виде матрицы смежности шаг можно ответить на вопрос «Существует ли ребро, связывающее вершины x и y?». Недостаток в том, что независимо от числа ребер объем занимаемой памяти пропорционален n2. Если в графе нет петель (вершин, соединенных сами с собой), то на главной диагонали всегда будут нули. Матрица смежности является симметричной относительно главной диагонали [12].

Рис. 2.6 – Представление графа соответствующих его ребрам Лучшим решением во многих случаях оказывается структура данных – список инцидентностей [11] – или список смежных вершин [12] (рис. 2.7). Для неориентированного графа каждого ребра x-y вершина x содержится во множестве, соответствующем вершине y и наоборот.

поисковые задачи, на которые при использовании предыдущих требовалось бы гораздо большее количество шагов. Этот способ представления является одним из экономичных в отношении использования памяти.

У каждого из рассмотренных способов представления графов есть свои недостатки и свои преимущества. Использование того или иного способа зависит от назначения и задач проектируемой информационной системы.

Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра – зависит от конкретной задачи, для решения которой производится обход. В любом случае, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую [9].

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин, такой, что каждая вершина просматривается в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Метод поиска хорош, если он позволяет алгоритму решения интересующей нас задачи легко использовать этот метод и каждое ребро графа анализируется не более одного раза (или количество таких исследований ограничено сверху) [11].

Поиск в глубину – это наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода – идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями: «бэктрекинг», «поиск с возвращением» [9].

Обход начинается с посещения заданной стартовой вершины a, которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине a ребро (a, y) и посещается вершина y. Она становится открытой и активной. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине x, уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер (x, y), это ребро исследуется. Если вершина y новая, то она посещается и превращается в открытую.

При поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина [9].

Поиск в ширину – это классический метод решения задачи нахождения кратчайшего пути между двумя конкретными вершинами графа. Кратчайший путь – это такой путь, соединяющий вершины графа, который обладает тем свойством, что никакой другой путь, соединяющий эти вершины, не содержит меньшее число ребер. Поиск в глубину мало пригоден для решения этой задачи, поскольку предлагаемый им порядок прохождения графа не имеет отношения к поиску кратчайших путей, а поиск в ширину предназначен как раз для достижения этой цели [12].

Итак, рассмотрим метод поиска в ширину. Отметим, что в рассмотренном в предыдущем разделе методе поиска в глубину чем позднее будет посещена вершина, тем раньше она будет использована – точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью [11].

Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины a. Иначе говоря, сначала посещается сама вершина a, затем все вершины, смежные с a, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от a на расстоянии 2, и далее по удаленности [9].

Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной a. Вначале все вершины помечаются как новые. Первой посещается вершина a, она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины x. Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину x с новой вершиной y, то вершина y посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.

Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь – когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале [9].

Оба метода поиска в графе – в глубину и в ширину могут быть использованы для нахождения пути между фиксированными вершинами a и b. Достаточно начать поиск в графе с вершины a и вести его до момента посещения вершины b. Преимуществом поиска в глубину является тот факт, что в момент посещения вершины b стек содержит последовательность вершин, определяющую путь из a в b. Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является смежной с предыдущей. Однако недостатком поиска в глубину является то, что полученный таким образом путь в общем случае не будет кратчайшим путем из a в b. От этого недостатка свободен метод нахождения пути, основанный на поиске в ширину [11].

В этом и 3 последующих разделах будем рассматривать ориентированные графы G=(V,E), дугам которых приписаны веса. Это значит, что каждой дуге (u,v) поставлено в соответствие некоторое вещественное число a(u,v), называемое весом данной дуги. Полагаем a(u,v)=, если дуга (u,v) не существует.

Под длиной пути будем понимать сумму весов дуг, из которых состоит путь. Длину кратчайшего пути будем обозначать d(s,t) и называть расстоянием от s до t. Если не существует ни одного пути из s в t, то полагаем d(s,t)=.

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

Зная расстояние между парой вершин, можно легко определить кратчайший путь.

Так как для двух произвольных вершин s и t (st) существует такая вершина v, что d(s,t)=d(s,v)+d(v,t). Этим свойством обладает и предпоследняя вершина в кратчайшем пути от s к t. Следовательно, определяя таким образом предпоследнюю вершину, можно пройти от конца кратчайшего пути к его началу [11].

Большинство известных алгоритмов нахождения расстояния между двумя вершинами s и t можно описать следующей последовательностью действий.

1) При заданной матрице весов дуг A[u,v], вычисляем некоторые верхние ограничения D[v] на расстояния от s до всех вершин v.