Розробка віртуальної лабораторії для пошуку мінімального маршруту
Зміст
Введення
. Аналіз завдання, огляд аналогів
.1 Аналіз завдання
.2 Огляд аналогів
. Сценарій роботи користувача
.1 Прецеденти використання
.2 Сценарій роботи користувача
. Архітектура програмного коду
. Опис формату відповідей і тестового набору
.1 Формат відповіді
.2 Формат тестового набору
. Віртуальний стенд
. Перевіряючий сервер
. Завдання та тестові набори
Висновок
Введення
віртуальна лабораторія дискретна математика граф
За найбільш загальним визначенням віртуальна лабораторія являє собою якусь середовище, що дозволяє проводити експерименти, не маючи безпосереднього доступу до об'єкта дослідження. У разі дискретної математики віртуальні лабораторії мають особливе значення, так як предмети дисципліни здебільшого абстрактні, і створення моделей в рамках цього курсу забезпечить краще розуміння матеріалу. p align="justify"> У рамках даної курсової роботи необхідно розробити віртуальну лабораторію, реалізовує хвильової алгоритм для пошуку мінімального маршруту та визначення метричних характеристик заданого графа. p align="justify"> 1. Аналіз завдання і огляд аналогів
.1 Аналіз завдання
Хвильовий алгоритм - алгоритм, що дозволяє знайти мінімальний шлях у графі з ребрами одиничної довжини. Заснований на алгоритмі пошуку в ширину. Застосовується для знаходження найкоротшого шляху в графі, в загальному випадку знаходить лише його довжину. p align="justify"> Суть алгоритму наступна:
1. Вказуються вершини першого фронту - суміжні з початковою точкою шляху. Їм приписується мітка 1.
2. Вершинам наступного фронту - суміжним з вершинами попереднього - приписується мітка на один більше.
. Якщо під фронт не досягнута кінцева точка шляху, і є нерозмічену вершини, суміжні з поточним фронтом, то повторюється крок 2. Інакше виконується крок 4.
. Якщо у фронті досягнута кінцева точка шляху, то довжина найкоротшого шляху складе значення мітки фронту, до якого вона належить. Якщо ні нерозмічених вершин, суміжних з поточним фронтом, то кінцева точка шляху недосяжна з початкової (нескінченно далека).
За ...
