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

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

Содержание Введение

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

1.1 Анализ задания

1.2 Обзор аналогов

2. Сценарий работы пользователя

2.1 Прецеденты использования

2.2 Сценарий работы пользователя

3. Архитектура программного кода

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

4.1 Формат ответа

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

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

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

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

Введение

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

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

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

1.1 Анализ задания Волновой алгоритм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.

Суть алгоритма следующая:

1. Указываются вершины первого фронта — смежные с начальной точкой пути. Им приписывается метка 1.

2. Вершинам следующего фронта — смежным с вершинами предыдущего — приписывается метка на один больше.

3. Если во фронте не достигнута конечная точка пути, и есть неразмеченные вершины, смежные с текущим фронтом, то повторяется шаг 2. Иначе выполняется шаг 4.

4. Если во фронте достигнута конечная точка пути, то длина кратчайшего пути составит значение метки фронта, к которому она принадлежит. Если нет неразмеченных вершин, смежных с текущим фронтом, то конечная точка пути недостижима из начальной (бесконечно далека).

С помощью волнового алгоритма можно рассчитать основные метрические характеристики графа — диаметр и радиус.

Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через ecc (a).

Величина наименьшего эксцентриситета называется радиусом графа и обозначается через rad (G), а величина наибольшего — диаметром и обозначается diam (G).

Наименьший диаметр имеет полный граф — его диаметр равен 1. Среди связных графов с n вершинами наибольший диаметр, равный n-1, имеет цепь P_n .

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

1.2 Обзор аналогов В качестве аналогов были выбраны визуализаторы по дискретной математике, представленные на сайте кафедры компьютерных техгологий СПбГУ ИТМО.

К недостаткам ресурса можно отнести:

· отсутствие какой бы то ни было документации;

· неудобный интерфейс.

К плюсам:

· охват широкого спектра алгоритмов в области дискретной математики и комбинаторики.

2. Сценарий работы пользователя

2.1 Прецеденты использования При разработке диаграммы прецедентов рассматривались следующие актеры:

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

· апплет, второстепенный актер; цель апплета — получить ответ пользователя и отправить его на проверку на сервер;

Далее следует определить возможные сценарии взаимодействия актеров с системой и между собой (см. рисунок 1)

Как видно из схемы, главная роль отводится студенту — апплет же реагирует на его действия: отрисовывает интерфейс, производит раскраску графа, а по окончании работы отправляет ответ на сервер.

Рисунок 1 — Диаграмма прецедентов использования

2.2 Сценарий работы пользователя

1. Отрисовка графа, описанного в задании матрицей смежности:

1.1. Установка количества вершин.

1.2. Указание вершин начала и конца пути.

2. Поиск минимального маршрута в графе:

2.1. Отчитывая от начальной точки маршрута, указываются вершины n_го фронта (отмеченным вершинам приписывается метрика n);

2.2. Если конечная точка маршрута не достигнута, повторяется шаг 2.1;

2.3. Указывается длина кратчайшего пути.

3. Определение метрических характеристик графа:

3.1. Для каждой вершины производится полная разметка графа волновым алгоритмом для поиска эксцентриситета:

3.1.1. Отчитывая от начальной вершины, указываются вершины n_го фронта (отмеченным вершинам приписывается метрика n);

3.1.2. Если есть неразмеченные вершины, повторяется шаг 3.1.1;

3.1.3. Указывается эксцентриситет вершины

3.2. Из сводки всех эксцентриситетов выводятся радиус и диаметр графа.

4. Завершение работы, отправка результатов.

3. Архитектура программного кода На схеме ниже представлена структура классов виртуального стенда (рисунок 4).

Описание классов:

1. Console — интерфейс для реализации лабораторного стенда.

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

o int x, y — координаты узла;

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) — удаление вершины из фронта.

6. 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. Описание формата ответа и тестовых наборов

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

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

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 вершин, поскольку выполнение большей части работы в таком случае сведется к рутинным операциям. Такая работа тоже будет мало дифференцировать аттестующихся, поскольку навыки и знания, необходимые для выполнения данной работы, проверяются и на меньшем числе вершин, а так только добавляются ошибки, связанные с рассеянием внимания на однообразных действиях.