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

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

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

Содержание

Введение

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

.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, имеет цепь P_n .

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

.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 - класс, описывающий вершину графа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pathLength exct1 exct2 … exctN rad diam

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

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

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

−      длина кратчайшего пути - 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. Формат тестового набора.

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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