В.И. Мунерман – к.т.н., доцент, кафедра информатики, Смоленский государственный университет (СмолГУ) E-mail: vimoon@gmail.com

Т.А. Самойлова – к.т.н., доцент, кафедра информатики, Смоленский государственный университет (СмолГУ) E-mail: tatsamoilova24@gmail.com

Рассмотрен алгебраический подход к повышению эффективности обработки данных при решении задач построения маршрутов. В основу подхода положены теория многомерных матриц и специальные двухосновные алгебраические системы (абстрактные алгебраические машины). Отмечено, что этот подход позволяет эффективно распараллеливать алгоритмы построения всех возможных маршрутов, а также использовать технологию in database для построения всех маршрутов. Показано, что это возможно в силу изоморфизма алгебры многомерных матриц и реляционной алгебры для рассматриваемого класса задач. В качестве основной алгебраической операции использован один из вариантов операции умножения многомерных матриц – (1,0)-свернутое произведение, при котором не производится суммирование элементов (отсутствуют кэлиевы индексы). Приведен алгоритм построения всех маршрутов с заданными свойствами, который реализует многократное применения этой операции. Дано описание представления разреженных многомерных матриц в реляционной базе данных. Описан алгоритм построения всех маршрутов с заданными свойствами, который реализует многократное применение операции Join. Представлен пример, иллюстрирующий предложенный подход.

1. Bast H. Car or public transport – two worlds // Efficient Algorithms. LNCS. Springer. 2009. V. 5760. P. 355−367.
2. Беляков С.Л., Коломийцев Я.А., Розенберг И.Н., Савельева М.Н. Модель решения задачи маршрутизации в интеллектуальной геоинформационной системе // Известия ЮФУ. Технические науки. 2011. Т. 118. № 5. С. 113−119.
3. Ageyev D., Ignatenko A., Wehbe F. Design of Information and Telecommunication Systems with the Usage of the Multi-Layer Graph Model // XII International Conference «The Experience of Designing and Application of CAD Systems in Microelectronics». Lviv-Polyana. Ukraine. 2013. P. 1−4.
4. Miller J.A., Ramaswamy L., Kochut K.J., Fard A. Research Directions for Big Data Graph Analytics // IEEE International Congress on BigData. 2015. P. 785−794.
5. Марголис Б.И., Музанна М.М. Синтез магистральных телекоммуникационных сетей // Программные продукты и системы. 2014. № 1(105). С. 162−168.
6. Семенов Ю.Н., Семенова О.С. Применение методов кластеризации при организации международных перевозок грузов // Вестник КузГТУ. 2016. № 6. С. 201−205.
7. Masum K., Faruque F., Shahjalal M., Sarker H. Solving the Vehicle Routing Problem using Genetic Algorithm // International Journal of Advanced Computer Science and Applications. 2011. V. 2. № 7. 126−131.
8. Соколов Н.П. Введение в теорию многомерных матриц. Киев: Наукова думка. 1972. 176 с.
9. Мунерман В.И. Модели обработки больших объемов данных в системах массового параллелизма // Системы высокой доступности. 2013. Т. 9. № 1. С. 35−43.
10. Мунерман В.И. Архитектура программно-аппаратного комплекса для массовой обработки данных на базе многомерноматричной модели // Системы высокой доступности. 2015. Т. 11. № 2. С. 13−18.
11. Захаров В.Н., Мунерман В.И. Параллельный алгоритм умножения многомерных матриц // Современные информационные технологии и ИТ-образование. 2015. Т. 2. № 11. С. 384−390.