Русский
!

Conference publications

Abstracts

XX conference

Математические вычисления средствами баз данных на примере алгоритма Дейкстры

Маркеев В.Ю., Крючков А.А.

г. Тамбов, ул. Интернациональная, д. 33

1 pp. (accepted)

Исторически сложилось, что для математических вычислений в компьютерной среде, в большинстве случаев, используются такие языки программирования, как C++, Java, Pascal и подобные. Что касается баз данных, то их принято использовать преимущественно для длительного хранения информации, а для серьезных вычислений они считаются непригодными. Однако вопрос о реализации математических алгоритмов средствами баз данных оставался без ответа. Вертикальная организация данных упрощает логику алгоритмов, связанных с некоторыми математическими объектами, такими как графы.

Решение многих задач связанных с графами нередко базируется на поиске кратчайшего маршрута, соединяющего определенные вершины в заданном графе. Впервые такая задача (задача о минимальном пути) была решена в 1959 году норвежским программистом и математиком Эдсгером Дейкстрой. Он разработал алгоритм поиска длины минимального пути для неотрицательных значений дуг графа.

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

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

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



© 2004 Designed by Lyceum of Informational Technologies №1533