Нахождение кратчайшего пути между городами Минской области
ЧАСТНОЕ Учреждение образования
«КОЛЛЕДЖ БИЗНЕСА И ПРАВА»
Программа
автоматизации расчета
Пояснительная записка
КП Т.992016.401
Выполнил Н.О. Пархимчик
Руководители практики Н.В. Ржеутская
2012
Содержание
1 Объектно-ориентированный анализ и проектирование системы 3
- Сущность задачи 3
- Проектирование модели 5
2 Вычислительная система 8
2.1 Требования к аппаратным и операционным ресурсам 8
2.2 Инструменты разработки 8
3 Проектирование задачи 11
3.1 Требования к приложению 11
3.2 Концептуальный прототип 11
3.3 Организация данных 12
3.4 Функции и элементы управления 12
3.5 Проектирование справочной системы приложения 17
4 Описание программного средства 19
4.1 Общие сведения 19
4.2 Функциональное назначение 19
4.3 Входные данные 19
4.4 Выходные данные 19
5 Методика испытаний 20
5.1 Технические требования 20
5.2 Порядок проведения испытаний 20
5.2.1 Функциональное тестирование 20
5.2.2 Полное тестирование 26
6 Применение 39
6.1 Назначение программы 39
6.2 Условия применения 39
6.3 Справочная система 39
Заключение 45
Литература 46
Приложение А 47
1 Объектно-ориентированный анализ и проектирование системы
1.1 Сущность задачи
Задачей данного проекта является автоматизация расчета кратчайшего расстояния между городами Минской области. Программное приложение должно выводить сведения об оптимальном пути маршрута.
В Минской области осуществляется автобусное сообщение между следующими городами:
- Минск;
- Березино;
- Борисов;
- Вилейка;
- Воложин;
- Дзержинск;
- Жодино;
- Клецк;
- Копыль;
- Крупки;
- Логойск;
- Любань;
- Марьина Горка;
- Молодечно;
- Мядель;
- Нарочь;
- Несвиж;
- Плещеницы;
- Пуховичи;
- Слуцк;
- Смолевичи;
- Солигорск;
- Ст. Дороги;
- Столбцы;
- Узда;
- Червень.
Исходя из исследования предметной области, основной задачей, подлежащей автоматизации, будут являться нахождение кратчайшего расстояние между городами, для которых существует автобусное сообщение.
В настоящее время существуют аналогичные программы, такие как: «MinskCityInfo». Однако в данной программе возможно нахождение кратчайшего пути только в пределах города Минска. Разрабатываемый же продукт, будет оптимизировать расстояния между городами Минской области.
«MinskCityInfo» обладает рядом достоинств. С помощью данной программы, можно узнавать номера и виды транспортных средств наиболее подходящих для прохождения из начальной выбранной точки в пункт назначения. Но все-таки основная функция этого приложения – карта Минска.
Однако в «MinskCityInfo» возможно нахождение кратчайшего пути только в пределах города Минска. Разрабатываемый же продукт, будет оптимизировать расстояния между городами Минской области.
Учитывая достоинства и недостатки конкурирующего проекта, можно сказать, что разработка программы, решающей подобную задачу, будет достаточно востребована для пользователей, нуждающихся в информации о необходимом им маршруте.
1.2 Проектирование модели
Цель моделирования данных
состоит в обеспечении
Наиболее распространенным средством моделирования данных являются диаграммы «сущность-связь» (ERD). С их помощью определяются важные для предметной области объекты (сущности), их свойства (атрибуты) и отношения друг с другом (связи). ERD непосредственно используются для проектирования реляционных баз данных. Нотация ERD была впервые введена П. Ченном и получила дальнейшее развитие в работах Баркера. Диаграмма «сущность-связь» представлена на рисунке 1.
Рисунок 1 – Диаграмма «сущность-связь»
Исходя из исследования предметной области, можно выделить следующие сущности разработки: пользователь, место отправления, пункт назначения, список городов .
Для сущности «Место отправления» можно выделить следующие атрибуты:
- название;
- расстояние от ближайших городов.
Для сущности «Пункт назначения» атрибутами будут являться:
- название;
- расстояние от ближайших городов.
Для сущностей «Пользователь» и «Список городов» явных атрибутов выделить нельзя.
Суть диаграммы вариантов
использования состоит в том,
что проектируемая система
Варианты использования
описывают не только взаимодействия
между пользователями и сущностью,
но также реакции сущности на получение
отдельных сообщений от пользователей
и восприятие этих сообщений за пределами
сущности. Варианты использования могут
включать в себя описание особенностей
способов реализации сервиса и различных
исключительных ситуаций, таких как
корректная обработка ошибок системы.
Множество вариантов
Актёр представляет собой внешнюю по отношению к моделируемой системе сущность, которая взаимодействует с системой и использует её функциональные возможности для достижения определённых целей или решения частных задач. При этом актёры служат для обозначения согласованного множества ролей, которые могут играть пользователи в процессе взаимодействия с проектируемой системой. Каждый актёр может рассматриваться как некоторая отдельная роль относительно конкретного варианта использования.
Диаграмма вариантов использования представлена в графической части на листе 1.
Данный программный продукт имеет следующие основные функции:
- сохранить данные об оптимальном маршруте в файл;
- работа со списком населенных пунктов, который включает в себя поиск населенного пункта по названию и сортировку списка населенных пунктов по различным критериям;
- выбор населенных пунктов, который включает в себя выбор места отправления и выбор места назначения;
- оптимизация маршрута, которая включает в себя получение данных об оптимальном маршруте и получение данных об альтернативном маршруте.
К вспомогательным функциям,
расширяющим возможности
- перечень городов, для которых существует автобусное сообщение;
- расстояние между городами.
Диаграмма классов служит
для представления статической
структуры модели системы в терминологии
классов объектно-
Диаграмма классов для проектируемой системы представлена в графической части на листе 2.
При моделировании
поведения проектируемой или
анализируемой системы
Основная цель использования диаграмм деятельности - визуализация особенностей реализации операций классов, когда необходимо представить алгоритмы их выполнения.
Диаграмма деятельности для функций программы представлена в графической части на листинге 3.
Для моделирования взаимодействия объектов в UML используются соответствующие диаграммы взаимодействия. Если рассматривать взаимодействия объектов во времени, тогда для представления временных особенностей передачи и приема сообщений между объектами используется диаграмма последовательности.
Временной аспект поведения имеет существенное значение при моделировании синхронных процессов, описывающих взаимодействия объектов. Именно для этой цели и используются диаграммы последовательности, в которых ключевым моментом является динамика взаимодействия объектов во времени. При этом диаграмма последовательности имеет как бы два измерения: одно - слева направо в виде вертикальных линий, каждая из которых изображает линию жизни отдельного объекта, участвующего во взаимодействии; второе - вертикальная временная ось, направленная сверху вниз, на которой начальному моменту времени соответствует самая верхняя часть диаграммы.
Диаграмма последовательности для проектируемой системы представлена в графической части на листе 4.
Рассмотренные ранее диаграммы отражали концептуальные аспекты построения модели системы и относились к логическому уровню представления. Особенность логического представления заключается в том, что оно оперирует понятиями, которые не имеют самостоятельного материального воплощения. Другими словами, различные элементы логического представления, такие как классы, ассоциации, состояния, сообщения, не существуют материально или физически. Они лишь отражают наше понимание структуры физической системы или аспекты ее поведения.
Основное назначение логического представления состоит в анализе структурных и функциональных отношений между элементами модели системы. Однако для создания конкретной физической системы необходимо некоторым образом реализовать все элементы логического представления в конкретные материальные сущности. Для описания таких реальных сущностей предназначен другой аспект модельного представления, а именно физическое представление модели.
Диаграмма компонентов описывает объекты реального мира - компоненты программного обеспечения. Эта диаграмма позволяет определить архитектуру разрабатываемой системы, установив зависимости между программными компонентами.
Вид диаграммы компонентов для
данной проектируемой системы
2 Вычислительная система
2.1 Требования к аппаратным и операционным ресурсам
Минимальные системные требования для данного приложения представлены в таблице 2.
Таблица 2 - Минимальные системные требования
Элементы конфигурации |
Описание характеристик |
Процессор |
Тактовая частота 1GHz |
Оперативная память |
Объём 256 mb |
Видео адаптер |
Объём памяти 16 mb |
Дисковое пространство |
Объём 100 mb |
Клавиатура |
Совместимая с персональным компьютером |
Мышь |
Совместимая с персональным компьютером |
Монитор |
Диагональ 15" |
Операционная система |
Windows XP Service Pack 2 |
2.2 Инструменты разработки
Программное приложение будет
функционировать под
Инструментами разработки будут являться:
- среда Visual Studio 2008;
- язык программирования C#;
- среда проектирование Rational Rose
Среда разработки Microsoft Visual Studio — это набор инструментов и средств, предназначенных для помощи разработчикам программ любого уровня квалификации в решении сложных задач и создания новаторских решений. Разработчикам программного обеспечения часто приходится решать ряд проблем, чтобы создавать удачные программы. Роль Visual Studio заключается в том, чтобы улучшить процесс разработки и упростить разработку высокоэффективных программ.
Средства Visual Studio позволяют разработчикам работать с большей отдачей и затрачивать меньше усилий на повторяющиеся задачи. Следует отметить высокопроизводительные редакторы кода, поддержку технологии IntelliSense, мастеров и различных языков кодирования в одной интегрированной среде разработки (IDE), а также продукты управления жизненным циклом приложений (ALM) в Microsoft® Visual Studio® Team System. В новых версиях Visual Studio постоянно появляются новые средства, позволяющие разработчикам сосредоточиться на решении основных проблем, а не на рутинной работе.
Разработчики, применяющие Visual Studio, получают в свое распоряжение интегрированный продукт, включающий инструменты, серверы и службы. Продукты Visual Studio отлично работают вместе — не только один с другим, но и с прочими программами Майкрософт, включая серверные продукты и приложения Microsoft Office.
В Visual Studio содержатся инструменты для всех этапов разработки программного обеспечения (разработка, тестирование, развертывание, интеграция и управления) и для разработчиков любого уровня квалификации, от новичков до опытных специалистов. Visual Studio поддерживает разработку для различных типов устройств — ПК, серверов, сетевых и мобильных устройств.
Visual Studio разрабатывается таким образом, чтобы обеспечить высокую надежность и совместимость. Visual Studio обладает удачным сочетанием безопасности, масштабируемости и взаимодействия. В Visual Studio всегда поддерживаются новейшие технологии, но везде, где это возможно, обеспечивается обратная совместимость.[8]
C# – элегантный, строго
типизированный объектно-
Как объектно-ориентированный язык, C# поддерживает понятия инкапсуляции, наследования и полиморфизма. Все переменные и методы, включая метод Main – точку входа приложения – инкапсулируются в определения классов. Класс может наследовать непосредственно из одного родительного класса, но может реализовывать любое число интерфейсов. Для методов, которые переопределяют виртуальные методы в родительском классе, необходимо ключевое слово override, чтобы исключить случайное повторное определение. В языке C# структура похожа на облегченный класс: это тип, распределяемый по стопкам, реализующий интерфейсы, но не поддерживающий наследование.
В дополнение к основным
описанным объектно-
- инкапсулированные подписи методов, называемые делегатами, которые поддерживают строго-типизированные уведомления о событиях;
- свойства, выступающие в роли методов доступа для закрытых переменных-членов;
- атрибуты с декларативными метаданными о типах во время выполнения;
- встроенные комментарии XML-документации.[8]
Ни одна из методологий
разработки программ не обходится без
некоторого инструмента. Разработка
крупных программных систем в
современных условиях невозможна без
использования средств
Из основных возможностей можно перечислить следующие:
- мощный графический язык моделирования предметной области, обладающий высоким уровнем формализации и поддерживающий объектно-ориентированную методологию.
- удобная навигация между элементами модели при помощи «инспектора» проекта;
- хранение результатов проектирования в виде единой модели;
- поддержка работы над проектом группы разработчиков;
- мощная система подготовки отчетов и документации о проекте;
- возможности синтеза программ практически на всех современных объектно-ориентированных языках;
- поддержка компонентных технологий построения программных систем;
- широкие возможности по проектированию ПО различной архитектуры, от простых программ, до крупных «клиент-серверных» систем и Интернет-приложений;
- возможность реинженеринга модели на основе исходных текстов программы. Этим обеспечивается поддержание единства проектной информации и реализации;
- настройка и расширение функциональных возможностей CASE среды путем установки модулей расширения, в первую очередь для поддержки различных языков программирования.[9]
3 Проектирование задачи
3.1 Требования к приложению
Программное средство должно выполнять все основные функции, определённые на диаграмме вариантов использования:
- оптимизировать маршрут;
- сохранение маршрута в файл с расширением .txt;
- поиск города.
Графический интерфейс должен быть простым, интуитивно понятным и дружелюбным.
Средства защиты программы зависят от самого пользователя, он сам выбирает каталог для сохранения файла, и сам, используя возможности операционной системы, устанавливает защиту файла. Данные же самой программы защищать незачем, ибо они не несут и не могут нести никакой материальной ценности.
3.2 Концептуальный прототип
Концептуальный прототип состоит из описания внешнего пользовательского интерфейса, а именно, элементов управления.
При создании данного приложения важную роль играют формы, так как они являются основным диалоговым средством работы пользователя. Разрабатываемое приложение будет содержать несколько форм: две основные формы и пять дополнительных. Такая структура интерфейса позволит классифицировать основные функции программы по группам.
При проектировании концептуального прототипа были разработаны следующие формы:
- «Оптимизация маршрута»;
- «О программе».
На форме «Оптимизация маршрута» находится:
- компонент MenuStrip1 для удобства работы;
- компонент SaveFileDialog1 для сохранения в текстовый файл маршрута файл;
- компонент CheckedListBox1 для выбора города отправления;
- компонент CheckedListBox2 для выбора города прибытия;
- компонент CheckedListBox3 для выбора города проезда;
- компоненты Label1, Label2 и Label3 для дополнительной информации;
- компоненты Button1, Button2 и Button3 для выбора пункта назначения, города проезда и отправления соответственно;
- компонент Button6 перехода к выбору города на карте;
- компонент Button5 для нахождения кратчайшего маршрута;
- компонент Button4 для поиска города;
- компонент RadioButton1 для выбора поиска по городам отправления;
- компонент RadioButton2 для выбора поиска по городам прибытия;
- компонент RadioButton3 для выбора поиска по городам проезда;
- компонент TextBox2 для введения данных для поиска;
- компонент Button5 для нахождения кратчайшего пути;
- компонент TextBox1 для вывода кратчайшего маршрута;
- компонент TextBox1 для вывода кратчайшего расстояния.
На форме «О программе» находится:
- компоненты Label1-Label9 для получения информации о программе разработчике, а так же контакты с разработчиком;
- компонент LinkLabel2 и LinkLabel1 для вывода адресов сайтов.
- компонент Button2 для сохранения информации в файл.
На форме «Карта» находится:
- компонент PictureBox1 для вывода изображения карты;
- компоненты CheckBox1 – CheckBox25 для выбора городов;
- компонент СontextMenuStrip1 для подтверждения выбора городов.
3.3 Организация данных
Организация данных подразумевает создание модели данных, главными элементами которой являются сущности и их связи.
В разделе 2.2 на рисунке 1 представлена схема «Сущность-связь», на которой отображены главные сущности задачи: «Место отправления», «Пункт назначения», «Пользователь», «Список городов».
В текстовом файле будет храниться последовательность городов, через которые необходимо следовать, чтобы добиться кратчайшего маршрута следования, а так же наименьшее расстояние между двумя городами. Доступ к этим файлам могут осуществлять любые пользователи, не зависимо вы его создали или нет.
3.4 Функции и элементы управления
При нажатии клавиши «Найти кратчайший путь», использую алгоритм поиска кратчайшего пути на графах Флойда, программный продукт определяет кратчайший путь следования и его расстояние, и выводит в соответствующую строку пути и его расстояние. Далее, пожеланию, пользователь может сохранить данные в файл.
Программный код реализации данных функции представлен ниже.
class Optimization
{
int[,] D = new int[30, 30]
//1
{{0,9999,9999,9999,9999,9999,
//2
{9999,0,86,9999,9999,9999,69,
//3
{9999,86,0,9999,9999,9999,20,
//4
{9999,9999,99999,0,9999,9999,
//5
{9999,9999,9999,9999,0,9999,
//6
{9999,9999,9999,9999,9999,0,
//7
{9999,69,20,9999,9999,9999,0,
//8
{9999,9999,9999,9999,9999,
//9
{9999,9999,9999,9999,9999,
//10
{9999,79,46,9999,9999,9999,
//11
{41,9999,60,83,9999,9999,41,
//12
{9999,99999,9999,9999,9999,
//13
{64,9999,9999,9999,9999,93,
//14
{9999,9999,9999,23,41,9999,
//15
{133,9999,9999,9999,9999,9999,
//16
{9999,9999,9999,9999,9999,
//17
{9999,9999,9999,9999,9999,
//18
{9999,9999,54,9999,9999,9999,
//19
{65,9999,9999,9999,9999,9999,
//20
{115,9999,9999,9999,9999,9999,
//21
{55,9999,9999,9999,9999,9999,
//22
{9999,9999,9999,9999,9999,
//23
{9999,9999,9999,9999,9999,
- Нахождение минималного элемента в массиве
- Нахождение минимальной стоимости в транспортной сети
- Нахождение минимума унимодальной функции методами Дихотомии и Золотого сечения
- Нахождение оптимального места расположения склада для предприятия сеть киосков «Табакерка»
- Нахождение оптимального плана вложения денежных средств в депозиты
- Нахождение оптимального плана транспортной задачи
- Нахождение погрешности показания среднесуточной температуры термометра
- Научный метод, логика и методология развития естествознания
- Научный потенциал в РФ
- Научный стиль: традиции и новые тенденции
- НАФТА и международная миграция рабочей силы
- Нафтова промисловість у системі РПС
- Нахождение безусловного экстремума методом Ньютона
- Нахождение кратчайшего пути алгоритмом Дейкстры
