Задача Штейнера в ориентированных графах

Выпускная квалификационная работа на тему: «Задача Штейнера в ориентированных графах» состоит из введения, пяти разделов, заключения и списка используемой литературы. Общий объем работы 115 страниц текста, содержащего 11 рисунков и 16 таблиц. Список литературы содержит 15 источников, в том числе 5 иностранных. Ключевые слова: Задача Штейнера, минимальное дерево Штейнера, евклидовы графы, ориентированные графы, точные методы решения задачи Штейнера, приближённые методы задачи Штейнера Данная работа посвящена исследованию вопроса применения точных и приближённых методов решения задачи Штейнера на ориентированных графах. Актуальность: Точные алгоритмы решения задачи Штейнера могут быть использованы для решения задач малых размерностей. Приближённые алгоритмы направлены на решение высокомощностных задач на графах, однако вопрос целесообразности их применения на практике остаётся до сих пор открытым. Особенно при решении задачи Штейнера на ориентированных графах, которая в литературе не так широко затронута в отличие от задач на неориентированных сетях в заданном метрическом пространстве. Отметим, что многие подобные задачи, ставящиеся на практике, сводятся к евклидовому графу, в котором каждая вершина имеет евклидовы координаты, а длина каждого ребра задается расстоянием между инцидентными ей вершинами. Таким образом, обуславливается актуальность исследования различных алгоритмов решения задачи Штейнера на ориентированных графах, заданных в Евклидовом пространстве/плоскости. Научная новизна: применение матрицы расстояний между вершинами при описании ориентированного графа. Разработка программы для ЭВМ для решения задачи Штейнера на ориентированных графах. Во введении дается общая характеристика работы, обосновывается актуальность исследований, формулируется цель работы, раскрывается научная новизна и практическая значимость полученных результатов. Дается краткий обзор содержания работы по разделам. В первом разделе делается обзор предметной области и приводятся классические постановки задачи Штейнера, а также рассматриваются основные точные и приближённые алгоритмы решения задачи Штейнера на ориентированных графах. Во втором разделе проводится теоретический анализ поставленной задачи. Приводится базовая модель объекта исследования в виде матрицы расстояний, описывающей исходный граф, а также выходной бинарной матрицы отображений, которая используется для отображения минимального дерева Штейнера, получаемого по результатам использования выбранного алгоритма решения задачи Штейнера по отношению к исходной матрице расстояний. Дается обоснование выбора точных методов решения задачи Штейнера на ориентированных графов и двух приближённых методов решения данной задачи. Также приводится модель визуализации искомого минимального дерева Штейнера. В третьем разделе приводится подробное описание методики решения поставленной задачи. В четвертом разделе приводится практическая реализация решения поставленной задачи в виде программы, реализующей работу алгоритмов, описанных в третьем разделе, с целью обеспечения возможности проведения экспериментальных исследований. В пятом разделе описываются проделанные эксперименты по исследованию качественных и количественных показателей работы алгоритмов. Формулируются выводы о применимости алгоритмов решения задачи Штейнера и выносятся рекомендации по их использованию. В заключении подробно изложены основные результаты проведенных исследований. Студент: Горбачева Арина Андреевна Научный руководитель: Мокеев Дмитрий Борисович