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

- из стека вершин текущего маршрута извлекается верхняя вершина;

- из стека рёбер текущего маршрута извлекается верхнее ребро;

- вес текущего маршрута уменьшается на вес извлечённого ребра;

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

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

вершина, в которую попадает ребро, добавляется в стек вершин и становится текущей;

ребро добавляется в стек, в котором хранится текущий маршрут;

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

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

- из стека вершин текущего маршрута извлекается верхняя вершина;

- из стека рёбер текущего маршрута извлекается верхнее ребро;

- вес текущего маршрута уменьшается на вес извлечённого ребра;

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

1. отказаться от рекурсии (что и было сделано в рамках данного алгоритма);

2. использование избыточных данных, позволяющих хранить уже рассчитанные значения (что и было сделано во всех предложенных алгоритмах);

3. использование многопоточных алгоритмов, рассчитанных на выполнение на многоядерных процессорах (что и будет сделано в следующих разделах).

Поиск в ширину (однопоточная версия)

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

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

Как и раньше текущий путь будет размещаться в структуре данных типа стек. Туда помещается стартовая вершина.

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

На самом деле будет использовать 4 очереди.

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

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

В третьей очереди будут храниться веса потенциальных маршрутов.

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

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

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

1. Из начала очереди маршрутов из вершин извлекается маршрут и делается текущим.

2. Из начала очереди маршрутов из рёбер извлекается маршрут и делается текущим.

3. Из начала очереди весов извлекается вес текущего маршрута. 4. Из начала очереди количества пересадок извлекается текущее количество пересадок.

5. Извлекаем с вершины стека вершин текущего маршрута вершину и делаем её текущей.

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

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

a. в стек вершин добавляется конечная вершина ребра;

b. в стек рёбер добавляется ребро;

c. пересчитывается текущий вес за счёт прибавления веса ребра, по которому осуществляется переход;

d. пересчитывается текущее количество пересадок, в соответствии с ребром по которому осуществляется переход;

e. копия стека вершин помещается в конец очереди стеков вершин;

f. копия стека рёбер помещается в конец очереди стеков рёбер; g. вес текущего пути помещается в конец очереди весов; h. количество пересадок текущего пути помещается в конец очереди количества пересадок;

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

Поиск в ширину (многопоточная версия)

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

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

2. Заводится вспомогательная структура данных хранящая в себе полный набор параметров необходимых для алгоритма. Это делается в силу того, что функции-делегату представляющей собой тело потока может быть передан только один параметр типа object. В состав структуры входят следующие поля:

a. текущая вершина; b. конечная вершина; c. текущий вес;

d. текущее количество пересадок;

e. стек вершин, входящих в текущий путь; f. стек рёбер, входящих в текущий путь.

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

Рассмотрим сам алгоритм:

1. Увеличивается количество активных потоков.

2. В локальный стек вершин помещается текущая вершина.

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

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

a. формируется копия текущего стека вершин; b. формируется копия текущего стека рёбер;

c. формируется копия веса текущего пути;

d. формируется копия количества пересадок на текущем пути;

e. в копию стека вершин помещается конец ребра, по которому мы хотим идти;

f. в копию сетка рёбер помещается рёбро, по которому мы хотим идти;

g. копия веса текущего пути увеличивается на вес ребра, по которому мы хотим пойти;

h. копия количества пересадок на текущем пути, если ребро ведёт в другую транспортную сеть;

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

программа логистика транспортный алгоритм

3.5 Пример работы алгоритма

Рассмотрим небольшой пример. Пусть необходимо найти путь из вершины A в вершину H. При двух разрешённых пересадках оптимальный путь состоит из четырёх рёбер и имеет вес равный 13. При трёх разрешённых пересадках оптимальный путь состоит из одиннадцати рёбер и имеет вес равный 11.

Заключение

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

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

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

В качестве среды разработки был выбран пакет Visual Studio 2008. Реализация велась с использованием языка программирования высокого уровня C#. Для хранения транспортной сети использовались принципы сериализации объектов и формат XML. Были выявлены отличительные особенности и положительные стороны данной среды программирования.

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

1. Создание, модификация, загрузка, сохранение транспортной сети.

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

3. Задание условий поиска и критериев оптимальности поиска маршрута.

4. Осуществление поиска маршрутов с учётом заданных ограничений.

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

Список используемых источников и литературы

1. Задачи по программированию. / С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. - Москва: Наука, 1988. - 234 с.

2. Вентцель, С.Е. Исследование операций: задачи, принципы, методология. / С.Е. Вентцель. - Москва.: Наука, 1980. - 304 с.

3. Вирт, Н. Алгоритмы и структуры данных. / Н. Вирт. -- Москва: Мир, 1989. - 340 с.

4. Демидович, Е.М. Основы алгоритмизации и программирования. Язык СИ. / Е.М. Демидович. - Мосвка: “Бестпринт” 2003. - 403 с.

5. Дейтл, Х. C#. / Х. Дейтл. - Санкт Петербург.: БХВ-Петербург, 2006.- 542 с.

6. Лекции по теории графов. / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - Москва: Наука, 1990. - 674 с.

7. Кормен, М.Т. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ. - Москва: «Вильямс», 2006. - 345 с.

8. Кнут, Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. / Д.Э. Кнут. - Москва: ООО «И.Д. Вильямс», 2007. - 832с.

9. Культин, Н.Б. Microsoft Visual C# в задачах и примерах. / Н.Б. Культин. - Санкт Петербург: БХВ-Петербург, 2009. - 289 с.

10. Лахатин, А.С. Языки программирования. Учеб. пособие. / А.С. Лахатин, Л.Ю. Искакова. - Екатеринбург, 1998. - 548 с.: ил.

11. Левитин, А.В. Алгоритмы: введение в разработку и анализ. / А.В. Левитин. - Москва: «Вильямс», 2006. - 430 с.

12. Меньшиков, Ф. Олимпиадные задачи по программированию. / Ф. Меньшиков. - Санкт Петербург.: «Питер», 2006. - 386 с.

13. Мудров, В.И. Задача о коммивояжере. / В.И. Мудров. - Москва: «Знание», 1969. - 254 с.

14 Муртаф, Б. Современное линейное программирование. / Б. Муртаф. - Москва: Мир, 1984. - 630 с.

15. C# 2005 и платформа.NET 3.0 для профессионалов. / К. Нейгл, Б. Ивьен, Д. Глинн и др. - Москва: ООО "И.Д. Вильямс", 2008. - 765 с.

16. Оре, О. Теория графов. / О. Оре. - Москва: Наука, 1968. - 380 с.

17. Павловская, Т.А. C#. Программирование на языке высокого уровня. / Т.А. Павловская. - Санкт Петербург: «Питер», 2007. - 544 с.

18. Поляков, А. Программирование на языке Си. / А. Поляков. - Москва: Наука,. 2012. - 460 с.

19. Сербин, Д.В. Основы логистики. / Д.В. Сербин. - Таганрог: ТРТУ, 2004. - 420 с.

20. Сток, Р.Д. Стратегическое управление логистикой. / Р.Д. Сток. - Москва: Инфра-М, 2005. - 512 с.

21. Стивен, С. Олимпиадные задачи по программированию. / С. Стивен, М.А. Скиена. - Москва: ИД Кудиц-образ, 2005. - 340 с.

22. Стэкер, М.А. Разработка клиентских Windows-приложений на платформе Microsoft.NET Framework. / М.А. Стэкер, С.Д. Стэйн, Т. Нортроп. - Санкт Петербург: «Питер», 2008. - 580 с.

23. Таха, Х.А. Введение в исследование операций. / Х.А. Таха. - Москва: «Вильямс», 2007. - 374 с.

24. Уилсон, Р. Введение в теорию графов. Пер с англ. / Р. Уилсон. - Москва: Мир, 1977. - 286 с.

25. Уэйт, М. Язык С. Руководство для начинающих. / М. Уэйт, С. Прага, Д. Мартин. - Москва: Мир, 1995. - 521с.: ил.

26. Харари, Ф. Теория графов / Ф. Харари. - Москва: Мир, 1973. - 420 с.

27. Богатырев, А. Язык программирования С [Электронный ресурс] / А. Богатырев.- электр. дан. - Режим доступа: http://www.refby.com. - Загл. с экрана.

Размещено на Allbest.ru