Нравится0
25.11.202221:3725 ноября 2022 21:37:40
Оптимизация задачи TSP на планарных графах
Научно-исследовательская работа
Автор:
Юдина Вероника Андреевна
ученица 10 Б класса
г. Ханты - Мансийск
Бюджетное общеобразовательное учереждение
«Югорский физико-математический лицей интернат»
Научный руководитель:
Юдина Ирина Игоревна
учитель информатики и ИКТ
высшей квалификационной категории
Муниципального автономного общеобразовательного учреждения
муниципального образования г. Нягань «Гимназия»
Аннотация
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Задача коммивояжера (traveling salesman problem, TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
В данной работе исследуется планарная версия этой задачи, где вершины графа можно представить, как точки на декартовой плоскости, а расстояние между вершинами будет в точности расстояние между точками на плоскости.
Объект исследования – оптимизации эвристических алгоритмов для планарного графа.
Гипотеза – применив методы оптимизации, можно достаточно эффективно решить задачу коммивояжера на планарных графах.
Цель работы - исследования решений задачи коммивояжера на планарных графах с помощью эвристических методов и создание собственного, более совершенного по сравнению с доступными алгоритмами.
В рамках достижения цели были поставлены следующие задачи: рассмотреть существующие методы решения задачи коммивояжера; исследовать эвристические алгоритмы и их реализации; разработать собственную программу на языке программирования Си++.
Методы исследования: анализ научной литературы и Интернет-ресурсов по теме; эксперимент; сравнение и обобщение полученных результатов.
Полученные результаты: разработан алгоритм, который качественно превосходит известные жадные, и прочие эвристические алгоритмы, при этом работает за полиномиальное (приемлемое в реальности) время.
Вывод: эффективность эвристических методов повышается при их комбинировании; применив методы оптимизации, получилось достаточно эффективно решить задачу коммивояжера на планарных графах.
