Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Разработка виртуальной лаборатории для поиска минимального маршрута
Содержание
Введение
. Анализ задания, обзор аналогов
.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 - класс, описывающий вершину графа:
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) - удаление вершины из фронта.
. 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” - диаметр графа.
В качестве примера приводится строка, полученная в результате работы с графом, заданным следующей матрицей смежности:
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
После всех необходимых измерений, получились следующие результаты:
− длина кратчайшего пути - 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_path |
5 |
|
exct1 |
4 |
|
|
exct2 |
4 |
|
|
exct3 |
5 |
|
|
exct4 |
5 |
|
|
exct5 |
5 |
|
|
exct6 |
3 |
|
|
exct7 |
3 |
|
|
radius |
4 |
|
|
diameter |
5 |
|
|
Граф задан матрицей. Определить минимальную длину пути из вершины 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_path |
2 |
|
exct1 |
2 |
|
|
exct2 |
2 |
|
|
exct3 |
2 |
|
|
exct4 |
2 |
|
|
exct5 |
2 |
|
|
exct6 |
2 |
|
|
radius |
2 |
|
|
diameter |
2 |
|
|
Граф задан матрицей. Определить минимальную длину пути из вершины 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_path |
3 |
|
exct1 |
2 |
|
|
exct2 |
3 |
|
|
exct3 |
3 |
|
|
exct4 |
3 |
|
|
exct5 |
2 |
|
|
radius |
2 |
|
|
diameter |
3 |
Заключение
В результате выполнения тестирования виртуальной лаборатории найдено оптимальное количество вершин в графе, составляющем задание.
Во-первых, число узлов не должно быть меньше 5. Иначе нет возможности составить сколько-нибудь трудное задания для данного алгоритма. Помимо этого результаты сдачи студентами лабораторной работы будут мало их рассеивать, так как рассеивающая способность в данной работе прямо пропорциональна числу вершин, на которых построен граф (за каждое задание студент получает 100/(N+3) баллов, где N - это число вершин).
Во-вторых, нет надобности составлять задания с графами более 9 вершин, поскольку выполнение большей части работы в таком случае сведется к рутинным операциям. Такая работа тоже будет мало дифференцировать аттестующихся, поскольку навыки и знания, необходимые для выполнения данной работы, проверяются и на меньшем числе вершин, а так только добавляются ошибки, связанные с рассеянием внимания на однообразных действиях.