Программное средство нахождения кратчайших путей в графе. Курсовая работа (т). Информационное обеспечение, программирование.
⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Информационное обеспечение, программирование
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!
Похожие работы на - Программное средство нахождения кратчайших путей в графе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Нужна качественная работа без плагиата?
Не нашел материал для своей работы?
Поможем написать качественную работу Без плагиата!
Слушателю Политыко Марии Леонидовне
. Тема проекта: Программное средство нахождения
кратчайших путей в графе.
. Срок сдачи законченного проекта «13»июня 2014
г.
. Исходные данные по проекту: MS
Visual Studio
2010.
а) пояснительная записка: Введение. Постановка
задачи. 1. Системы транспортной логистики. 2. Построение модели. 3. Реализация
модели. Заключение.
б) графическая часть проекта (презентация 12
слайдов)
. Календарный график работы на весь период проектирования:
.02.2014-26.02.2014 - постановка задачи и анализ
предметной области;
.02.2014-27.03.2014 - построение модели;
.03.2014-13.06.2014 - реализация модели;
Задание принял к исполнению: 31.01.2014 г.
К курсовому проекту Иванова Сергея Дмитриевича,
слушателя группы 15ПО12-05з специальности 1-40 01 73 «Программное обеспечение
информационных систем» на тему «Программное средство нахождения кратчайших путей
в графе»
Ключевые слова: транспортная задача, алгоритм
дейкстры, задача коммивояжёра
Предметной областью курсового проектирования
является транспортная логистика.
Целью курсового проекта является создание
программного средства нахождения кратчайших путей в графе.
При выполнении курсового проектирования были
использованы среда визуального программирования MS Visual Studio 2008.
Пояснительная записка к курсовому проекту
включает три главы и заключение. Курсовая работа содержит 68 страниц, в том
числе 7 приложений.
. СИСТЕМЫ
ТРАНСПОРТНОЙ ЛОГИСТИКИ
.8 История
поиска методов решения
2.1 Основные
понятие и ограничения
2.2 Внутреннее
представление данных
.5 Списки
смежных вершин через списки
.6 Списки
смежных вершин через матрицы
.8 Модифицированная
структура данных
.9 Алгоритмы
поиска маршрутов в графе
3.2 Визуализация
транспортной сети
3.3 Редактирование
транспортной сети
.3.4 Загрузка
и сохранение транспортной сети
3.4.2 Поиск
в глубину (рекурсивная версия)
.4.3 Поиск
в глубину (нерекурсивная версия)
.4.4 Поиск
в ширину (однопоточная версия)
.4.5 Поиск
в ширину (многопоточная версия)
В настоящее время задачи транспортной логистики
представляют несомненный интерес, как с точки зрения практического
программирования, так и с точки зрения теоретической.
Это связано с несколькими причинами
Причина первая состоит в том, что в настоящее
время компьютерная техника имеется в наличии практически в любой организации и
естественным желанием этой организации является её использование «на сто
процентов», в частности и для оптимизации транспортных расходов.
Вторая причина состоит в том, что, не смотря на
то, что задача поиска кратчайшего пути в графе на текущий момент уже является
классической, её различные реализации могут значительным образом отличаться как
с точки зрения интерфейса и удобства использования, так и с точки зрения скорости
работы. Третья причина состоит в том, что классические постановки задачи,
связанные с поиском кратчайшего пути, подробно описанные в ряде трудов, решают
лишь общую задачу. И, если имеются некоторые априорные данные о предмете
исследования или наложены дополнительные ограничения, всегда может быть
построена некоторая модификация уже известного алгоритма, обладающая лучшими
характеристиками как с точки зрения использования оперативной памяти, так и с
точки зрения скорости работы.
В рамках данного курсового проекта будет
рассмотрено решение задачи поиска кратчайшего пути в транспортной сети,
состоящей из нескольких графов, где каждый граф может представлять собой
отдельный вид транспорта: автомобильный, железнодорожный, водный, воздушный. В
связи с тем, что каждый вид транспорта может обладать некоторыми уникальными
характеристиками, а процесс смены вида транспорта занимать дополнительное
время, эта формулировка задачи может представлять несомненный интерес не только
с точки зрения практического программирования, но и с точки зрения теории
графов.
Разработать программный комплекс, позволяющий
осуществлять поиск кратчайшего пути для перевозки груза внутри связанной
системы транспортных сетей, с возможностью задания дополнительных ограничений
согласно следующему плану:
. Разработать редактор связанной системы графов
позволяющий:
.1.1 Создавать, редактировать, удалять
.1.2 Выгружать на внешний носитель, загружать с
внешнего носителя
.2 Осуществлять работу с вершинами графа:
.2.1 Создавать, редактировать, удалять
.3 Осуществлять работу с рёбрами графа:
.3.1 Создавать, редактировать, удалять
. Разработать приложение, позволяющее
осуществлять поиск кратчайшего пути между заданной парой вершин согласно
следующим ограничениям:
.1 Количество пересадок (переходов от одного
графа к другому) ограничено.
.2 Отдельные элементы транспортной сети могут
быть заблокированы:
.3 Приоритет транспорта определённого вида.
Логистика - стратегическое управление
(менеджмент) материальными потоками в процессе закупки, снабжения, перевозки и
хранения материалов, деталей и готового инвентаря (техники и проч.). Понятие
включает в себя также управление соответствующими потоками информации, а также
финансовыми потоками.
Логистика направлена на оптимизацию издержек и
рационализацию процесса производства, сбыта и сопутствующего сервиса как в
рамках одного предприятия, так и для группы предприятий. В зависимости от
специфики деятельности компании применяются различные логистические системы.
Понятие логистики включает в себя множество
поддисциплин: закупочная, транспортная, складская, производственная,
информационная логистика и другие.
В рамках данного курсового проекта будет
рассматриваться транспортная логистика.
Транспортная логистика - это система по
организации доставки, а именно по перемещению каких-либо материальных
предметов, веществ и пр. из одной точки в другую по оптимальному маршруту. Одно
из основополагающих направлений науки об управлении информационными и
материальными потоками в процессе движения товаров.
Оптимальным считается маршрут, по которому
возможно доставить логистический объект, в кратчайшие сроки (или
предусмотренные сроки) с минимальными затратами, а также с минимальным вредом
для объекта доставки.
Вредом для объекта доставки считается негативное
воздействие на логистический объект как со стороны внешних факторов (условия
перевозки), так и со стороны временного фактора при доставке объектов,
подпадающих под данную категорию.
Перечислим основные задачи, которые стоят перед
транспортной логистикой:
. Выбор типа транспортного средства
. Выбор вида транспортного средства
. Совместное планирование транспортных процессов
со складскими и производственными операциями
. Совместное планирование транспортных процессов
на различных видах транспорта
. Обеспечение технологического единства
транспортно-складского процесса
. Определение рациональных маршрутов поставки
Все они (кроме подзадач связанных со складскими
операциями) будут затронуты в данном исследовании.
Исследование операций - дисциплина, занимающаяся
разработкой и применением методов нахождения оптимальных решений на основе
математического моделирования, статистического моделирования и различных
эвристических подходов в различных областях человеческой деятельности. Иногда
используется название математические методы исследования операций.
Когда мы говорим об оптимальности решения,
всегда необходимо определять набор признаков, по которым данное решение будет
предпочтительнее других. В свою очередь цель исследования операций -
предварительное количественное обоснование оптимальных решений.
Характерная особенность исследования операций -
системный подход к поставленной проблеме и анализ. Системный подход является
главным методологическим принципом исследования операций. Он заключается в
следующем. Любая задача, которая решается, должна рассматриваться с точки
зрения влияния на критерии функционирования системы в целом. Для исследования
операций характерно то, что при решении каждой проблемы могут возникать новые
задачи. Важной особенностью исследования операций есть стремление найти
оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на
практике такое решение найти невозможно по таким причинам:
. отсутствие методов, дающих возможность найти
глобально оптимальное решение задачи
. ограниченность существующих ресурсов (к
примеру, ограниченность машинного времени ЭВМ), что делает невозможным
реализацию точных методов оптимизации.
В таких случаях ограничиваются поиском не
оптимальных, а достаточно хороших, с точки зрения практики, решений. Приходится
искать компромисс между эффективностью решений и затратами на их поиск.
Исследование операций дает инструмент для поиска таких компромиссов.
Одной из самых известных задач транспортной
логистики является задача коммивояжёра.
Задача заключается в отыскании самого выгодного
маршрута, проходящего через указанные города хотя бы по одному разу с
последующим возвратом в исходный город. В условиях задачи указываются критерий
выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т.п.) и
соответствующие матрицы расстояний, стоимости и т.п. Как правило, указывается,
что маршрут должен проходить через каждый город только один раз - в таком
случае выбор осуществляется среди гамильтоновых циклов.
Существует несколько частных случаев общей
постановки задачи, в частности геометрическая задача коммивояжёра (также
называемая планарной или евклидовой, когда матрица расстояний отражает
расстояния между точками на плоскости), треугольная задача коммивояжёра (когда
на матрице стоимостей выполняется неравенство треугольника), симметричная и
асимметричная задачи коммивояжёра. Также существует обобщение задачи, так
называемая обобщённая задача коммивояжёра.
Общая постановка задачи, впрочем, как и
большинство её частных случаев, относится к классу NP-сложных задач.
Перечислим основные методы решения этой задачи:
o метод включения ближайшего города
o метод самого дешёвого включения
· метод минимального остовного дерева
Все эффективные (сокращающие полный перебор)
методы решения задачи коммивояжёра - методы эвристические. В большинстве
эвристических методов находится не самый эффективный маршрут, а приближённое
решение. Зачастую востребованы так называемые any-time алгоритмы, то есть
постепенно улучшающие некоторое текущее приближенное решение.
Существует также постановки, в которых задача
коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим
образом: существует ли на заданном графе G
такой обход, что его стоимость не превышает X.
Часто на ней проводят обкатку новых подходов к эвристическому сокращению
полного перебора.
На практике применяются различные модификации
более эффективных методов: метод ветвей и границ и метод генетических
алгоритмов, а также алгоритм муравьиной колонии.
В теории алгоритмов классом NP (от англ.
non-deterministic polynomial) называют множество алгоритмов, время работы
которых существенно зависит от размера входных данных. В то же время, если
предоставить алгоритму некоторые дополнительные сведения (так называемых
свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее
многочлена от размера данных) решить задачу.
Многие задачи на графах относят к классу
NP-полных задач.
Транспортная задача (Задача Монжа-Канторовича) -
задача об оптимальном плане перевозок продукта из пунктов отправления в пункты
потребления. Разработка и применение оптимальных схем грузовых потоков
позволяют снизить затраты на перевозки. Транспортная задача является по теории
сложности вычислений NP-сложной.
Когда суммарный объем предложений (грузов,
имеющихся в пунктах отправления) не равен общему объему спроса на товары
(грузы), запрашиваемые пунктами потребления, транспортная задача называется
несбалансированной.
Транспортная задача (классическая) - задача об
оптимальном плане перевозок однородного продукта из однородных пунктов наличия
в однородные пункты потребления на однородных транспортных средствах
(предопределённом количестве) со статичными данными и линеарном подходе (это
основные условия задачи).
Для классической транспортной задачи выделяют
два типа задач: критерий стоимости (достижение минимума затрат на перевозку)
или расстояний и критерий времени (затрачивается минимум времени на перевозку).
Проблема была впервые формализована французским
математиком Гаспаром Монжем в 1781. Основное продвижение было сделано на полях
во время Великой Отечественной войны советским математиком и экономистом
Леонидом Канторовичем. Поэтому иногда эта проблема называется Транспортной
задачей Монжа-Канторовича.
Классическую транспортную задачу можно решить
симплекс-методом, но есть и другие подходы.
Например, сначала ищется опорный план при помощи
одного из ниже перечисленных методов:
А уже затем при помощи теории графов ищется
оптимальный путь.
Рассматривается двудольный граф, в котором
пункты производства находятся в верхней доле, а пункты потребления - в нижней.
Пункты производства и потребления попарно соединяются рёбрами бесконечной
пропускной способности и цены за единицу потока C ij .
К верхней доле искусственно присоединяется
исток. Пропускная способность рёбер из истока в каждый пункт производства равна
запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.
Аналогично к нижней доле присоединяется сток.
Пропускная способность рёбер из каждого пункта потребления в сток равна
потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже
равна 0.
Дальше решается задача нахождения максимального
потока минимальной стоимости (mincost maxflow). Её решение аналогично
нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо
кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой
подзадаче используется не поиск в ширину, а алгоритм Беллмана-Форда. При
возврате потока стоимость считается отрицательной.
Алгоритм mincost maxflow можно запускать и сразу
- без нахождения опорного плана. Но в этом случае процесс решения будет
несколько более долгим. Выполнение алгоритма mincost maxflow происходит не
более чем за O(v 2 e 2 )
операций (e - количество
рёбер, v - количество
вершин.) При случайно подобранных данных обычно требуется гораздо меньше -
порядка O(ve)
операций.
Но, подобные постановки транспортной задачи и,
соответственно, методы их решения не лучшим образом в явном виде подходят для
проблематики, рассматриваемой в рамках курсового проекта, поскольку в них:
. Не рассматривается возможность наличия
нескольких транспортных сетей.
. Не формализуются затраты на пересадки между
транспортными сетями.
. На оптимальность маршрута влияет не только
стоимость перевозки, но и количество перевозимого груза.
. Формулировка задачи больше подходит для задач,
в которых происходят не разовые перевозки, а регулярные поставки и отгрузки
логистических единиц.
Всё это приводит к идее поиска решения задачи не
в рамках линейного программирования, а в области теории графов.
В математической теории графов и информатике граф
- это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы
графа, а связи - как дуги, или рёбра. Для разных областей применения виды
графов могут различаться направленностью, ограничениями на количество связей и
дополнительными данными о вершинах или рёбрах (1).
Граф или неориентированный граф G
- это упорядоченная пара G
= (V,E)
для которой выполнены следующие условия:
· V
это множество вершин или узлов,
· E
это множество пар (в случае неориентированного графа - неупорядоченных) вершин,
называемых рёбрами.
Будем считать, что в рамках решаемой задачи
будут рассматриваться только неориентированные графы, т.е. если между двумя
вершинами (A и B)
существует ребро, то путь от вершины A
к вершине B будет иметь такую
же стоимость что и путь от вершины B
к вершине A. Это ограничение
не является жёстким и может быть легко обойдено на уровне алгоритмов работы с
графом.
Граф не должен содержать кратных рёбер. Будем
считать, что пару вершин всегда связывает только единственное ребро. Это
ограничение также не является жёстким.
Граф не должен содержать петель, т.к. петля не
имеет смысла с точки зрения транспортной сети.
Граф не должен содержать изолированных вершин,
т.к из вершины всегда должно выходить хотя бы одно ребро.
Граф не обязательно должен быть связным, т.к.
поиск может осуществляться только внутри обособленной области связности.
Граф является взвешенным, т.е. каждое ребро
имеет определённый вес. В качестве весовых коэффициентов будут использоваться
целые неотрицательные числа. Вещественные числа не являются удобными в связи с
тем, что вещественные числа в машинном представлении всегда хранятся с потерей
точности, что затрудняет выполнение операции сравнения и приводит к
необходимости заведения специальной константы, определяющей точность
вычислений.
Отрицательные числа не будут использоваться по
тому, что отрицательная стоимость в рамках транспортной задачи не имеет смысла.
Допускается наличие ребра, имеющего нулевой вес,
в том случае если некоторая вершина одновременно принадлежит нескольким графам.
В этом случае, обыгрывается ситуация в которой некоторая узловая точка
одновременно принадлежит нескольким транспортным системам и смена вида
транспорта отнимает нулевое количество ресурсов.
Рисунок 1.1 - Пример случая ребра нулевой длины
2.2 Внутреннее представление данных
Проведём анализ способов внутреннего
представления графов (13) (14):
Матрица смежности - таблица, где как столбцы,
так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы
записывается число, определяющее наличие связи от вершины-строки к
вершине-столбцу (либо наоборот).
Несомненным плюсом этого способа представления
является возможность быстро отвечать на вопросы вида «А принадлежит ли ребро (i,j)
графу G?». Ещё одним
плюсом является возможность быстрого обновления графа. в случае вставки и
удаления рёбер.
Недостатком является требование к памяти -
квадрат количества вершин. Особенно ярко этот недостаток выражается при работе
с транспортными сетями, т.к. в этом случае матрица получается очень высокой
степени разреженности.
Каждая строка соответствует определённой вершине
графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой
строки с j-м столбцом матрицы
записывается:
· 1 в случае, если связь «выходит» из вершины,
· -1, если связь «входит» в вершину,
· 0 во всех остальных случаях (т.е.
если связь является петлёй или связь не инцидентна вершине).
Данный способ является самым ёмким и неудобным
для хранения, но облегчает нахождение циклов в графе.
2.5 Списки смежных вершин через
списки
Более эффективным способом представления
разреженных графов являются связанные списки, в которых хранятся инцидентные
соседи каждой вершины. Для работы со списками смежных вершин требуются
указатели, что уже усложняет решение задачи. Кроме того, не во всех языках
программирования есть такой инструмент как указатели, что может давать
дополнительные сложности при реализации этого способа хранения графа.
При работе со списками смежности становится
сложнее ответить на вопрос о принадлежности данного ребра (i,j)
графу, так как для этого необходимо просматривать соответствующий список, чтобы
найти подходящее ребро. Тем не менее, нередко совсем несложно построить алгоритмы
работы с графами, не прибегающие к таким запросам. В частности, возможен проход
по всем ребрам графа за один заход, используя обход в ширину или в глубину, и
обновление ребра в момент его посещения.
2.6 Списки смежных вершин через
матрицы
Списки смежности также можно реализовать через
матрицы, избегая, таким образом, работы с указателями. Мы можем представить
список массивом (или, что эквивалентно, строкой в матрице), введя счетчик k
числа элементов и помещая их в первые k
элементов массива. Теперь мы можем последовательно обойти элементы от первого к
последнему, просто увеличивая счетчик цикла, а не путешествуя по указателям.
На первый взгляд, кажется, что эта структура
данных объединила в себе худшие черты матриц смежности (большой размер) и
списков смежности (необходимость поиска ребер). Тем не менее, существуют и
плюсы. Во-первых, эту структуру данных проще всего запрограммировать, особенно,
если речь идет о статичных графах, неизменных после построения. Во-вторых,
проблему с размером можно решить, если выделять строки для каждой вершины
динамически и делать их соответствующего размера.
Еще более простой структурой данных будет массив
или связанный список ребер. Работая с ней, сложнее отвечать на такие вопросы,
как: «Какие вершины являются соседними для 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 Алгоритмы поиска маршрутов в
графе
Базовой операцией в любом графовом алгоритме
является полный и систематический обход графа. Целью обхода - посетить каждую
вершину и каждое ребро ровно один раз в строго определенном порядке. Су
Похожие работы на - Программное средство нахождения кратчайших путей в графе Курсовая работа (т). Информационное обеспечение, программирование.
Реферат по теме История Российских привилегий и патентов
Эссе Общение В Моей Профессии
Герой Великой Отечественной Войны Реферат
Контрольная работа: Сили цивільної оборони
Сочинение: Анализ стихотворения Н. Некрасова Родина.
Мини Футбол Реферат Кратко
Дипломная работа: Учетная политика организации: принципы формирования и раскрытия. Скачать бесплатно и без регистрации
Сочинение Повествование Примеры
Лабораторная работа: Разработка операционного бюджета предприятия
Реферат по теме Желчнокаменная болезнь
Курсовая работа по теме Организация размещения государственных заказов на лекарственные средства и медицинское оборудование на материалах ГЛПУЗ 'Челябинской областной детской клинической больницы'
Дипломная работа по теме Проект залізничного залізобетонного моста
Реферат: Черкизово. Скачать бесплатно и без регистрации
Реферат: Hamlet Didn
Итоги Практической Работы
Вибрационная Болезнь Профессиональные Болезни Реферат
Реферат: Методика проведения АВС анализа
Итоговое Сочинение 2022 При Поступлении
Курсовая работа по теме Анализ финансово-экономических показателей на предприятии ООО УМТС 'Сплав'
Помогите Составить Сочинение Мой Родной Край
Реферат: Методы коммутации в сетях ПД
Реферат: Genetic Engineering Gene Therapy Essay Research
Сочинение: Эволюция философских взглядов Л.Н. Толстого