Разработка виртуальной лаборатории для поиска минимального маршрута
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Разработка виртуальной лаборатории для поиска минимального маршрута
Содержание
Введение
. Анализ задания, обзор аналогов
.1 Анализ задания
.2 Обзор аналогов
. Сценарий работы пользователя
.1 Прецеденты использования
.2 Сценарий работы пользователя
. Архитектура программного кода
. Описание формата ответов и тестового набора
.1 Формат ответа
.2 Формат тестового набора
. Виртуальный стенд
. Проверяющий сервер
. Задания и тестовые наборы
Заключение
Введение
виртуальная лаборатория дискретная математика граф
По наиболее общему определению виртуальная лаборатория представляет собой некую среду, позволяющую проводить эксперименты, не имея непосредственного доступа к объекту исследования. В случае дискретной математики виртуальные лаборатории имеют особое значение, так как предметы дисциплины по большей части абстрактны, и создание моделей в рамках этого курса обеспечит лучшее понимание материала.
В рамках данной курсовой работы необходимо разработать виртуальную лабораторию, реализующую волновой алгоритм для поиска минимального маршрута и определения метрических характеристик заданного графа.
1. Анализ задания и обзор аналогов
.1 Анализ задания
Волновой алгоритм - алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.
Суть алгоритма следующая:
1.Указываются вершины первого фронта - смежные с начальной точкой пути. Им приписывается метка 1.
2.Вершинам следующего фронта - смежным с вершинами предыдущего - приписывается метка на один больше.
.Если во фронте не достигнута конечная точка пути, и есть неразмеченные вершины, смежные с текущим фронтом, то повторяется шаг 2. Иначе выполняется шаг 4.
.Если во фронте достигнута конечная точка пути, то длина кратчайшего пути составит значение метки фронта, к которому она принадлежит. Если нет неразмеченных вершин, смежных с текущим фронтом, то конечная точка пути недостижима из начальной (бесконечно далека).
С помощью волнового алгоритма можно рассчитать основные метрические характеристики графа - диаметр и радиус.
Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через ecc(a).
Величина наименьшего эксцентриситета называется радиусом графа и обозначается через rad(G), а величина наибольшего - диаметром и обозначается diam(G).
Наименьший диаметр имеет полный граф - его диаметр равен 1. Среди связных графов с n вершинами наибольший диаметр, равный n-1, имеет цепь Pn .
Разметив граф волновым алгоритмом поочередно от каждой вершины, можно определить ее эксцентриситет, а из множества всех эксцентриситетов графа установить его радиус и диаметр.
.2 Обзор аналогов
В качестве аналогов были выбраны визуализаторы по дискретной математике, представленные на сайте кафедры компьютерных техгологий СПбГУ ИТМО.
К недостаткам ресурса можно отнести:
отсутствие какой бы то ни было документации;
неудобный интерфейс.
К плюсам:
охват широкого спектра алгоритмов в области дискретной математики и комбинаторики.
2. Сценарий работы пользователя
.1 Прецеденты использования
При разработке диаграммы прецедентов рассматривались следующие актеры:
студент, главный актер, его цель - нахождение кратчайшего пути в заданном графе и определение его метрических характеристик; для реализации этих задач он взаимодействует с апплетом;
апплет, второстепенный актер; цель апплета - получить ответ пользователя и отправить его на проверку на сервер;
Далее следует определить возможные сценарии взаимодействия актеров с системой и между собой (см. рисунок 1)
Как видно из схемы, главная роль отводится студенту - апплет же реагирует на его действия: отрисовывает интерфейс, производит раскраску графа, а по окончании работы отправляет ответ на сервер.
Рисунок 1 - Диаграмма прецедентов использования
2.2 Сценарий работы пользователя
1.Отрисовка графа, описанного в задании матрицей смежности:
1.1.Установка количества вершин.
1.2.Указание вершин начала и конца пути.
2.Поиск минимального маршрута в графе:
2.1. Отчитывая от начальной точки маршрута, указываются вершины n-го фронта (отмеченным вершинам приписывается метрика n);
2.2. Если конечная точка маршрута не достигнута, повторяется шаг 2.1;
.3. Указывается длина кратчайшего пути.
3.Определение метрических характеристик графа:
3.1. Для каждой вершины производится полная разметка графа волновым алгоритмом для поиска эксцентриситета:
3.1.1.Отчитывая от начальной вершины, указываются вершины n-го фронта (отмеченным вершинам приписывается метрика n);
3.1.2.Если есть неразмеченные вершины, повторяется шаг 3.1.1;
.1.3.Указывается эксцентриситет вершины
3.2. Из сводки всех эксцентриситетов выводятся радиус и диаметр графа.
4. Завершение работы, отправка результатов.
3. Архитектура программного кода
На схеме ниже представлена структура классов виртуального стенда (рисунок 4).
Описание классов:
1.Console - интерфейс для реализации л