программа логистика транспортный алгоритм
3.5
Пример работы алгоритма
Рассмотрим
небольшой пример. Пусть необходимо найти путь из вершины A в вершину H. При
двух разрешённых пересадках оптимальный путь состоит из четырёх рёбер и имеет
вес равный 13. При трёх разрешённых пересадках оптимальный путь состоит из
одиннадцати рёбер и имеет вес равный 11.
Заключение
В ходе работы была спроектирована и разработана вычислительная система для решения задач транспортной логистики. В результате проведённого исследования было разработано четыре модифицированных алгоритма поиска оптимального маршрута в транспортной сети с возможностью задания широкого спектра дополнительных условий и ограничений.
В результате проведённого анализа наиболее заслуживающими внимания с точки зрения практического использования были признаны: нерекурсивный поиск в глубину и многопоточный поиск ширину. Первый из них менее требователен к оперативной памяти и ориентирован на исполнение в системах, базирующихся на процессоре с одним ядром. Второй имеет большие требования к оперативной памяти, но за счёт использования многопоточности может быть более быстродействующим в системах, базирующихся на многоядерных процессорах.
Так же была разработана собственная модель для внутреннего представления транспортной сети.
В качестве среды разработки был выбран пакет Visual Studio 2008. Реализация велась с использованием языка программирования высокого уровня C#. Для хранения транспортной сети использовались принципы сериализации объектов и формат XML. Были выявлены отличительные особенности и положительные стороны данной среды программирования.
На основе разработанного модифицированного алгоритма и модели внутреннего представления данных был создан программный комплекс, обладающий следующими возможностями:
. Создание, модификация, загрузка, сохранение транспортной сети.
. Визуализация транспортной сети с возможностью с возможностью временного сокрытия отдельных её частей.
. Задание условий поиска и критериев оптимальности поиска маршрута.
Одним
из дальнейших направлений развития данной работы может быть более подробное исследование
многопоточной версии алгоритма поиска в ширину и определения такого
максимального количества работающих параллельных потоков, которое бы
обеспечивало и высокую скорость работы и не допускало бы пробуксовки.
Список
используемых источников и литературы
1. Задачи по программированию. / С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. - Москва: Наука, 1988. - 234 с.
. Вентцель, С.Е. Исследование операций: задачи, принципы, методология. / С.Е. Вентцель. - Москва.: Наука, 1980. - 304 с.
. Вирт, Н. Алгоритмы и структуры данных. / Н. Вирт. - Москва: Мир, 1989. - 340 с.
. Демидович, Е.М. Основы алгоритмизации и программирования. Язык СИ. / Е.М. Демидович. - Мосвка: “Бестпринт” 2003. - 403 с.
. Дейтл, Х. C#. / Х. Дейтл. - Санкт Петербург.: БХВ-Петербург, 2006.- 542 с.
. Лекции по теории графов. / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - Москва: Наука, 1990. - 674 с.
. Кормен, М.Т. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ. - Москва: «Вильямс», 2006. - 345 с.
. Кнут, Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. / Д.Э. Кнут. - Москва: ООО «И.Д. Вильямс», 2007. - 832с.
. Культин, Н.Б. Microsoft Visual C# в задачах и примерах. / Н.Б. Культин. - Санкт Петербург: БХВ-Петербург, 2009. - 289 с.
. Лахатин, А.С. Языки программирования. Учеб. пособие. / А.С. Лахатин, Л.Ю. Искакова. - Екатеринбург, 1998. - 548 с.: ил.
. Левитин, А.В. Алгоритмы: введение в разработку и анализ. / А.В. Левитин. - Москва: «Вильямс», 2006. - 430 с.
. Меньшиков, Ф. Олимпиадные задачи по программированию. / Ф. Меньшиков. - Санкт Петербург.: «Питер», 2006. - 386 с.
. Мудров, В.И. Задача о коммивояжере. / В.И. Мудров. - Москва: «Знание», 1969. - 254 с.
Муртаф, Б. Современное линейное программирование. / Б. Муртаф. - Москва: Мир, 1984. - 630 с.
. C# 2005 и платформа.NET 3.0 для профессионалов. / К. Нейгл, Б. Ивьен, Д. Глинн и др. - Москва: ООО "И.Д. Вильямс", 2008. - 765 с.
. Оре, О. Теория графов. / О. Оре. - Москва: Наука, 1968. - 380 с.
. Павловская, Т.А. C#. Программирование на языке высокого уровня. / Т.А. Павловская. - Санкт Петербург: «Питер», 2007. - 544 с.
. Поляков, А. Программирование на языке Си. / А. Поляков. - Москва: Наука,. 2012. - 460 с.
. Сербин, Д.В. Основы логистики. / Д.В. Сербин. - Таганрог: ТРТУ, 2004. - 420 с.
. Сток, Р.Д. Стратегическое управление логистикой. / Р.Д. Сток. - Москва: Инфра-М, 2005. - 512 с.
. Стивен, С. Олимпиадные задачи по программированию. / С. Стивен, М.А. Скиена. - Москва: ИД Кудиц-образ, 2005. - 340 с.
. Стэкер, М.А. Разработка клиентских Windows-приложений на платформе Microsoft.NET Framework. / М.А. Стэкер, С.Д. Стэйн, Т. Нортроп. - Санкт Петербург: «Питер», 2008. - 580 с.
. Таха, Х.А. Введение в исследование операций. / Х.А. Таха. - Москва: «Вильямс», 2007. - 374 с.
. Уилсон, Р. Введение в теорию графов. Пер с англ. / Р. Уилсон. - Москва: Мир, 1977. - 286 с.
. Уэйт, М. Язык С. Руководство для начинающих. / М. Уэйт, С. Прага, Д. Мартин. - Москва: Мир, 1995. - 521с.: ил.
. Харари, Ф. Теория графов / Ф. Харари. - Москва: Мир, 1973. - 420 с.
27. Богатырев, А. Язык программирования С [Электронный ресурс] / А. Богатырев.- электр. дан. - Режим доступа: http://www.refby.com. - Загл. с экрана.