Программное средство нахождения кратчайших путей в графе

Размещено на http://www.allbest.ru/

ЗАДАНИЕ на курсовое проектирование

Слушателю Политыко Марии Леонидовне

1. Тема проекта: Программное средство нахождения кратчайших путей в графе.

2. Срок сдачи законченного проекта «13»июня 2014 г.

3. Исходные данные по проекту: MS Visual Studio 2010.

4. Состав проекта:

а) пояснительная записка: Введение. Постановка задачи. 1. Системы транспортной логистики. 2. Построение модели. 3. Реализация модели. Заключение.

б) графическая часть проекта (презентация 12 слайдов)

5. Календарный график работы на весь период проектирования:

04.02.2014-26.02.2014 - постановка задачи и анализ предметной области;

27.02.2014-27.03.2014 - построение модели;

28.03.2014-13.06.2014 - реализация модели;

Руководитель проекта Н.И. Байкова

Дата выдачи задания 31 01 2014 г.

Задание принял к исполнению: 31.01.2014 г.

Подпись слушателя



АННОТАЦИЯ

К курсовому проекту Иванова Сергея Дмитриевича, слушателя группы 15ПО12-05з специальности 1-40 01 73 «Программное обеспечение информационных систем» на тему «Программное средство нахождения кратчайших путей в графе»

Ключевые слова: транспортная задача, алгоритм дейкстры, задача коммивояжёра

Предметной областью курсового проектирования является транспортная логистика.

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

При выполнении курсового проектирования были использованы среда визуального программирования MS Visual Studio 2008.

Пояснительная записка к курсовому проекту включает три главы и заключение. Курсовая работа содержит 68 страниц, в том числе 7 приложений.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ПОСТАНОВКА ЗАДАЧИ

1. СИСТЕМЫ ТРАНСПОРТНОЙ ЛОГИСТИКИ

1.1 Логистика

1.2 Транспортная логистика

1.3 Подходы к решению задачи

1.4 Задача коммивояжёра

1.5 NP-сложные задачи

1.6 Транспортная задача

1.7 Постановка задачи

1.8 История поиска методов решения

1.9 Методы решения

2. ПОСТРОЕНИЕ МОДЕЛИ

2.1 Основные понятие и ограничения

2.2 Внутреннее представление данных

2.3 Матрица смежности

2.4 Матрица инцидентности

2.5 Списки смежных вершин через списки

2.6 Списки смежных вершин через матрицы

2.7 Таблица рёбер

2.8 Модифицированная структура данных

2.9 Алгоритмы поиска маршрутов в графе

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

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

2.12 Алгоритм Форда-Фалкерсона

2.13 Алгоритм Прима

2.14 Алгоритм Дейкстры

2.15 Алгоритм Беллмана-Форда

Выводы

3. РЕАЛИЗАЦИЯ МОДЕЛИ

3.1 Выбор среды разработки

3.2 Визуализация транспортной сети

3.3 Редактирование транспортной сети

3.3.1 Добавление элементов

3.3.2 Удаление элементов

3.3.3 Редактирование элементов

3.3.4 Загрузка и сохранение транспортной сети

3.4 Задание условий поиска

3.4.1 Поиск маршрутов

3.4.2 Поиск в глубину (рекурсивная версия)

3.4.3 Поиск в глубину (нерекурсивная версия)

3.4.4 Поиск в ширину (однопоточная версия)

3.4.5 Поиск в ширину (многопоточная версия)

3.5 Пример работы алгоритма

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ



ВВЕДЕНИЕ

В настоящее время задачи транспортной логистики представляют несомненный интерес, как с точки зрения практического программирования, так и с точки зрения теоретической.

Это связано с несколькими причинами

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

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

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

ПОСТАНОВКА ЗАДАЧИ

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

1. Разработать редактор связанной системы графов позволяющий:

1.1 Осуществлять работу с графами:

1.1.1 Создавать, редактировать, удалять

1.1.2 Выгружать на внешний носитель, загружать с внешнего носителя

1.1.3 Выделять цветом

1.1.4 Давать название

1.1.5 Давать описание

1.1.6 Временно скрывать

1.1.7 Временно блокировать

1.2 Осуществлять работу с вершинами графа:

1.2.1 Создавать, редактировать, удалять

1.2.2 Выделять цветом

1.2.3 Давать название

1.2.4 Давать описание

1.2.5 Временно скрывать

1.2.6 Временно блокировать

1.3 Осуществлять работу с рёбрами графа:

1.3.1 Создавать, редактировать, удалять

1.3.2 Выделять цветом

1.3.3. Давать название

1.3.4 Давать описание

1.3.5 Временно скрывать

1.3.6 Временно блокировать

1.3.7 Задавать вес

2. Разработать приложение, позволяющее осуществлять поиск кратчайшего пути между заданной парой вершин согласно следующим ограничениям:

2.1 Количество пересадок (переходов от одного графа к другому) ограничено.

2.2 Отдельные элементы транспортной сети могут быть заблокированы:

2.2.1 Блокировка на уровне вершины.

2.2.2 Блокировка на уровне ребра.

2.2.3 Блокировка на уровне графа.

2.3 Приоритет транспорта определённого вида.



1. СИСТЕМЫ ТРАНСПОРТНОЙ ЛОГИСТИКИ

1.1 Логистика

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

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

Понятие логистики включает в себя множество поддисциплин: закупочная, транспортная, складская, производственная, информационная логистика и другие.

В рамках данного курсового проекта будет рассматриваться транспортная логистика.

1.2 Транспортная логистика

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

Оптимальным считается маршрут, по которому возможно доставить логистический объект, в кратчайшие сроки (или предусмотренные сроки) с минимальными затратами, а также с минимальным вредом для объекта доставки.

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

Перечислим основные задачи, которые стоят перед транспортной логистикой:

1. Выбор типа транспортного средства

2. Выбор вида транспортного средства

3. Совместное планирование транспортных процессов со складскими и производственными операциями

4. Совместное планирование транспортных процессов на различных видах транспорта

5. Обеспечение технологического единства транспортно-складского процесса

6. Определение рациональных маршрутов поставки

Все они (кроме подзадач связанных со складскими операциями) будут затронуты в данном исследовании.

1.3 Подходы к решению задачи

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

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

Характерная особенность исследования операций -- системный подход к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи. Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на практике такое решение найти невозможно по таким причинам:

1. отсутствие методов, дающих возможность найти глобально оптимальное решение задачи

2. ограниченность существующих ресурсов (к примеру, ограниченность машинного времени ЭВМ), что делает невозможным реализацию точных методов оптимизации.

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

1.4 Задача коммивояжёра

Одной из самых известных задач транспортной логистики является задача коммивояжёра.

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

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

Общая постановка задачи, впрочем, как и большинство её частных случаев, относится к классу NP-сложных задач.

Перечислим основные методы решения этой задачи:

· полный лексический перебор

· случайный перебор

· жадные алгоритмы

o метод ближайшего соседа

o метод включения ближайшего города

o метод самого дешёвого включения

· метод минимального остовного дерева

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

Существует также постановки, в которых задача коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает X. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

1.5 NP-сложные задачи

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

Многие задачи на графах относят к классу NP-полных задач.

1.6 Транспортная задача

Транспортная задача (Задача Монжа-Канторовича) -- задача об оптимальном плане перевозок продукта из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной.

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

1.7 Постановка задачи

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

1.8 История поиска методов решения

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется Транспортной задачей Монжа-Канторовича.

1.9 Методы решения

Классическую транспортную задачу можно решить симплекс-методом, но есть и другие подходы.

Например, сначала ищется опорный план при помощи одного из ниже перечисленных методов:

· «северо-западного угла»,

· «наименьшего элемента»,

· двойного предпочтения,

· аппроксимацией Фогеля

А уже затем при помощи теории графов ищется оптимальный путь.

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

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана-Форда. При возврате потока стоимость считается отрицательной.

Алгоритм mincost maxflow можно запускать и сразу -- без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма mincost maxflow происходит не более чем за O(v²e²) операций (e -- количество рёбер, v -- количество вершин.) При случайно подобранных данных обычно требуется гораздо меньше -- порядка O(ve) операций.

Но, подобные постановки транспортной задачи и, соответственно, методы их решения не лучшим образом в явном виде подходят для проблематики, рассматриваемой в рамках курсового проекта, поскольку в них:

1. Не рассматривается возможность наличия нескольких транспортных сетей.

2. Не формализуются затраты на пересадки между транспортными сетями.

3. На оптимальность маршрута влияет не только стоимость перевозки, но и количество перевозимого груза.

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

Всё это приводит к идее поиска решения задачи не в рамках линейного программирования, а в области теории графов.



2. ПОСТРОЕНИЕ МОДЕЛИ

2.1 Основные понятие и ограничения

В математической теории графов и информатике граф -- это совокупность объектов со связями между ними.

Объекты представляются как вершины, или узлы графа, а связи -- как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах (1).

Граф или неориентированный граф G -- это упорядоченная пара G = (V,E) для которой выполнены следующие условия:

· V это множество вершин или узлов,

· E это множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых рёбрами.

Будем считать, что в рамках решаемой задачи будут рассматриваться только неориентированные графы, т.е. если между двумя вершинами (A и B) существует ребро, то путь от вершины A к вершине B будет иметь такую же стоимость что и путь от вершины B к вершине A. Это ограничение не является жёстким и может быть легко обойдено на уровне алгоритмов работы с графом.

Граф не должен содержать кратных рёбер. Будем считать, что пару вершин всегда связывает только единственное ребро. Это ограничение также не является жёстким.

Граф не должен содержать петель, т.к. петля не имеет смысла с точки зрения транспортной сети.

Граф не должен содержать изолированных вершин, т.к из вершины всегда должно выходить хотя бы одно ребро.

Граф не обязательно должен быть связным, т.к. поиск может осуществляться только внутри обособленной области связности.

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

Отрицательные числа не будут использоваться по тому, что отрицательная стоимость в рамках транспортной задачи не имеет смысла.

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

Рисунок 1.1 - Пример случая ребра нулевой длины

2.2 Внутреннее представление данных

Проведём анализ способов внутреннего представления графов (13) (14):

2.3 Матрица смежности

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

Несомненным плюсом этого способа представления является возможность быстро отвечать на вопросы вида «А принадлежит ли ребро (i,j) графу G?». Ещё одним плюсом является возможность быстрого обновления графа. в случае вставки и удаления рёбер.

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

2.4 Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:

· 1 в случае, если связь «выходит» из вершины,

· -1, если связь «входит» в вершину,

· 0 во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине).

Данный способ является самым ёмким и неудобным для хранения, но облегчает нахождение циклов в графе.



2.5 Списки смежных вершин через списки

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

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

2.6 Списки смежных вершин через матрицы

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

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

2.7 Таблица рёбер

Еще более простой структурой данных будет массив или связанный список ребер. Работая с ней, сложнее отвечать на такие вопросы, как: «Какие вершины являются соседними для x?» -- но она прекрасно подходит для определенных простых процедур, таких, как алгоритм Крускала остовного дерева минимального веса.

2.8 Модифицированная структура данных

Данная структура строится на основе типа данных, который используется в таких классических алгоритмах работы с графами как:

· поиск в ширину;

· поиск в глубину;

· алгоритм Прима;

· алгоритм Дейкстры;

· алгоритм Форда-Фалкерсона;

· алгоритм Беллмана-Форда;

Рассмотрим структуру данных и связанных с ними методов, которые будут использоваться для внутреннего представления транспортной сети. (Рис. 1.2)

Класс Transport Network представляет собой верхний уровень транспортной сети и хранит в себе следующий набор полей:

· aGraph -- хранит в себе массив графов, входящих в транспортную сеть;

· aVertex -- хранит в себе массив вершин, входящих в транспортную сеть;

· aEdge -- хранит в себе массив рёбер, входящих в транспортную сеть;

Рисунок 1.2 - Диаграмма связей классов представляющих транспортную сеть

Рисунок 1.3 Класс транспортной сети



· Width -- ширина транспортной сети в пикселях, т.е. ширина изображения необходимая для того, что бы транспортная сеть могла на нём поместиться;

· Height -- высота транспортной сети в пикселях, т.е. высота изображения необходимая для того, что бы транспортная сеть могла на нём поместиться;

· pb -- ссылка на объект PictureBox на котором осуществляется отрисовка транспортной сети;

· dc -- ссылка на объект Graphics посредством которого осуществляется отрисовка транспортной сети;

· textFontNormal -- шрифт для отрисовки нормального текста;

· textFontBold -- шрифт для отрисовки полужирного текста, при помощи которого выделяются объекты, являющиеся активными в настоящий момент;

· dSize -- размер квадратика, которые представляет собой визуальное отображение вершины транспортной сети, за этот квадратик узлы транспортной сети могут перемещаться, на этом же квадратике отображается название вершины;

· rSize -- размер кружочка, который представляет собой визуальное отображение ребра транспортной сети, используя этот кружочек пользователь может выбирать рёбра транспортной сети, на этом же кружочке отображается вес ребра;

Рассмотрим список методов для работы с вышеуказанным набором полей:

· метод AddGraph() добавляет новый граф в транспортную сеть;

· метод AddVertex(int iGraph, int X, int Y) добавляет новую вершину в заданный граф транспортной сети, при этом вершина сразу получает координаты своего расположения;

· метод AddEdge(int srcVertexId, int destVertexId) добавляет новое ребро, соединяющее заданную пару вершин транспортной сети;

· метод GetVertexId(int x, int y, bool showInvisible, bool showDeleted) осуществляет поиск номера вершины расположенной в заданных координатах (в методе предусмотрено два флага, которые контролируют, будет ли осуществляться поиск среди невидимых и помеченных на удаление вершин);

· метод GetEdgeId(int x, int y, bool showInvisible, bool showDeleted) осуществляет поиск номера ребра расположенного в заданных координатах (в методе предусмотрено два флага, которые контролируют, будет ли осуществляться поиск среди невидимых и помеченных на удаление рёбер);

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

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

· метод DropEdge() удаляет ребро из транспортной сети;

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

· метод PackArrays() осуществляет упаковку массивов, в которых хранятся графы, вершины и рёбра (вызывается автоматически при выходе из программы или по требованию пользователя);

· метод AutoSize() осуществляет подбор размера изображения для отображения транспортной сети (размер изображения может быть как увеличен так и уменьшен);

· метод Draw(bool showInvisible, bool showDeleted) осуществляет прорисовку транспортной сети на заданное изображение (в методе предусмотрено два флага, которые контролируют, будут ли прорисованы элементы транспортной сети помеченные как невидимые и как помеченные на удаление).

Класс Element является базовым для классов Graph, Vertex, Edge и содержит в себе общие характеристики.

Рассмотрим список полей:

· Title -- название абстрактного объекта;

· Description -- описание абстрактного объекта;

· Color -- цвет абстрактного объекта;

· Visible -- признак того, является ли абстрактный объект видимым, это свойство необходимо для того, чтобы можно было временно отключать отображение не нужных в данный момент элементов транспортной сети;

· Enabled -- признак того, является ли абстрактный объект доступным, это свойство необходимо для того, чтобы можно было временно исключать из расчётов отдельные части транспортной сети;

· Deleted -- признак того, был ли абстрактный объект помечен для удаления;

· Selected -- признак того, абстрактный объект является текущим и пользователь ведёт с ним в настоящий момент работу.

Перейдём к рассмотрению класса Graph, который содержит в себе описание графа, представляющего собой часть транспортной сети.

· tn -- ссылка на транспортную сеть в которую входит граф, необходима для доступа к другим объектам входящим в транспортную сеть;

· iVertex -- массив, содержащий номера вершин, входящих в граф.

Рассмотрим список методов:

· конструктор Graph(TransportNetwork tn) осуществляет инициализацию графа, в качестве параметра передаётся ссылка на транспортную сеть, в которую входит граф;

· деструктор ~Graph() осуществляет удаление графа.

Перейдём к рассмотрению класса Vertex, который содержит в себе описание вершин, входящих в граф. Рассмотрим список полей:

· tn -- ссылка на транспортную сеть в которую входит вершина, необходима для доступа к другим объектам входящим в транспортную сеть;

· X -- координата центра вершины в рамках транспортной сети;

· Y -- координата центра вершины в рамках транспортной сети;

· IsStart -- признак того, что эта вершина является стартовой для задачи поиска оптимального пути в транспортной сети;

· IsFinish -- признак того, что эта вершина является конечной для задачи поиска оптимального пути в транспортной сети;

· IsPartOfPath -- признак того, что эта вершина является частью оптимального пути;

· iGraph -- индекс графа, в который входит вершина;

· iEdge -- массив, содержащий номера рёбер, выходящих их текущей вершины.

Рассмотрим список методов:

· конструктор Vertex(TransportNetwork tn, int iGraph, int X, int Y) осуществляет инициализацию вершины, при этом вершина сразу получает координаты своего расположения;

· деструктор ~Vertex() осуществляет удаление вершины.

Перейдём к рассмотрению класса Edge, который содержит в себе описание рёбер, входящих в граф. Рассмотрим список полей:

· SrcVertex -- номер вершины из которой выходит это ребро;

· DestVertex -- номер вершины в которую входит это ребро;

· IsPartOfPath -- признак того, что это ребро является частью найденного оптимального маршрута;

· Weight -- вес ребра, будет интерпретироваться как целое беззнаковое число.



Рассмотрим список методов:

· конструктор Edge(int srcVertex, int destVertex, int Weight) осуществляет инициализацию ребра, при этом указывается стартовая и конечная вершина, а так же вес добавляемого ребра;

· деструктор ~Edge() осуществляет удаление ребра.

2.9 Алгоритмы поиска маршрутов в графе

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

· поиск в ширину (breadth-first search -- BFS);

· поиск в глубину (depth-first search -- DFS).

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

Обе процедуры обхода графа используют одну фундаментальную идею, а именно: мы должны помечать вершины, которые уже видели, чтобы не пытаться посетить их снова. Иначе мы можем зациклиться и никогда не выйти из алгоритма. BFS и DFS различаются только порядком, в котором они рассматривают вершины.

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

Поиск в ширину следует использовать в том случае, если

1. нам не важен порядок, в котором мы обходим вершины и ребра графа, то есть нас устроит любой,

2. нам нужно найти кратчайший путь в невзвешенном графе.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам -- метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т.д.

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

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.

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

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

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

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

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

Пусть задан граф G = (V,E), где V -- множество вершин графа, E -- множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Из множества всех белых вершин выберем любую вершину, обозначим её v1.

2. Выполняем для нее процедуру DFS(v1).

3. Перекрашиваем ее в черный цвет.

4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр -- вершина uU)

1. Перекрашиваем вершину u в серый цвет.

2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:

a. Если вершина окрашена в белый цвет, выполняем процедуру DFS(w).

b. Окрашиваем w в черный цвет.

2.12 Алгоритм Форда-Фалкерсона

Алгоритм Форда-Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

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

2.13 Алгоритм Прима

Алгоритм Прима решает задачу поиска остовного дерева.

Остовным деревом графа G (V,E) называется подмножество ребер из E, образующее дерево и соединяющее все вершины из V. Для реберно-взвешенных графов особый интерес представляет остовное дерево минимального веса, то есть остовное дерево, сумма весов ребер которого минимальна.

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

Главным недостатком этого алгоритма является то, что он не даёт сам маршрут, но на его основе строится алгоритм Дейкстры.

2.14 Алгоритм Дейкстры

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

Для заданной вершины s он находит кратчайший путь от s до всех остальных вершин, включая желаемую вершину t.

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

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

Если бы транспортная сеть ограничивалась одним графом, то алгоритм Дейкстры являлся бы одним из лучших выборов для поиска оптимального пути. Но, сама идея алгоритма при учёте количества пересадок может привести к тому, что некоторые потенциально достижимые вершины никогда не будут достигнуты, т.к. алгоритм «израсходует» все допустимые пересадки, стремясь сделать путь максимально дешёвым. В первую очередь это связано с тем, что поиск осуществляется не только для целевой вершины, но и для всех вершин входящих в транспортную сеть.

2.15 Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда -- алгоритм поиска кратчайшего пути во взвешенном графе. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Для реализации этого алгоритма чаще всего используются принципы динамического программирования.

Он имеет несомненное преимущество перед алгоритмом Дейкстры т.к. позволяет ограничивать поиск не только стоимостью пути, но и количеством рёбер входящих в этот путь.

Но он не позволяет формализовать и алгоритмизировать ограничения на количество пересадок, т.к. в нём, как и в алгоритме Дейкстры путь ищется не только до заданной вершины, но и для всех остальных.

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

Выводы:

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



3. РЕАЛИЗАЦИЯ МОДЕЛИ

3.1 Выбор среды разработки

Для реализации программного комплекса использовался язык высокого уровня C# и среда разработки MS Visual Studio 2010. Этот выбор обусловлен исходя из следующих критериев:

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

2. Язык C# так же обладает рядом преимуществ по сравнению с Object Pascal, т.к. является более новым и более развитым языком.

3. В нём на очень высоком уровне реализованы механизмы безопасности кода.

4. Ещё одним несомненным плюсом является наличие русскоязычной развитой справочной системы, что значительно упрощает процесс программирования.

3.2 Визуализация транспортной сети

Рассмотрим алгоритм визуализации транспортной сети.

В функцию передаются два флага, которые позволяют временно скрывать части транспортной сети помеченные как невидимые и как удалённые.

Текущие объекты (вершины и рёбра) отрисовываются с использованием полужирного начертания линий и шрифтов.

Перейдём непосредственно к алгоритму.

Сначала отрисовывались рёбра, т.к. вершины их перекрывают и визуально находятся на один уровень выше.

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

В середине ребра рисуется кружочек, в который вписывается числовое значение, характеризующее вес ребра.

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

Предусмотрена система обозначений в виде суффиксов веса:

Ч -- ребро недоступно;

° -- ребро помечено как невидимое;

† -- ребро помечено для удаления.

После того, как отрисованы рёбра, начинается визуализация вершин.

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

Для вершин предусмотрена та же система обозначений, что и для рёбер. Кроме этого предусмотрено ещё два возможных суффикса.

» -- вершина является стартовой;

« -- вершина является конечной.

3.3 Редактирование транспортной сети

3.3.1 Добавление элементов

При добавлении нового графа в конец списка добавляется ещё одни элемент, и он становится текущим, после чего пользователь может задать имя графа, описание, цвет и прочие характеристики.

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

Добавление ребра осуществляется в два этапа. При нажатии на кнопку «Добавить» текущая вершина считается стартовой, и пользователь переходит в режим добавления ребра, в котором он дважды должен кликнуть на вершине конечной. Предусмотрен запрет на создание петель и дублирующихся рёбер.

3.3.2 Удаление элементов

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

· если граф помечен на удаление, все рёбра и вершины в него входящие так же помечаются на удаление;

· если вершина помечена на удаление, все рёбра ей инцидентные также помечаются на удаление;

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

3.3.3 Редактирование элементов

Пользователь может менять все характеристики элементов. При этом на признак доступности элемента и признак невидимости распространяются те же правила что и на признак пометки на удаление.

А все элементы управления на форме имеют соответствующие обработчики событий, которые при изменении значений сразу фиксируют их.



3.3.4 Загрузка и сохранение транспортной сети

Для хранения данных использовался формат XML. Этот открытый формат имеет явные преимущества, т.к. является стандартом. Таким образом, транспортная сеть в этом формате потенциально может использоваться и в других приложениях.

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

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

Использовались стандартные диалоги открытия и сохранения файлов.

3.4 Задание условий поиска

Условия поиска задаются при помощи компонента numeric UpDown.

3.4.1 Поиск маршрутов

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

Все представленные алгоритмы обладают похожей секцией инициализации:

Перед осуществлением непосредственного поиска выполняются следующие действия.

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

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

3. Все вершины, которые ранее были помечены как часть пути, должны потерять эту отметку.

4. Все рёбра, которые ранее были помечены как часть пути, должны потерять эту отметку.

5. Создаётся стек для хранения вершин входящих в оптимальный путь. Создаётся стек для хранения рёбер входящих в оптимальный путь. По идее этот стек является избыточным, т.к. рёбра могут быть восстановлены из последовательности вершин, но его наличие позволяет получить к рёбрам непосредственный доступ без дополнительных затрат на их поиск. Использование стека для хранения обусловлено тем фактом, что для поиска в глубину эта структура данных является более удобной и естественной.

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

7. Создаётся стек для хранения вершин, входящих в текущий путь. Создаётся стек для хранения рёбер, входящих в текущий путь. Причины, по которым для хранения используется стек аналогичны перечисленным в пункте 5.

8. Вес текущего пути принимается за ноль.

9. Количество сделанных пересадок принимается за ноль.

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

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

2. Из стека извлекаются все рёбра вошедшие в оптимальный маршрут.

a. Каждое ребро, извлечённое из стека, помечается как часть оптимального маршрута;

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

3. Осуществляется отрисовка транспортной сети с отмеченным на ней маршрутом.

3.4.2 Поиск в глубину (рекурсивная версия)

Перейдём к самому алгоритму поиска. Данная версия алгоритма поиска в глубину была реализована с использованием рекурсии, т.к. рекурсия является очень естественным приёмом при работе с графами. Учитывая тот факт, что использование рекурсии может приводить к замедлению работы алгоритма в следующем параграфе будет рассмотрена версия алгоритма поиска в глубину без использования рекурсии.

Основная идея алгоритма состоит в следующем.

В функцию передаётся 4 параметра:

1. Вершина, в которой мы сейчас находимся (из какой вершины пришли).

2. Вершина, в которую мы хотим пойти.

3. Ребро, по которому мы хотим пойти.

4. Вершина, в которую мы хотим попасть.

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

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

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

Перейдём к штатному режиму работы алгоритма.

В-первую очередь проверяется «А можно ли идти в эту вершину?».

Идти нельзя если:

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

· вершина заблокирована;

· ребро заблокировано.

Если нельзя, то функция досрочно прекращает свою работу.

Во-вторых, проверяется «А нужно ли идти в эту вершину?».

Идти не нужно если:

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

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

Если не нужно, то функция досрочно прекращает свою работу.

После этих проверок вершина, которая подходит по всем параметрам, добавляется в стек вершин, в котором хранится текущий путь.

Затем пересчитываются показатели.

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

· при необходимости увеличивается количество пересадок.

Делается проверка «А не достигли ли мы заданной вершины?».

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

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

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

· уменьшается вес текущего пути (т.к. мы движемся обратно по маршруту);

· при необходимости уменьшается количество пересадок.

И, наконец, из стека извлекается текущая вершина.

3.4.3 Поиск в глубину (нерекурсивная версия)

Нерекурсивная версия этого алгоритма может иметь выигрыш по скорости работы в связи с тем что:

· Каждый вызов рекурсивной функции приводит к тому, что происходит надстраивание программного стека, сохраняется точка возврата, создаётся окружение для запуска функции, выделяется память под локальные переменные и т.д.

o увеличиваются требования по памяти;

o увеличиваются требования по количеству выполняемых инструкций.

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