Разработка виртуальной лаборатории для поиска минимального маршрута

 

Разработка виртуальной лаборатории для поиска минимального маршрута

Содержание

Введение

. Анализ задания, обзор аналогов

.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 - интерфейс для реализации лабораторного стенда.

2.Node - класс, описывающий вершину графа:

oint x, y - координаты узла;

ovoid setCoords(int x, int y) - устанавливает координаты;

oint[] getCoords() - возвращает координаты;

3.Edge - класс, реализующий ребро графа:

oint[] nodes - ID вершин, которые соединяет ребро;

oint[] getNodes - возвращает вершины, соединяемые ребром.

4.Front - класс, интерпретирующий фронт волнового алгоритма:

oint[] nodes - вершины, образующие фронт;

ovoid add(int index) - добавляет вершину во фронт;

oint findNode(int index) - проверка на наличие во фронте; если вершина найдется, то возвратится ее индекс во фронте, инасе возвратится -1;

oint[] getNodes() - возвращает вершины фронта;

oint getNodesCount() - возвращат размер фронта;

ovoid remove(int index) - удаляет вершину из фронта.

5.Graph - класс, описывающий граф:

oEdge[] edges - массив рёбер графа

oNode[] nodes - массив вершин графа;

oFrontd[] fronts - масств созданных фронтов волнового алгоритма.

oint edgesCount, nodesCount, frontdCount - число рёбер, узлов и размеченных фронтов в графе;

oint finish, start - концы маршрута;

ovoid addEdge(int[] nodes)- добавляет в граф ребро;

ovoid addFront() - создает новый фронт в графе;

ovoid addToFront(int index) - добавляет узел во фронт;

ovoid removeEdge(int[] nodes) - удаляет ребро;

ovoid removeFront() - удаляет текущий фронт;

oboolean isAllNodesMarked() - проверка на полную раскраску графа;

ovoid removeFromFront(int index) - удаление вершины из фронта.

. Laboratory - класс апплета виртуального стенда:

oString answer - строка ответа аттестующегося;

oGraph graph - граф, на котором реализуется задание;

oint step - текущий шаг прохождения лабораторной работы;

ovoid changeMark(Graphics g, int clickedNode) - изменение разметки вершины;

ovoid initComponents() - инизиализация компонентов интерфейса;

ovoid paintEdge(Graphics g, int first, int second) - отрисовка ребра;

ovoid paintNode(Graphics g, int index) - отрисовка вершины;

ovoid paintGraph(JPanel panel, int nodesCount) - отрисовка графа;

ovoid setNewStartNode(Graphics g, int node) - установка новой начальной точки на четвертом этапе - вычислении эксцентриситетов;

Рисунок 2 - Схема классов виртуального стенда

4. Описание формата ответа и тестовых наборов

.1 Формат ответа

Формат строки ответа, возвращаемой методом апплета getResults(), имеет следующий вид:

pathLength exct1 exct2 … exctN rad diam

.., где pathLength - длина кратчайшего пути в графе, описанном матрицей смежности, exct1 exct2 … exctN - эксцентриситеты для графа на N вершинах, rad - радиус графа, diam - диаметр графа.

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

0001011000001000001011000001001000011000001011000

После всех необходимых измерений, получились следующие результаты:

?длина кратчайшего пути - 5;

?эксцентриситеты - 3 5 4 3 5 4 3;

?радиус графа - 3

?диаметр графа - 5

Строка ответа будет выглядеть следующим образом:

3 5 4 3 5 4 3 3 5

4.2 Формат тестового набора

В тестовый набор на задание с графом на N вершинах входит N+3 проверки - на каждую часть ответа, вводимую студентом. Каждая проверка описана в таблице 1.

Таблица 1. Формат тестового набора.

Входная строкаВыходная строкаmin_pathдлина кратчайшего пути для заданного графаexct1эксцентриситет для первой вершины заданного графаexct2эксцентриситет для второй вершины заданного графа………………………………………………..exctNэксцентриситет для N-ой вершины заданного графаradiusрадиус заданного графаdiameterдиаметр заданного графа

5. Виртуальный стенд

На первом шаге студенту предоставляется интерфейс для ввода начальных данных - количества вершин в графе, а также начала и конца пути (рисунок 3).

Рисунок 3 - ввод начальных данных

По этим данным строятся вершины графа, отмечаются концы пути. Предоставляется интерфейс для отрисовки рёбер (рисунок 4).

Рисунок 4 - отрисовка рёбер

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

Рисунок 5 - поиск кратчайшего пути.

Следующий шаг - это раскраска графа, начиная от каждой вершины по очереди, с целью нахождения эксцентриситетов (рисунок 6).

.

Рисунок 6 - определение эксцентриситетов

Когда для каждой вершины будет определен эксцентриситет, будет произведен переход к последнему шагу - вводу радиуса и диаметра графа по данным предыдущего этапа (рисунок 7).

Рисунок 7 - ввод радиуса и диаметра графа

По нажатии кнопки «Завершить работу» методом getResult() ответ студента отправится на проверку.

6. Проверяющий сервер

При анализе ответа студента проверяется каждое задание в отдельности. Сопоставляются с эталонными значениями:

?длина кратчайшего пути;

?каждый эксцентриситет;

?радиус графа;

?диаметр графа.

Таким образом, за каждое верно введенное значение студент получает 100/(N+3) баллов из расчета, что полностью верный ответ - это 100 баллов.

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

7. Задания и тестовые наборы

Ниже представлено несколько вариантов заданий и тестовые наборы для них.

Таблица 2. Задания для виртуальной лабораторной работы.

ЗаданиеВходящий тестовы наборВыходящий тестовый наборГраф задан матрицей. Определить минимальную длину пути из вершины 3 в вершину 5. Определить метрические характеристики данного графа. 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 min_path5exct14exct24exct35exct45exct55exct63exct73radius4diameter5Граф задан матрицей. Определить минимальную длину пути из вершины 3 в вершину 5. Определить метрические характеристики данного графа. 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 min_path2exct12exct22exct32exct42exct52exct62radius2diameter2Граф задан матрицей. Определить минимальную длину пути из вершины 3 в вершину 5. Определить метрические характеристики данного графа. 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 min_path3exct12exct23exct33exct43exct52radius2diameter3

Заключение

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

Во-первых, число узлов не должно быть меньше 5. Иначе нет возможности составить сколько-нибудь трудное задания для данного алгоритма. Помимо этого результаты сдачи студентами лабораторной работы будут мало их рассеивать, так как рассеивающая способность в данной работе прямо пропорциональна числу вершин, на которых построен граф (за каждое задание студент получает 100/(N+3) баллов, где N - это число вершин).

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

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

Больше работ по теме: