Назад в библиотеку

---

Обучающая система по нахождению остовных деревьев минимальной стоимости

Науч. руководитель ст.преп. Ольшевский А.И. 

Институт информатики и искусственного интеллекта Донецкого Национального технического университета

Автор: Степанова А.А.

В настоящее время во многих странах активно ведутся вычисления нахождения кратчайшего пути при помощи разных алгоритмов. Среди существующих поисков решений для нахождения кратчайшего пути можно выделить следующие алгоритмы: «Прима», «Дейкстры» и «Форда-Беллмана» и т.п. Алгоритмы «Прима» и «Дейкстры» являются жадными алгоритмами. Жадный алгоритм – это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным. Алгоритм «Форда-Беллмана» значительно отличается от алгоритмов «Прима» и «Дейкстры» тем, что в графе допускаются ребра с отрицательным весом.

Остовное дерево это – ациклический связный подграф данного графа, в который входят все его вершины. Другими словами, минимальное остовное дерево (МОД) состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам. При этом в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды. Таким образом, это обстоятельство позволяет нам сформулировать следующую постановку задачи: найти кратчайший путь между двумя заданными вершинами [1].

Задача нахождения кратчайшего пути от одного узла сети к другому предполагает нечто большее, чем поиск какого-нибудь одного маршрута. При этом вершины остовного дерева можно использовать для представления объектов, а дуги – для отношения между объектами. Путем в остовном дереве можно назвать последовательность вершин V_1, V₂, …, V_n, для которой существует дуги соединение этих вершин [2].

Разбирая алгоритмы по нахождению кратчайшего пути, как правило, многие понимают принцип работы на примере. Естественно это облегчает понимание работы алгоритма.

Автором предлагается программная реализация обучающей системы по нахождению остовного дерева минимальной стоимости с реализацией наиболее известных алгоритмов. Обучающая система позволяет визуализировать пошаговое построение дерева в графическом виде и анализировать численные результаты. Исходными данными для решения поставленной задачи являются элементы графа. Достоинства программной реализации заключается в возможности:

– использования интерактивного графического интерфейса для изучения теоретического материала по методам;

– выбора реализованного алгоритма построения МОД с пошаговым графическим построением;

– анализа численных результатов для разных алгоритмов с построением сравнительных диаграмм.

Система обучения методам построения остовного дерева минимальной стоимости разрабатывалось с учетом современных программных технологий и может быть использовано не только в виде отдельного пакета в университетах, школах  и других обучающих центрах, но и в системах дистанционного обучения.

 

Литература: