3.4 Требования к программе

К разрабатываемому программному продукту предъявляется ряд требований:

- залогом успешного использования любого программного продукта является простой и понятный интерфейс – программный продукт должен иметь «дружественный» для пользователя интерфейс;

- основная информация о городах и расстояниях должна быть защищена от повреждения, удаления и несанкционированного изменения;

- программный продукт должен быть защищён от действий неопытного пользователя;

- программный продукт должен исполняться на windows платформах;

- должна быть обеспечена как автономная работа, так и возможность получения данных из сети интернет, с узла http://maps.google.ru/.

3.5 Требования к программной документации

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

3.6 Технико-экономические показатели

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

3.7 Стадии и этапы разработки

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

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

Уточнив все тонкости можно приступать к стадии создания рабочего проекта. На данной стадии происходит программирование оболочки-интерфейса программного продукта и функциональное тестирование.

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

3.8 Порядок контроля и приемки

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

Испытания, которым подвергается программный продукт, состоят из опытной эксплуатации и приёмочных испытаний.

Перед началом работ по контролю и приёмки программного продукта необходимо провести обучение эксплуатационного и оперативного персонала работе с программным продуктом.

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

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

Анализ предметной области и постановка задачи

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

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

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

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

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

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

Целью курсового проекта является создание автономной системы поиска кратчайшего пути в системе городов.

В связи с этим в проекте поставлены следующие ключевые задачи: 

- анализ и поиск оптимального алгоритма для поиска кротчайшего пути в системе городов;

- создание автономной системы поиска кратчайшего пути в системе городов;

- предусмотреть получение информации о расстояниях с интернет-узла maps.google.by;

- рассмотреть возможность дополнения и расширения системы городов.

Объектом темы данного дипломного проектирования являются города республики Беларусь и сеть дорого между ними.

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

Анализ предметной области

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

GPS-навигатор – устройство, которое получает сигналы глобальной системы позиционирования с целью определения текущего местоположения устройства на Земле. Устройства GPS обеспечивают информацию о широте и долготе, а некоторые могут также вычислить высоту. Общим недостатком использования любой радионавигационной системы является то, что при определённых условиях сигнал может не доходить до приёмника, или приходить со значительными искажениями или задержками. Например, практически невозможно определить своё точное местонахождение в глубине квартиры внутри железобетонного здания, в подвале или в тоннеле. Так как рабочая частота GPS лежит в дециметровом диапазоне радиоволн, уровень приёма сигнала от спутников может серьёзно ухудшиться под плотной листвой деревьев или из-за очень большой облачности. Нормальному приёму сигналов GPS могут повредить помехи от многих наземных радиоисточников, а также от магнитных бурь.

Наличие GPS навигатора не даёт стопроцентной уверенности, что именно в тот момент, когда появится необходимость поиска кратчайшего пути, будет получен сигнал от спутника. Поэтому нужна система, которая будет содержать информацию о точках (пунктах назначения) и расстоянии между ними. А так же, когда система глобального позиционирования не функционирует, но имеется доступ к сети Интернет – можно получать данные о расстояниях из этой сети, а конкретно с узла maps.google.by. Создаваемая система должна совмещать в себе эти типы автономной и полуавтономной работы.

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

Граф – это совокупность непустого множества вершин и множества пар вершин, либо связей между вершинами. Объекты представляются как вершины, или узлы графа, а связи – как дуги, или рёбра.

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

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

Алгори́тм Де́йкстры (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстром в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например: его использует протокол OSPF для устранения кольцевых маршрутов.

Алгоритм Беллмана - Форда – алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана - Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в1962 году Робертом Флойдом и Стивеном Уоршеллом.

Постановка задачи

В рамках данного дипломного проектирования были поставлены следующие задачи:

- анализ и поиск оптимального алгоритма для поиска кратчайшего пути в системе городов;

- создание автономной системы поиска кратчайшего пути в системе городов;

- рассмотреть возможность дополнения и расширения системы городов.

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

Каждой вершине из V сопоставим метку – минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

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

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