Данный исследовательский проект посвящен разработке и анализу алгоритмов для построения ориентированного или неориентированного графа, представленного в виде весовой матрицы смежности. Особое внимание уделяется детальному изучению методов нахождения всех возможных путей и маршрутов между двумя заданными вершинами графа, учитывая веса ребер. Проект предполагает реализацию и тестирование предложенных алгоритмов на различных тестовых наборах данных для оценки их эффективности, временной и пространственной сложности. Будут рассмотрены теоретические основы теории графов, алгоритмы поиска в глубину (DFS) и ширину (BFS) в модификациях для поиска всех путей, а также краевые случаи и оптимизации.
Идея проекта заключается в исследовании и применении методов компьютерной дискретной математики для решения практической задачи построения графовых моделей и полного анализа связности между узлами. Основной акцент делается на алгоритмическую разработку для выявления всех доступных маршрутов, что открывает возможности для дальнейших оптимизаций и применения в логистике, сетевом планировании или анализе данных.
В результате проекта будет разработан набор программных модулей, способных принимать на вход весовую матрицу, строить соответствующий граф и находить все существующие маршруты между любыми двумя указанными вершинами. Эти модули будут содержать как реализацию классических, так и, возможно, модифицированных алгоритмов, с подробной документацией и примерами использования.
Задача поиска всех возможных путей между двумя вершинами в графе является вычислительно сложной, особенно для больших графов. Стандартные алгоритмы поиска кратчайшего пути не решают эту задачу, требуя модификаций или специализированных подходов. Существующие методы могут быть неоптимальны или трудноприменимы в различных контекстах, что требует дальнейших исследований.
Актуальность проекта обусловлена широким применением графовых моделей в современных технологиях, таких как маршрутизация в сетях, логистика, анализ социальных связей и биоинформатика. Понимание и возможность полного перебора всех путей между точками имеет значение для задач, где важна не только оптимальность, но и разнообразие вариантов.
Основная цель проекта — разработать и продемонстрировать эффективные алгоритмы для построения графа по весовой матрице и определения всех возможных путей между двумя заданными вершинами. Будет проведено сравнение производительности различных подходов и сформулированы рекомендации по их применению.
Проект ориентирован на студентов и специалистов в области информатики, математики, инженерии и смежныхдисциплин, интересующихся алгоритмическими задачами и теорией графов. Он будет полезен для тех, кто занимается разработкой систем, требующих анализа связей и маршрутизации.
Для реализации проекта потребуются персональный компьютер или ноутбук с установленной средой разработки (например, Python с библиотеками NetworkX, NumPy), доступ к литературе по теории графов и алгоритмам, а также учебные материалы.
Отвечает за теоретическое исследование и проектирование новых или модификацию существующих алгоритмов поиска всех путей, а также за их математическое обоснование и документирование.
Занимается написанием кода для реализации разработанных алгоритмов, интеграцией их в единую программную среду, обеспечением корректной работы и тестированием функциональности.
Отвечает за подготовку тестовых данных, проведение экспериментов по оценке производительности алгоритмов, сбор и анализ результатов, а также визуализацию полученных данных.
Отвечает за создание пользовательской и технической документации, описывающей принципы работы, методику применения и особенности разработанных алгоритмов и программных модулей.
Выполнил: ФИО
Руководитель: ФИО
