Содержание
Цель, постановка задачи и алгоритм….3
Реализация алгоритма4
Программа…7
Результаты.43
Список литературы…48
Выдержка из текста работы
К курсовому проекту Иванова Сергея Дмитриевича, слушателя группы 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 Методы решения
Классическую транспортную задачу можно решить симплекс-методом, но есть и другие подходы.
Например, сначала ищется опорный план при помощи одного из ниже перечисленных методов:
· «северо-западного угла»,
· «наименьшего элемента»,
· двойного предпочтения,
· аппроксимацией Фогеля
А уже затем при помощи теории графов ищется оптимальный путь.
Рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней. Пункты производства и потребления попарно соединяются рёбрами бесконечной пропускной способности и цены за единицу потока Cij.
К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.
Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.
Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана-Форда. При возврате потока стоимость считается отрицательной.
Алгоритм mincost maxflow можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма mincost maxflow происходит не более чем за O(v2e2) операций (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 увеличиваются требования по количеству выполняемых инструкций.
· Кроме того, алгоритм уже имеет в своём составе стек, в котором хранится текущий путь. В принципе, при использовании рекурсивной версии поиска в глубину есть возможность избежать необходимости хранения пройденного пути в стеке, т.к. этот путь может быть восстановлен при обратном ходе рекурсии. Кроме того, современные процессоры и компиляторы имеют ряд механизмов, оптимизирующих рекурсивные вызовы таким образом, что накладные расходы будут практически не заметны. Но, учитывая, что в данном случае решается не классическая задача поиска в глубину, этот подход может вызвать ряд проблем.
В нерекурсивную функцию поиска в глубину передаётся только два параметра: стартовая вершина, и вершина в которую мы хотим попасть.
Рассмотрим сам алгоритм.
1. Осуществляется проверка того, не является ли стартовая вершина совпадающей с финальной вершиной. Если это так, то осуществляется досрочный выход из функции поиска маршрута. При этом ни одно ребро не может быть помечено как часть оптимального пути т.к. согласно принятым выше ограничениям в графе не могут присутствовать петли. Поэтому только одна вершина добавляется в список вершин, входящих в оптимальный путь.
2. Для каждой вершины заводится вспомогательный массив, в котором хранится порядковый номер ребра, которое было выбрано перед переходом в следующую вершину. В рекурсивной версии алгоритма не было необходимости в этой переменной, т.к. эта информация сохранялась перед рекурсивным вызовом в локальной переменной. Элементы этого вспомогательного массива инициализируются значением минус единица, т.к. ни одно ребро ещё не было выбрано.
3. В стек складывается текущая вершина, с которой начинается поиск.
4. Поиск продолжается до тех пор, пока не будут просмотрены все возможные маршруты. Учитывая специфику алгоритма поиска (которая будет рассмотрена ниже) при возврате назад, все посещённые ранее вершины постепенно извлекаются из стека. Поэтому условием завершения поиска является извлечение из стека последней вершины (т.е. когда он становится пустым). В рекурсивной версии мы имеем почти аналогичное условие, только там пустым становится стек рекурсивных вызовов.
5. Верхняя вершина стека является текущей. Осуществляется проверка того, а не дошли ли мы до финальной вершины.
a. Если мы дошли до финальной вершины, то необходимо выполнить уже стандартную проверку того, а не является ли найденный путь более лёгким по сравнению с текущим кандидатом на оптимальный маршрут. Если это действительно так, то текущий путь запоминается как оптимальный и его вес так же запоминается. Далее нам необходимо сделать шаг назад, что бы мы могли проверить альтернативные пути, исходящие из предыдущей вершины. Для этого нам необходимо просмотреть ребро, находящееся на вершине стека рёбер, и узнать из какой вершины мы пришли. Смысла дальнейшего передвижения из финальной вершины по графу нет, поэтому далее делается шаг назад:
I. из стека вершин текущего маршрута извлекается верхняя вершина;
II. из стека рёбер текущего маршрута извлекается верхнее ребро;
III. вес текущего маршрута уменьшается на вес извлечённого ребра;
IV. если возврат назад на один шаг связан с пересадкой, то текущее количество сделанных пересадок уменьшается на единицу.
b. В том случае, если мы ещё не дошли до финальной вершины нам необходимо просмотреть все рёбра, по которым может быть осуществлено движение из текущей вершины. При этом отсекаются пути, которые приводят нас в вершины, которые уже хранятся в текущем пути. Это делается в силу того, что маршрут, содержащий цикл никогда не может претендовать на статус оптимального в плане суммарного веса посещённых рёбер. Так же не рассматриваются заблокированные рёбра и рёбра, которые приводят в заблокированные вершины. В силу ограничений на максимальное количество пересадок не рассматриваются рёбра, которые приводят к превышению заданного количества. Для первого ребра, прошедшего вышеуказанную проверку, выполняется следующий набор действий:
I. вершина, в которую попадает ребро, добавляется в стек вершин и становится текущей;
II. ребро добавляется в стек, в котором хранится текущий маршрут;
III. на этом цикл завершается, т.к. делается шаг в следующую вершину, но для вершины, из которой делается шаг, запоминается на каком ребре была сделана остановка, с тем, чтобы по возвращению в эту вершину, продолжить перебор возможных маршрутов.
c. После того, как все рёбра, выходящие из текущей вершины, проверены, делается шаг назад. Для этого
I. из стека вершин текущего маршрута извлекается верхняя вершина;
II. из стека рёбер текущего маршрута извлекается верхнее ребро;
III. вес текущего маршрута уменьшается на вес извлечённого ребра;
IV. если возврат назад на один шаг связан с пересадкой, то текущее количество сделанных пересадок уменьшается на единицу;
V. и так как мы ушли из текущей вершины, счётчик просмотренных из неё рёбер обнуляется, т.е. принимает значение минус единица.
Очевидно, что этот алгоритм является самым эффективным в плане использования оперативной памяти, т.к. мы храним только один текущий путь.
Рассмотрим вопрос, связанный со скоростью работы. Все представленные в этой работе алгоритмы основаны на полном переборе. Во всех алгоритмах используются одинаковые эвристики, позволяющие отсекать заведомо неоптимальные ветви. Следовательно, с этой точки зрения ускорение возможно по следующим направлениям:
1. отказаться от рекурсии (что и было сделано в рамках данного алгоритма);
2. использование избыточных данных, позволяющих хранить уже рассчитанные значения (что и было сделано во всех предложенных алгоритмах);
3. использование многопоточных алгоритмов, рассчитанных на выполнение на многоядерных процессорах (что и будет сделано в следующих разделах).
3.4.4 Поиск в ширину (однопоточная версия)
Функция поиска в ширину является более требовательной в плане использования оперативной памяти, т.к. ней все пути рассматриваются параллельно. Особенно эта проблема становится актуальной в графах с большим количеством связей. Поэтому однопоточная версия этого алгоритма не желательна для использования и приводится в силу того, что на её основе будет строиться многопоточная версия.
Алгоритму на вход подаётся два параметра, номер стартовой вершины и номер конечной вершины.
Перед запуском алгоритма осуществляется проверка на то, не совпадают ли стартовая и конечная вершина. В случае совпадения производится досрочный выход из функции подобно тому, как это делалось в предыдущем алгоритме.
Как и раньше текущий путь будет размещаться в структуре данных типа стек. Туда помещается стартовая вершина.
В классической версии поиска в ширину используется структура данных типа очередь. Однако мы не можем использовать только очередь, т.к. нам важен не только обход графа в заданном порядке, нам необходимо иметь возможность хранения всего пройденного пути и сравнения его с оптимальным. Именно в силу этого условия будет использована не просто очередь, а очередь стеков (в каждом стеке будет храниться один из потенциальных путей).
На самом деле будет использовать 4 очереди.
В первой очереди будут храниться стеки вершин потенциальных маршрутов.
Во второй очереди будут храниться стеки рёбер потенциальных маршрутов.
В третьей очереди будут храниться веса потенциальных маршрутов.
И в четвёртой очереди будут храниться количества пересадок сделанных на текущий момент для каждого из потенциальных маршрутов.
По мере достижения финальной вершины, маршруты будут удаляться из очередей. Поэтому условием окончания работы алгоритма будет тот факт, что одна из очередей будет пуста. Пусть это будет очередь вершин.
Основной цикл до опустения очереди вершин будет выглядеть следующим образом:
1. Из начала очереди маршрутов из вершин извлекается маршрут и делается текущим.
2. Из начала очереди маршрутов из рёбер извлекается маршрут и делается текущим.
3. Из начала очереди весов извлекается вес текущего маршрута.
4. Из начала очереди количества пересадок извлекается текущее количество пересадок.
5. Извлекаем с вершины стека вершин текущего маршрута вершину и делаем её текущей.
6. Если текущая вершина совпадает с финальной вершиной, то осуществляется проверка того, а не является ли текущий путь более лёгким, по сравнению с текущим, считающимся оптимальным маршрутом. И если это так, то он записывается на его место и его вес также запоминается.
7. Если же текущая вершина не является финальной, то нам необходимо сформировать все возможные направления движения из неё исходящие. Для этого просматриваются все рёбра, которые выходят из текущей вершины. Не рассматриваются рёбра, которые приводят к возникновению циклов, т.е. приводят к вершинам уже находящимся в текущем пути. Так же не рассматриваются заблокированные рёбра и рёбра, приводящие в заблокированные вершины. Не рассматриваются рёбра, имеющие такой вес, которые будучи сложенным с текущим весом, будет превышать вес текущего оптимального маршрута. Не рассматриваются рёбра, которые ведут к превышению максимально возможного количества пересадок. После того, как подходящие ребра найдены, для каждого из них осуществляется следующая последовательность действий:
a. в стек вершин добавляется конечная вершина ребра;
b. в стек рёбер добавляется ребро;
c. пересчитывается текущий вес за счёт прибавления веса ребра, по которому осуществляется переход;
d. пересчитывается текущее количество пересадок, в соответствии с ребром по которому осуществляется переход;
e. копия стека вершин помещается в конец очереди стеков вершин;
f. копия стека рёбер помещается в конец очереди стеков рёбер;
g. вес текущего пути помещается в конец очереди весов;
h. количество пересадок текущего пути помещается в конец очереди количества пересадок;
i. делается шаг назад путём извлечения вершины из стека текущих вершин и извлечением ребра из стека текущих рёбер, также пересчитывается текущий вес путём вычитания веса удалённого ребра и пересчитывается количество сделанных пересадок в сторону уменьшения.
3.4.5 Поиск в ширину (многопоточная версия)
Этот метод является улучшенной версией поиска в ширину. Он сохраняет тот же самый принцип обхода графа, но позволяет одновременно просматривать сразу несколько потенциальных маршрутов. Распараллеливание поиска в глубину невозможно в силу специфики порядка обхода вершин. В данной версии алгоритма не осуществляется ограничение на максимальное количество одновременно работающих потоков, и при необходимости, может быть осуществлено за счёт использования механизма пула потоков.
В силу многопоточности для запуска алгоритма используются дополнительные построения.
1. Заводится глобальная переменная, в которой хранится текущее количество активных потоков. Каждый поток при запуске увеличивает её значение и уменьшает перед завершением.
2. Заводится вспомогательная структура данных, хранящая в себе полный набор параметров необходимых для алгоритма. Это делается в силу того, что функции-делегату представляющей собой тело потока может быть передан только один параметр типа object. В состав структуры входят следующие поля:
a. текущая вершина;
b. конечная вершина;
c. текущий вес;
d. текущее количество пересадок;
e. стек вершин, входящих в текущий путь;
f. стек рёбер, входящих в текущий путь.
После запуска потока для осуществления поиска в ширину главный поток, отвечающий за работу формы должен дождаться завершения всех вспомогательных потоков. Для этого он ждёт завершения первого созданного потока, а затем ждёт пока переменная, в которой хранится текущее количество активных потоков, не станет равной нулю. Отдельное ожидание завершения первого порождённого потока необходимо в силу того, что он может не успеть инициализироваться и инкрементировать значение переменной, в которой хранится текущее количество активных потоков.
Рассмотрим сам алгоритм:
1. Увеличивается количество активных потоков.
2. В локальный стек вершин помещается текущая вершина.
3. Если текущая вершина совпадает с финальной вершиной, то необходимо проверить, не является ли текущий путь лучшим по сравнению с кандидатом на оптимальность. Однако, подобная проверка может быть осуществлена только в рамках критической секции, которая помогает избежать потенциальных конфликтов с параллельными потоками. И, если текущий путь лучше оно копируется в качестве оптимального и его вес запоминается (эти два действия так же должны осуществляться в рамках критической секции).
4. Если же мы ещё не дошли до финальной вершины. Перебираются все рёбра исходящие из текущей вершины. Не рассматриваются рёбра, которые приводят к возникновению циклов, т.е. приводят к вершинам уже находящимся в текущем пути. Так же не рассматриваются заблокированные рёбра и рёбра, приводящие в заблокированные вершины. Не рассматриваются рёбра, имеющие такой вес, которые будучи сложенным с текущим весом, будет превышать вес текущего оптимального маршрута. Не рассматриваются рёбра, которые ведут к превышению максимально возможного количества пересадок. После того, как подходящие ребра найдены, для каждого из них осуществляется следующая последовательность действий:
a. формируется копия текущего стека вершин;
b. формируется копия текущего стека рёбер;
c. формируется копия веса текущего пути;
d. формируется копия количества пересадок на текущем пути;
e. в копию стека вершин помещается конец ребра, по которому мы хотим идти;
f. в копию сетка рёбер помещается рёбро, по которому мы хотим идти;
g. копия веса текущего пути увеличивается на вес ребра, по которому мы хотим пойти;
h. копия количества пересадок на текущем пути, если ребро ведёт в другую транспортную сеть;
i. и вместо того чтобы помещать это всё в конец очереди, как это делалось в классическом поиске в ширину создаётся ещё один поток с только что сформированным набором параметров.
5. После того как все возможные пути из текущей вершины перебраны и соответствующие потоки стартовали, поток уничтожается, уменьшая количество запущенных потоков на единицу.
3.5 Пример работы алгоритма
Рассмотрим небольшой пример. Пусть необходимо найти путь из вершины A в вершину H. При двух разрешённых пересадках оптимальный путь (представленный на верхнем рисунке) состоит из четырёх рёбер и имеет вес равный 13. При трёх разрешённых пересадках оптимальный путь (представленный на нижнем рисунке) состоит из одиннадцати рёбер и имеет вес равный 11.
Подобный результат обеспечивают все разработанные алгоритмы.
Рисунок 2.1 — Пример работы программы
ЗАКЛЮЧЕНИЕ
В ходе курсового проекта был проведён анализ методов решения задач транспортной логистики. В результате проведённого исследования было разработано четыре модифицированных алгоритма поиска оптимального маршрута в транспортной сети с возможностью задания широкого спектра дополнительных условий и ограничений.
В результате проведённого анализа наиболее заслуживающими внимания с точки зрения практического использования были признаны: нерекурсивный поиск в глубину и многопоточный поиск ширину. Первый из них менее требователен к оперативной памяти и ориентирован на исполнение в системах, базирующихся на процессоре с одним ядром. Второй имеет большие требования к оперативной памяти, но за счёт использования многопоточности может быть более быстродействующим в системах, базирующихся на многоядерных процессорах.
Так же была разработана собственная модель для внутреннего представления транспортной сети.
В качестве среды разработки был выбран пакет Visual Studio 2010. Реализация велась с использованием языка программирования высокого уровня C#. Для хранения транспортной сети использовались принципы сериализации объектов и формат XML.
На основе разработанного модифицированного алгоритма и модели внутреннего представления данных был создан программный комплекс, обладающий следующими возможностями:
1. Создание, модификация, загрузка, сохранение транспортной сети.
2. Визуализация транспортной сети с возможностью с возможностью временного сокрытия отдельных её частей.
3. Задание условий поиска и критериев оптимальности поиска маршрута.
4. Осуществление поиска маршрутов с учётом заданных ограничений.
Одним из дальнейших направлений развития данного курсового проекта может быть более подробное исследование многопоточной версии алгоритма поиска в ширину и определения такого максимального количества работающих параллельных потоков, которое бы обеспечивало и высокую скорость работы и не допускало бы пробуксовки.
алгоритм транспортный маршрут граф
СПИСОК ЛИТЕРАТУРЫ
1. Оре, О. Теория графов. М.: Наука, 1968.
2. Харари, Ф. Теория графов. М.: Мир, 1973.
3. Уилсон, Р. Введение в теорию графов. Пер с англ. М: Мир, 1977.
4. Емеличев, В.А., Лекции по теории графов. М.: Наука, 1990.
5. Кормен, М. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ. М.: «Вильямс», 2006.
6. Сербин, В.Д. Основы логистики. Таганрог: ТРТУ, 2004.
7. Сток, Р. Стратегическое управление логистикой. М.: Инфра-М, 2005.
8. Хемди, А. Введение в исследование операций. М.: «Вильямс», 2007.
9. Вентцель, С.Е. Исследование операций: задачи, принципы, методология. М.: Наука, 1980.
10. Мудров, В.И. Задача о коммивояжере. М.: «Знание», 1969.
11. Ананий, В. Алгоритмы: введение в разработку и анализ. М.: «Вильямс», 2006.
12. Муртаф, Б. Современное линейное программирование. М.: Мир, 1984.
13. Стивен, С. Олимпиадные задачи по программированию. М.: ИД Кудиц-образ, 2005.
14. Меньшиков, Ф. Олимпиадные задачи по программированию. Спб.: Питер, 2006.
15. Дейтл, Х. C#. СПб.: БХВ-Петербург, 2006.
16. Павловская, Т.А. C#. Программирование на языке высокого уровня. СПб.: Питер, 2007.
ПРИЛОЖЕНИЕ А
Функция отрисовки транспортной сети
public void Draw(bool showInvisible, bool showDeleted)
//отрисовать граф
//перо для отрисовки
Pen dcPen = new Pen(Color.Black, 1);
//кисть для отрисовки
Brush dcBrush = new SolidBrush(Color.White);
//если необходимо изменить размер компонента перед отрисовкой
if (this.pb.Width != this.width || this.pb.Height != this.height)
this.pb.Width = this.width;
this.pb.Height = this.height;
this.pb.Image = new Bitmap(this.width, this.height);
this.dc = Graphics.FromImage(this.pb.Image);
//отрисовка вед?тся в высоком качестве
dc.SmoothingMode =
System.Drawing.Drawing2D.SmoothingMode.HighQuality;
dc.TextRenderingHint =
System.Drawing.Text.TextRenderingHint.SingleBitPerPixel;
//заливаем всю картинку белым цветом
this.dc.FillRectangle(dcBrush, 0, 0, this.width, this.height);
//перед тем как отрисовывать вершины, нужно отрисовать ребра
for (int i = 0; i < aEdge.Count; i++)
//отрисовываем только видимые и не помеченные как удаленные ребра
if ((aEdge[i].Visible == true || (aEdge[i].Visible == false && showInvisible
== true))
&& (aEdge[i].Deleted == false || (aEdge[i].Deleted == true &&
showDeleted == true)))
int x1 = aVertex[aEdge[i].srcVertex].X;
int y1 = aVertex[aEdge[i].srcVertex].Y;
int x2 = aVertex[aEdge[i].destVertex].X;
int y2 = aVertex[aEdge[i].destVertex].Y;
int xm = (x1 + x2) / 2;
int ym = (y1 + y2) / 2;
//цвет исходящий от первой вершины
dcPen.Width = 4;
dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;
dc.DrawLine(dcPen, x1, y1, xm, ym);
dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;
dc.DrawLine(dcPen, x2, y2, xm, ym);
dcPen.Width = 2;
dcPen.Color = aEdge[i].Color;
dc.DrawLine(dcPen, x1, y1, x2, y2);
((SolidBrush)dcBrush).Color = aEdge[i].Color;
string suffix = «»;
string prefix = «»;
if (aEdge[i].Enabled == false) suffix += «Ч»;
if (aEdge[i].Visible == false) suffix += «°»;
if (aEdge[i].Deleted == true) suffix += «†»;
if (aEdge[i].IsPartOfPath == true)
//suffix += » =»;
//prefix = «= «;
((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200);
if (aEdge[i].Selected == true)
dcPen.Width = 2;
//рисуем кружочек за который можно таскать ребро
dc.FillEllipse(dcBrush, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;
dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot;
dcPen.DashOffset = 0;
dc.DrawEllipse(dcPen, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;
dcPen.DashOffset = 1;
dc.DrawEllipse(dcPen, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;
//надпись на ребре
int x = xm;
int y = ym;
Size textSize = TextRenderer.MeasureText(prefix +
aEdge[i].Weight.ToString() + suffix, textFontBold);
x -= textSize.Width / 2;
y -= textSize.Height / 2;
Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);
TextRenderer.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() +
suffix, textFontBold, textRect, Color.Black);
else
dcPen.Width = 1;
//рисуем кружочек за который можно таскать ребро
dc.FillEllipse(dcBrush, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;
dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot;
dcPen.DashOffset = 0;
dc.DrawEllipse(dcPen, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;
dcPen.DashOffset = 1;
dc.DrawEllipse(dcPen, xm — rSize, ym — rSize, 2 * rSize, 2 * rSize);
dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;
//надпись на ребре
int x = xm;
int y = ym;
Size textSize = TextRenderer.MeasureText(prefix +
aEdge[i].Weight.ToString() + suffix, textFontNormal);
x -= textSize.Width / 2;
y -= textSize.Height / 2;
Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);
TextRenderer.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() +
suffix, textFontNormal, textRect, Color.Black);
//теперь необходимо отрисовать вершины
for (int i = 0; i < aVertex.Count; i++)
//отрисовываем только видимые и не помеченные как удаленные
вершины
if ((aVertex[i].Visible == true || (aVertex[i].Visible == false &&
showInvisible == true))
&& (aVertex[i].Deleted == false || (aVertex[i].Deleted == true &&
showDeleted == true)))
//цвет границы
dcPen.Color = aGraph[aVertex[i].iGraph].Color;
//цвет заполнения
((SolidBrush)dcBrush).Color = aVertex[i].Color;
string suffix = «»;
if (aVertex[i].Enabled == false) suffix += «.»;
if (aVertex[i].Visible == false) suffix += «°»;
if (aVertex[i].Deleted == true) suffix += «†»;
if (aVertex[i].IsStart == true) suffix += » »»;
if (aVertex[i].IsFinish == true) suffix += » «»;
if (aVertex[i].IsPartOfPath == true)
((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200);
if (aVertex[i].Selected == true)
dcPen.Width = 2;
//рисуем квадратик за который можно таскать вершину
dc.FillRectangle(dcBrush, aVertex[i].X — dSize, aVertex[i].Y — dSize, 2 *
dSize, 2 * dSize);
dc.DrawRectangle(dcPen, aVertex[i].X — dSize, aVertex[i].Y — dSize, 2 *
dSize, 2 * dSize);
//надпись на вершине
int x = aVertex[i].X;
int y = aVertex[i].Y;
Size textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix,
textFontBold);
x -= textSize.Width / 2;
y -= textSize.Height / 2;
Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);
dc.FillRectangle(dcBrush, textRect);
dc.DrawRectangle(dcPen, textRect);
TextRenderer.DrawText(this.dc, aVertex[i].Title + suffix, textFontBold,
textRect, Color.Black);
else
dcPen.Width = 1;
//рисуем квадратик за который можно таскать вершину
dc.FillRectangle(dcBrush, aVertex[i].X — dSize, aVertex[i].Y — dSize, 2 *
dSize, 2 * dSize);
dc.DrawRectangle(dcPen, aVertex[i].X — dSize, aVertex[i].Y — dSize, 2 *
dSize, 2 * dSize);
//надпись на вершине
int x = aVertex[i].X;
int y = aVertex[i].Y;
Size textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix,
textFontNormal);
x -= textSize.Width / 2;
y -= textSize.Height / 2;
Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);
dc.FillRectangle(dcBrush, textRect);
dc.DrawRectangle(dcPen, textRect);
TextRenderer.DrawText(this.dc, aVertex[i].Title + suffix, textFontNormal,
textRect, Color.Black);
//обновляем картинку т.к. перерисовали
this.pb.Refresh();
ПРИЛОЖЕНИЕ Б
Свойство, реализующее признак видимости графа
new public bool Visible
return base.Visible;
base.Visible = value;
//наследовать свойство видимости всем принадлежащим графу
вершинам
for (int i = 0; i < this.iVertex.Count; i++)
tn.aVertex[this.iVertex[i]].Visible = value;
ПРИЛОЖЕНИЕ В
Свойство, реализующее признак видимости вершины
new public bool Visible
return base.Visible;
base.Visible = value;
//наследовать свойство видимости смежным ребрам
for (int i = 0; i < this.iEdge.Count; i++)
tn.aEdge[this.iEdge[i]].Visible = value;
ПРИЛОЖЕНИЕ Г
Свойство базового класса, реализующее свойство видимости
public bool Visible
return this.visible;
this.visible = value;
ПРИЛОЖЕНИЕ Д
Функции для сохранения/загрузки транспортной сети
private void menuItemСохранить_Click(object sender, EventArgs e)
if (saveFileDialogTN.ShowDialog() == DialogResult.OK)
//экземпляр xmlSer класса XmlSerializer нужен для сериализации
XmlSerializer xmlSer = new
XmlSerializer(typeof(TransportNetworkSerialization));
//имя файла в который будет сохраняться результат сериализации
//string fileName = System.Environment.CurrentDirectory + «\\tst.xml»;
string fileName = saveFileDialogTN.FileName;
//поток fileStream для создания XML-файла
FileStream fileStream = new FileStream(fileName, FileMode.Create);
TransportNetworkSerialization tns = new TransportNetworkSerialization();
tn.PreSerialize(tns);
//сериализация
xmlSer.Serialize(fileStream, tns);
//закрываем поток
fileStream.Close();
} private void menuItemЗагрузить_Click(object sender, EventArgs e)
if (openFileDialogTN.ShowDialog() == DialogResult.OK)
//экземпляр xmlSer класса XmlSerializer нужен для десериализации
XmlSerializer xmlSer = new
XmlSerializer(typeof(TransportNetworkSerialization));
//имя файла из которого будет осуществляться десериализации
//string fileName = System.Environment.CurrentDirectory + «\\tst.xml»;
string fileName = openFileDialogTN.FileName;
//поток fileStream для чтения XML-файла
FileStream fileStream = new FileStream(fileName, FileMode.Open);
TransportNetworkSerialization tns = new TransportNetworkSerialization();
//десериализация
tns = (TransportNetworkSerialization)xmlSer.Deserialize(fileStream);
//закрываем поток
fileStream.Close();
//теперь нужно развернуть транспортную сеть
//нужно очистить все списки
tn.aEdge.Clear();
tn.aVertex.Clear();
tn.aGraph.Clear();
//и визуальные списки тоже необходимо очистить
comboBoxEdge.Items.Clear();
comboBoxVertex.Items.Clear();
comboBoxGraph.Items.Clear();
//и поля ввода тоже необходимо очистить
textBoxGraphTitle.Text = «»;
textBoxGraphDescription.Text = «»;
checkBoxGraphDeleted.Checked = false;
checkBoxGraphEnabled.Checked = true;
checkBoxGraphVisible.Checked = true;
panelGraph.BackColor = Color.Black;
textBoxVertexTitle.Text = «»;
textBoxVertexDescription.Text = «»;
checkBoxVertexDeleted.Checked = false;
checkBoxVertexEnabled.Checked = true;
checkBoxVertexVisible.Checked = true;
panelVertex.BackColor = Color.White;
textBoxEdgeTitle.Text = «»;
textBoxEdgeDescription.Text = «»;
checkBoxEdgeDeleted.Checked = false;
checkBoxEdgeEnabled.Checked = true;
checkBoxEdgeVisible.Checked = true;
panelEdge.BackColor = Color.White;
numericUpDownEdge.Value = 0;
//а теперь в списки нужно добавлять значения
//сначала будем добавлять графы
for (int i = 0; i < tns.aGraph.Length; i++)
buttonGraphAdd_Click(sender, e);
textBoxGraphTitle.Text = tns.aGraph[i].title;
textBoxGraphDescription.Text = tns.aGraph[i].description;
checkBoxGraphDeleted.Checked = tns.aGraph[i].deleted;
checkBoxGraphEnabled.Checked = tns.aGraph[i].enabled;
checkBoxGraphVisible.Checked = tns.aGraph[i].visible;
panelGraph.BackColor = Color.FromArgb(tns.aGraph[i].colorR,
tns.aGraph[i].colorG, tns.aGraph[i].colorB);
tn.aGraph[i].Color = panelGraph.BackColor;
//теперь необходимо добавить вершины
for (int i = 0; i < tns.aVertex.Length; i++)
comboBoxGraph.SelectedIndex = tns.aVertex[i].iGraph;
buttonVertexAdd_Click(sender, e);
textBoxVertexTitle.Text = tns.aVertex[i].title;
textBoxVertexDescription.Text = tns.aVertex[i].description;
checkBoxVertexDeleted.Checked = tns.aVertex[i].deleted;
checkBoxVertexEnabled.Checked = tns.aVertex[i].enabled;
checkBoxVertexVisible.Checked = tns.aVertex[i].visible;
panelVertex.BackColor = Color.FromArgb(tns.aVertex[i].colorR,
tns.aVertex[i].colorG, tns.aVertex[i].colorB);
tn.aVertex[i].Color = panelVertex.BackColor;
tn.aVertex[i].X = tns.aVertex[i].x;
tn.aVertex[i].Y = tns.aVertex[i].y;
//и, наконец необходимо добавить р?бра
for (int i = 0; i < tns.aEdge.Length; i++)
if (tn.AddEdge(tns.aEdge[i].srcvertex, tns.aEdge[i].destvertex) == true)
//его имя записываем в список
comboBoxEdge.Items.Add(tn.aEdge[tn.aEdge.Count — 1].Title);
//и оно становится текущим
comboBoxEdge.SelectedIndex = tn.aEdge.Count — 1;
textBoxEdgeTitle.Text = tns.aEdge[i].title;
textBoxEdgeDescription.Text = tns.aEdge[i].description;
checkBoxEdgeDeleted.Checked = tns.aEdge[i].deleted;
checkBoxEdgeEnabled.Checked = tns.aEdge[i].enabled;
checkBoxEdgeVisible.Checked = tns.aEdge[i].visible;
panelEdge.BackColor = Color.FromArgb(tns.aEdge[i].colorR,
tns.aEdge[i].colorG, tns.aEdge[i].colorB);
tn.aEdge[i].Color = panelEdge.BackColor;
numericUpDownEdge.Value = tns.aEdge[i].weight;
//сначала устанавливаем ширину и высоту транспортной сети
this.numericUpDownWidth.Value = tns.width;
this.numericUpDownHeight.Value = tns.height;
public void PreSerialize(TransportNetworkSerialization tns)
//подготовить данные для сериализации
//сначала подготовить графы
tns.aGraph = new GraphSerialization[this.aGraph.Count];
for (int i = 0; i < tns.aGraph.Length; i++)
tns.aGraph[i] = new GraphSerialization();
tns.aGraph[i].colorR = this.aGraph[i].Color.R;
tns.aGraph[i].colorG = this.aGraph[i].Color.G;
tns.aGraph[i].colorB = this.aGraph[i].Color.B;
tns.aGraph[i].deleted = this.aGraph[i].Deleted;
tns.aGraph[i].description = this.aGraph[i].Description;
tns.aGraph[i].enabled = this.aGraph[i].Enabled;
tns.aGraph[i].selected = this.aGraph[i].Selected;
tns.aGraph[i].title = this.aGraph[i].Title;
tns.aGraph[i].visible = this.aGraph[i].Visible;
//потом подготовить вершины
tns.aVertex = new VertexSerialization[this.aVertex.Count];
for (int i = 0; i < tns.aVertex.Length; i++)
tns.aVertex[i] = new VertexSerialization();
tns.aVertex[i].colorR = this.aVertex[i].Color.R;
tns.aVertex[i].colorG = this.aVertex[i].Color.G;
tns.aVertex[i].colorB = this.aVertex[i].Color.B;
tns.aVertex[i].deleted = this.aVertex[i].Deleted;
tns.aVertex[i].description = this.aVertex[i].Description;
tns.aVertex[i].enabled = this.aVertex[i].Enabled;
tns.aVertex[i].selected = this.aVertex[i].Selected;
tns.aVertex[i].title = this.aVertex[i].Title;
tns.aVertex[i].visible = this.aVertex[i].Visible;
tns.aVertex[i].x = this.aVertex[i].X;
tns.aVertex[i].y = this.aVertex[i].Y;
tns.aVertex[i].iGraph = this.aVertex[i].iGraph;
//и, наконец подготовить р?бра
tns.aEdge = new EdgeSerialization[this.aEdge.Count];
for (int i = 0; i < tns.aEdge.Length; i++)
tns.aEdge[i] = new EdgeSerialization();
tns.aEdge[i].colorR = this.aEdge[i].Color.R;
tns.aEdge[i].colorG = this.aEdge[i].Color.G;
tns.aEdge[i].colorB = this.aEdge[i].Color.B;
tns.aEdge[i].deleted = this.aEdge[i].Deleted;
tns.aEdge[i].description = this.aEdge[i].Description;
tns.aEdge[i].enabled = this.aEdge[i].Enabled;
tns.aEdge[i].selected = this.aEdge[i].Selected;
tns.aEdge[i].title = this.aEdge[i].Title;
tns.aEdge[i].visible = this.aEdge[i].Visible;
tns.aEdge[i].srcvertex = this.aEdge[i].srcVertex;
tns.aEdge[i].destvertex = this.aEdge[i].destVertex;
tns.aEdge[i].weight = this.aEdge[i].Weight;
//и не забыть сохранить ширину и высоту транспортной сети
tns.width = this.Width;
tns.height = this.Height;
ПРИЛОЖЕНИЕ Е
Функции для осуществления поиска в глубину
//многопоточный поиск в ширину
public void tbfs(object p)
thread_count++; //увеличиваем количество запущенных потоков
ptbfs t = (ptbfs)p;
t.current_pathV.Push(t.start); //в стеке лежит путь, а путь мы начинаем с
стартовой вершины
int v; //номер текущей вершины
v = t.current_pathV.Peek(); //узнаем номер текущей вершины
if (v == t.finish)
//если дошли до финальной вершины
lock (locker)
if (t.current_weight < best_weight)
best_weight = t.current_weight;
best_path = new Stack<int>(t.current_pathV);
best_pathE = new Stack<int>(t.current_pathE);
//если дошли до финальной вершины
else
//если же мы не дошли еще до финальной вершины
//идти из этой вершины во все остальные по очереди
foreach (int iE in tn.aVertex[v].iEdge)
int vv; //один из вариантов, куда можно пойти
if (tn.aEdge[iE].srcVertex == v)
vv = tn.aEdge[iE].destVertex;
else
vv = tn.aEdge[iE].srcVertex;
if (t.current_pathV.Contains(vv) == true) //туда идти нельзя, мы там уже
были
continue; //и дальше можно эту вершину не обсчитывать
if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она
заблокированная
continue; //и дальше можно эту вершину не обсчитывать
if (tn.aEdge[iE].Enabled == false)//по этому ребру идти нельзя, оно
заблокированное
continue; //и дальше можно эту вершину не обсчитывать
int w = tn.aEdge[iE].Weight; //вес того ребра по которому мы можем
пойти
lock (locker)
if (t.current_weight + w > best_weight)//есть более легкие пути
continue; //и дальше можно эту вершину не обсчитывать
int tr; //нужна ли пересадка для попадания в следующую
//она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)
tr = 1;
else
tr = 0;
if (t.current_transfer + tr > numericUpDownTransfer.Value) //есть более
короткие пути
continue; //и дальше можно эту вершину не обсчитывать
ptbfs tt = new ptbfs();
tt.current_pathV = new Stack<int>(t.current_pathV);
tt.current_pathE = new Stack<int>(t.current_pathE);
//идти в эту вершину
//tt.current_pathV.Push(vv); //положить в стек вершину
tt.current_pathE.Push(iE); //положить в стек ребро
//идти в эту вершину
//пересчитать показатели
tt.current_transfer = t.current_transfer + tr; //увеличим количество
пересадок
tt.current_weight = t.current_weight + w; //увеличим стоимость пути
//пересчитать показатели
tt.start = vv;
tt.finish = t.finish;
Thread ttt = new Thread(tbfs); //создали поток
ttt.Start(tt); //пустили поток с параметом
//если же мы не дошли еще до финальной вершины
thread_count—; //не забыть уменьшить текущее количество потоков
//поиск в ширину
private void bfs(int s, int finish)
//отдельно нужно рассмотреть случай если стартовая вершина
совпадает с финальной
if (s == finish)
{ //конечно это редкий случай, но тем не менее
best_path.Push(s);
return;
current_path.Push(s); //в стеке лежит путь, а путь мы начинаем с
стартовой вершины
//очередь стеков вершин, а в каждом стеке лежит путь
Queue<Stack<int>> qV = new Queue<Stack<int>>();
qV.Enqueue(new Stack<int>(current_path)); //положили в очередь
текущий путь
//очередь стеков р?бер, а в каждом стеке лежит путь
Queue<Stack<int>> qE = new Queue<Stack<int>>();
qE.Enqueue(new Stack<int>(current_pathE)); //положили в очередь
текущий путь
Queue<int> qW = new Queue<int>(); //очередь весов для каждого пути
qW.Enqueue(0); //положили в очередь текущий нулевой вес
Queue<int> qT = new Queue<int>(); //очередь количества пересадок для
каждого пути
qT.Enqueue(0); //положили в очередь текущее нулевое количество
пересадок
while (qV.Count != 0) //пока мы не просмотрим все возможные пути
current_path = new Stack<int>(qV.Dequeue()); //достаем из стека
текущий путь вершин
current_pathE = new Stack<int>(qE.Dequeue()); // достаем из стека
текущий путь ребер
current_weight = qW.Dequeue(); //узнаем его вес
current_transfer = qT.Dequeue(); // узнаем сколько пересадок было на
этом пути
int v; //номер текущей вершины
v = current_path.Peek(); // узнаем номер текущей вершины
if (v == finish)
//если дошли до финальной вершины
if (current_weight < best_weight)
best_weight = current_weight;
best_path = new Stack<int>(current_path);
best_pathE = new Stack<int>(current_pathE);
//если дошли до финальной вершины
else
//если же мы не дошли еще до финальной вершины
//идти из этой вершины во все остальные по очереди
foreach (int iE in tn.aVertex[v].iEdge)
int vv; //один из вариантов, куда можно пойти
if (tn.aEdge[iE].srcVertex == v)
vv = tn.aEdge[iE].destVertex;
else
vv = tn.aEdge[iE].srcVertex;
if (current_path.Contains(vv) == true) //туда идти нельзя, мы там уже
были
continue; //и дальше можно эту вершину не обсчитывать
if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она
заблокированная
continue; //и дальше можно эту вершину не обсчитывать
//по этому ребру идти нельзя, оно заблокированное
if (tn.aEdge[iE].Enabled == false)
continue; //и дальше можно эту вершину не обсчитывать
int w = tn.aEdge[iE].Weight; //вес того ребра по которому мы можем
пойти
if (current_weight + w > best_weight) //есть более легкие пути
continue; //и дальше можно эту вершину не обсчитывать
int t; //нужна ли пересадка для попадания в следующую
//она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)
t = 1;
else
t = 0;
//есть более короткие пути
if (current_transfer + t > numericUpDownTransfer.Value)
continue; //и дальше можно эту вершину не обсчитывать
//идти в эту вершину
current_path.Push(vv); //положить в стек вершину
current_pathE.Push(iE); //положить в стек ребро
//идти в эту вершину
//пересчитать показатели
current_transfer += t; //увеличим количество пересадок
current_weight += w; //увеличим стоимость пути
//пересчитать показатели
//генерируем для очереди очередное направление движения
qV.Enqueue(new Stack<int>(current_path));
//генерируем для очереди очередное направление движения
qE.Enqueue(new Stack<int>(current_pathE));
//генерируем для очереди очередное направление движения
qW.Enqueue(current_weight);
//генерируем для очереди очередное направление движения
qT.Enqueue(current_transfer);
//вернуться
current_path.Pop(); //достать из стека вершину
current_pathE.Pop(); //достать из стека ребро
//вернуться
//вернуться и пересчитать показатели
current_transfer -= t; //уменьшим количество пересадок
current_weight -= w; //уменьшим стоимость пути
//вернуться и персчитать показатели
//если же мы не дошли еще до финальной вершины
//нерекурсивный поиск в глубину
private void dfs(int s, int finish)
//отдельно нужно рассмотреть случай если стартовая вершина
совпадает с финальной
if (s == finish)
{ //конечно это редкий случай, но тем не менее
best_path.Push(s);
return;
int v; //номер текущей вершины
//в этом всмпомогательном массиве мы будем помнить индекс ребра,
по которому ходили из этой
вершины в последний раз
int[] d = new int[tn.aVertex.Count];
//ни из одной вершины никуда ещ? не ходили
for (int i = 0; i < tn.aVertex.Count; i++) d[i] = -1;
current_path.Push(s); //в стеке лежит путь, а путь мы начинаем со
стартовой вершины
while (current_path.Count != 0) //пока мы не просмотрим все возможные
пути
v = current_path.Peek(); //узна?м номер текущей вершины
if (v == finish)
//если дошли до финальной вершины
if (current_weight < best_weight)
best_weight = current_weight;
best_path = new Stack<int>(current_path);
best_pathE = new Stack<int>(current_pathE);
//если дошли
int e; //по какому ребру дошли до финальной вершины
//узна?м его по вершине стека, т.к. в стеке что-то точно есть
e = current_pathE.Peek();
int v1 = tn.aEdge[e].srcVertex; //начало ребра, по которому пришли
int v2 = tn.aEdge[e].destVertex; //конец ребра, по которому пришли
int t; //нужна ли была пересадка для попадания в эту вершину
//она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v1].iGraph != tn.aVertex[v2].iGraph)
t = 1;
else
t = 0;
int w = tn.aEdge[e].Weight; //вес ребра, по которому мы пришли в
финальную вершины
//пересчитать показатели
//уменьшить количество пересадок, т.к. мы собираемся делать шаг
назад
current_transfer -= t;
//уменьшить вес текущего пути, т.к. мы собираемся делать шаг назад
current_weight -= w;
//пересчитать показатели
//выйти из этой вершины
current_path.Pop(); //делаем шаг назад
current_pathE.Pop(); //делаем шаг назад
//выйти из этой вершины
//и так как мы из этой вершины ушли, то счетчик ребер для нее
обнуляется
d[v] = -1;
//если дошли до финальной вершины
else
//если же мы не дошли еще до финальной вершины
d[v]++; //ищем дальше по списку куда можно пойти
while (d[v] < tn.aVertex[v].iEdge.Count)
int vv; //в эту вершину есть ребро из текущей
int e = tn.aVertex[v].iEdge[d[v]]; //вот как раз это ребро и идет из
текущей
if (tn.aEdge[e].srcVertex == v)
vv = tn.aEdge[e].destVertex;
else
vv = tn.aEdge[e].srcVertex;
if (current_path.Contains(vv) == true)//туда идти нельзя, мы там уже
были
d[v]++; //ищем дальше по списку куда можно пойти
continue; //и дальше можно эту вершину не обсчитывать
if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она
заблокированная
d[v]++; //ищем дальше по списку куда можно пойти
continue; //и дальше можно эту вершину не обсчитывать
//по этому ребру идти нельзя, оно заблокированное
if (tn.aEdge[e].Enabled == false)
d[v]++; //ищем дальше по списку куда можно пойти
continue; //и дальше можно эту вершину не обсчитывать
int w = tn.aEdge[e].Weight; //вес того ребра по которому мы можем
пойти
if (current_weight + w > best_weight) //есть более легкие пути
d[v]++; //ищем дальше по списку куда можно пойти
continue; //и дальше можно эту вершину не обсчитывать
int t; //нужна ли пересадка для попадания в следующую
//она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)
t = 1;
else
t = 0;
//есть более короткие пути
if (current_transfer + t > numericUpDownTransfer.Value)
d[v]++; //ищем дальше по списку куда можно пойти
continue; //и дальше можно эту вершину не обсчитывать
//идти в эту вершину
current_path.Push(vv); //положить в стек вершину
current_pathE.Push(e); //положить в стек ребро
//идти в эту вершину
//пересчитать показатели
current_transfer += t; //увеличим количество пересадок
current_weight += w; //увеличим стоимость пути
//пересчитать показатели
//и так как мы пошли в вершину, то у нас теперь другая текущая и цикл
нужно кончать
break;
if (v == current_path.Peek()) //если из вершины идти дальше некуда
if (v == s) current_path.Pop(); //делаем последний шаг назад
if (v == s) break; //именно последний шаг назад
int e; //по какому ребру дошли до этой вершины
//узна?м его по вершине стека, т.к. в стеке что-то точно есть
e = current_pathE.Peek();
int v1 = tn.aEdge[e].srcVertex; //начало ребра по которому пришли
int v2 = tn.aEdge[e].destVertex; //конец ребра по которому пришли
int t; //нужна ли была пересадка для попадания в эту вершину
//она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v1].iGraph != tn.aVertex[v2].iGraph)
t = 1;
else
t = 0;
int w = tn.aEdge[e].Weight; //вес ребра по которому мы пришли в эту
вершины
//пересчитать показатели
//уменьшить количество пересадок, т.к. мы собираемся делать шаг
назад
current_transfer -= t;
//уменьшить вес текущего пути, т.к. мы собираемся делать шаг назад
current_weight -= w;
//пересчитать показатели
//выйти из этой вершины
current_path.Pop(); //делаем шаг назад
current_pathE.Pop(); //делаем шаг назад
//выйти из этой вершины
//и так как мы из этой вершины ушли, то счетчик ребер для нее
обнуляется
d[v] = -1;
//если же мы не дошли ещ? до финальной вершины
//рекурсивный поиск в глубину
private void rdfs(int s, int v, int e, int finish)
//можно ли идти в эту вершину
if (current_path.Contains(v) == true) return; //мы в ней уже были
if (tn.aVertex[v].Enabled == false) return; //в нее идти нельзя
if (e != -1)
if (tn.aEdge[e].Enabled == false) return; //по этому ребру идти нельзя
//можно ли идти в эту вершину
//нужно ли идти в эту вершину
int w; //вес того ребра, по которому идем
if (e != -1)
w = tn.aEdge[e].Weight;
else
w = 0;
if (current_weight + w > best_weight) return; //есть более легкие пути
int t; //нужна ли пересадка
if (e != -1)
if (tn.aVertex[s].iGraph != tn.aVertex[v].iGraph)
t = 1;
else
t = 0;
else
t = 0;
if (current_transfer + t > numericUpDownTransfer.Value) //есть более
короткие пути
return;
//нужно ли идти в эту вершину
//идти в эту вершину
current_path.Push(v);
if (e != -1) current_pathE.Push(e);
//идти в эту вершину
//пересчитать показатели
current_transfer += t;
current_weight += w;
//пересчитать показатели
//если дошли
if (v == finish)
if (current_weight < best_weight)
best_weight = current_weight;
best_path = new Stack<int>(current_path);
best_pathE = new Stack<int>(current_pathE);
//если дошли
//идти из этой вершины во все остальные по очереди
foreach (int iE in tn.aVertex[v].iEdge)
int vv; //один из вариантов, куда можно пойти
if (tn.aEdge[iE].srcVertex == v)
vv = tn.aEdge[iE].destVertex;
else
vv = tn.aEdge[iE].srcVertex;
rdfs(v, vv, iE, finish);
//идти из этой вершины во все остальные по очереди
//пересчитать показатели
current_transfer -= t;
current_weight -= w;
//пересчитать показатели
//выйти из этой вершины
current_path.Pop();
if (e != -1) current_pathE.Pop();
//выйти из этой вершины
ПРИЛОЖЕНИЕ Ж
Функция поиска оптимального пути
private void buttonSearch_Click(object sender, EventArgs e)
int start=-1; //стартовая вершина
int finish=-1; //конечная вершина
//ищем стартовую и конечную вершину
for (int i = 0; i < tn.aVertex.Count; i++)
if (tn.aVertex[i].IsStart == true) start = i;
if (tn.aVertex[i].IsFinish == true) finish = i;
//если хотя бы одну не нашли
if (start == -1 || finish == -1)
//ошибка
MessageBox.Show(«Не указана начальная или конечная вершина!»,
«Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
//и выходим
return;
if (tn.aVertex[start].Enabled == false || tn.aVertex[finish].Enabled == false)
//ошибка
MessageBox.Show(«Начальная или конечная вершина заблокированы!»,
«Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
//и выходим
return;
//нужно снять отметку с старого пути
for (int i = 0; i < tn.aEdge.Count; i++)
tn.aEdge[i].IsPartOfPath = false;
//нужно снять отметку с старого пути
for (int i = 0; i < tn.aVertex.Count; i++)
tn.aVertex[i].IsPartOfPath = false;
best_path.Clear();
best_pathE.Clear();
best_weight = int.MaxValue;
current_path.Clear();
current_pathE.Clear();
current_weight = 0;
current_transfer = 0;
rdfs(-1, start, -1, finish);
//если не нашли путь
if (best_weight == int.MaxValue)
//ошибка
MessageBox.Show(«Путь до конечной вершины не может быть
найден!», «Ошибка», MessageBoxButtons.OK, MessageBoxIcon.Error);
//и выходим
return;
//теперь нужно пометить путь
while (best_pathE.Count != 0)
int i = best_pathE.Pop();
tn.aEdge[i].IsPartOfPath = true;
tn.aVertex[tn.aEdge[i].srcVertex].IsPartOfPath = true;
tn.aVertex[tn.aEdge[i].destVertex].IsPartOfPath = true;
//отрисовать
tn.Draw(checkBoxShowInvisible.Checked,
checkBoxShowDeleted.Checked);}
Размещено на
