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

В случае дискретной математики виртуальные лаборатории имеют особое значение, так как предметы дисциплины по большей части абстрактны, и создание моделей в рамках этого курса обеспечит лучшее понимание материала.Волновой алгоритм - алгоритм, позволяющий найти минимальный путь в графе с ребрами единичной длины. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину. Указываются вершины первого фронта - смежные с начальной точкой пути. Если во фронте не достигнута конечная точка пути, и есть неразмеченные вершины, смежные с текущим фронтом, то повторяется шаг 2. Если во фронте достигнута конечная точка пути, то длина кратчайшего пути составит значение метки фронта, к которому она принадлежит.В качестве аналогов были выбраны визуализаторы по дискретной математике, представленные на сайте кафедры компьютерных техгологий СПБГУ ИТМО.При разработке диаграммы прецедентов рассматривались следующие актеры: · студент, главный актер, его цель - нахождение кратчайшего пути в заданном графе и определение его метрических характеристик; для реализации этих задач он взаимодействует с апплетом;Отчитывая от начальной точки маршрута, указываются вершины n-го фронта (отмеченным вершинам приписывается метрика n); Если конечная точка маршрута не достигнута, повторяется шаг 2.1; Для каждой вершины производится полная разметка графа волновым алгоритмом для поиска эксцентриситета: 3.1.1. Отчитывая от начальной вершины, указываются вершины n-го фронта (отмеченным вершинам приписывается метрика n);Edge - класс, реализующий ребро графа: o int[] nodes - ID вершин, которые соединяет ребро; o void add(int index) - добавляет вершину во фронт; o int FINDNODE(int index) - проверка на наличие во фронте; если вершина найдется, то возвратится ее индекс во фронте, инасе возвратится-1; o void remove(int index) - удаляет вершину из фронта. Graph - класс, описывающий граф: o Edge[] edges - массив ребер графа o Node[] nodes - массив вершин графа;.., где “PATHLENGTH” - длина кратчайшего пути в графе, описанном матрицей смежности, “exct1 exct2 … EXCTN” - эксцентриситеты для графа на N вершинах, “rad” - радиус графа, “diam” - диаметр графа. В качестве примера приводится строка, полученная в результате работы с графом, заданным следующей матрицей смежности: 0 0 0 1 0 1 1В тестовый набор на задание с графом на N вершинах входит N 3 проверки - на каждую часть ответа, вводимую студентом.На первом шаге студенту предоставляется интерфейс для ввода начальных данных - количества вершин в графе, а также начала и конца пути (рисунок 3). Предоставляется интерфейс для отрисовки ребер (рисунок 4). Затем становится возможным создание фронтов и раскраска графа по методу волнового алгоритма с целью нахождения длины кратчайшего пути (рисунок 5). Как только вершина конца пути попадает во фронт, становится доступным поле для ввода длины минимального маршрута, а также кнопка для перехода на следующий этап.При анализе ответа студента проверяется каждое задание в отдельности. Сопоставляются с эталонными значениями: - длина кратчайшего пути;Задание Входящий тестовы набор Выходящий тестовый набор Граф задан матрицей. Определить минимальную длину пути из вершины 3 в вершину 5. Определить метрические характеристики данного графа. Определить минимальную длину пути из вершины 3 в вершину 5.В результате выполнения тестирования виртуальной лаборатории найдено оптимальное количество вершин в графе, составляющем задание. Помимо этого результаты сдачи студентами лабораторной работы будут мало их рассеивать, так как рассеивающая способность в данной работе прямо пропорциональна числу вершин, на которых построен граф (за каждое задание студент получает 100/(N 3) баллов, где N - это число вершин).

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

виртуальная лаборатория дискретная математика граф

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

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

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

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

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

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

Размещено на