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