Материал: Программирование на языке С#

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

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

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

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

поиск в ширину (breadth-first search - BFS); поиск в глубину (depth-first search - DFS).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

3. Разработка вычислительной системы транспортной логистики на языке C#

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

Для реализации программного комплекса использовался язык высокого уровня C# и среда разработки MS Visual Studio 2008. Этот выбор обусловлен исходя из следующих критериев [5] [9] [15] [17] [22]:

. Среда разработки и язык позволяют быстро и качественно создавать пользовательский интерфейс высокого уровня, используя дизайнер форм, сводя к минимуму труд программиста. В качестве альтернативы могла быть рассмотрена среда разработки Code Gear 2009, но MS Visual Studio 2008 явно обладает рядом преимуществ т.к. является естественной платформой для разработки под Windows.

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

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

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

. Ещё одной альтернативным языком могла бы быть JAVA, но для её работы требуется устанавливать собственный Framework, в то время как Framework необходимый для работы программ написанных с использованием C# уже присутствует на уровне операционной системы.

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

. Ещё одним преимуществом может рассматриваться использование байт-кода, что обеспечивает высокую скорость работы и более полное использование аппаратных возможностей ПК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Листинг предложенных алгоритмов представлены в приложении.

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

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

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

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

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

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

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

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

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

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

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

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