Реализация алгоритма и анализ результатов
Среднее время работы программы представлено на рисунке 2. Вертикальная ось отображает время в тиках, горизонтальная — количество узлов в графе. Три кривые отображают зависимость времени работы от количества узлов при относительной погрешности. Таким образом, видно, что, чем ниже относительная погрешность, тем больше времени затрачивается на расчеты, однако при этом растет точность. Одной… Читать ещё >
Реализация алгоритма и анализ результатов (реферат, курсовая, диплом, контрольная)
Использованные средства и технологии
Для реализации был выбран язык программирования С++, т.к. он является одним из самых лучших, востребованных языков. К тому же С++ является кроссплатформенным языком программирования. В качестве среды разработки использовалась Microsoft Visual Studio 2013 Professional.
Помимо этого в приложении использована структура хранения данных в виде локальной базы данных для получения более удобной и организованной формы хранения информации. БД создана с помощью SQLite, а в программе сообщение с БД выполняется посредством языка SQL-запросов.
Для графического оформления демонстрационного режима были задействованы графические библиотеки OpenGL.
Измерения
Основные функции
После реализации основных алгоритмов программы (Рис.1) было необходимо провести эксперименты для замеров и оценки эффективности алгоритмов. После проведения некоторого числа экспериментов над программой были получены данные.
Среднее время работы программы представлено на рисунке 2. Вертикальная ось отображает время в тиках, горизонтальная — количество узлов в графе. Три кривые отображают зависимость времени работы от количества узлов при относительной погрешности. Таким образом, видно, что, чем ниже относительная погрешность, тем больше времени затрачивается на расчеты, однако при этом растет точность.
На рисунке 3 представлены данные проведения экспериментов с одним графом. Точно так же по горизонтали указано количество узлов в графе, по вертикали — время в тиках. В данном случае в расчеты вошло время вычисления объема выборки, случайное удаление ребер в графе и проверка связности графа на каждом этапе удаления. Не трудно заметить, что уже при (зеленая линия на графике) на вычисления времени уходит гораздо больше. Это связано с тем, что для большей точности данных требуется больший объем выборки.
Для наглядности рассмотрим пример графа с описанием (Рисунок 4).
граф стохастический связность библиотека Горизонтальная ось показывает значения относительной погрешности. Вертикальная ось так же отображает время в тиках. В данном случае четко видно, как резко возрастает время работы из-за повышения точности результата.
Второстепенные функции
Одной из второстепенных функций программы является предоставление демонстрационного режима для наглядного ознакомления или отслеживания процесса потери связности в графе. Было решено реализовать это с использованием графической библиотеки OpenGL (#include и #include). В этом режиме можно пошагово удалять случайные ребра до тех пор, пока граф не распадется на две несвязанные части.