Материал: Проектирование вычислительной системы транспортной логистики

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

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

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

Поиск в ширину выполняется в следующем порядке: началу обхода приписывается метка 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. Этот открытый формат имеет явные преимущества, т.к. является стандартом. Таким образом, транспортная сеть в этом формате потенциально может использоваться и в других приложениях.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если нельзя, то функция досрочно прекращает свою работу. Во-вторых, проверяется «А нужно ли идти в эту вершину?». Идти не нужно если:

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