Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

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

Работа добавлена на сайт samzan.ru: 2016-03-13


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


Содержание

Введение

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

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




1. Линейная структура следование образуется из последовательности команд следующих одна за другой
2. доходы и расходы Понятия доходы и расходы в бухгалтерском учете Понятие доходы Согласно ПБУ 9-
3. Труд в природе, его роль в формировании экологической воспитанности дошкольников
4. Бикерниекская церковь и церковь Креста
5. В в слове Введение далее вкладка вставка в ней разрыв страниц и так перед всеми заголовками чтобы он
6. Лекция КРОВЬ
7. задание 9 РЕШЕНИЕ ЗАДАЧИ ДИРИХЛЕ ДЛЯ УРАВНЕНИЯ ЛАПЛАСА МЕТОДОМ СЕТОК В настоящей лабора
8. Понятие и виды трудового стажа1
9. ЛЕСНОЙ НА ЛЕТНИЙ СЕЗОН 2014 года
10. либо симптомов проявления
11. на тему- Правовое воспитание учащихся Студент
12. Schoolru г
13. Антикризисное управление 1
14. Статья 1110 Наследование 1
15. это процесс и результаты социализации воспитания и саморазвития
16. Любов до мудрості це буквальний переклад з давньогрецької слова Первісна світоглядна форма Об~єк
17. 39401д спец 1905 Научный руководитель Пасечник Сергей Вениаминович Москва 1996
18. Реферат на тему- Совет Безопасности ООН ученицы 11А класса ООШ
19. на тему- Українське мистецтво доби просвітництва Виконала- студентка 2 курсу група 201
20. тема ірригації Але до VІ ст