«Матрица» как термин имеет много значений. В различных областях науки этот термин даже звучит по-разному, например: в математике – таблица чисел; в электронике – набор проводников и т.д. [2]. Покерные фишки так же имеют отношение к матрице. Поэтому матрицы можно встретить всюду, поэтому неважно программист ты, математик или простой обыватель, в любом случае нередко работаешь с матрицами.
Однако основное свое значение термин «матрица» имеет в математике. Матрица – математический объект, записанный в виде прямоугольной таблицы, представляющая собой совокупность строк и столбцов, на пересечение которых находятся элементы. Впервые понятие матрицы упоминалось еще в древнем Китае и называлась она «волшебным квадратом». И в основном применялись матрицы для решения линейных уравнений.
По количеству отличных от нуля элементов матрицу можно разделить на два вида: плотная матрица (или матрица общего вида) и разреженная [1,3]. И именно ее мы будем рассматривать в данной статье.
Часто под разреженными матрицами понимаются матрицы, которые содержат «много» нулевых элементов. Это несколько неясное определение. Совокупность схемы хранения данных в сочетании с соответствующим алгоритмом для выполнения необходимой операции - более корректное определение. Если предложенные схема хранения данных и алгоритм позволяют получить выигрыш по памяти и/или времени по сравнению с обычной схемой хранения (массив) и обычным алгоритмом, то тогда есть смысл говорить о разреженных матрица [1,3].
Решение многих прикладных задач, таких как методы теории графов, методы обработки изображений, численные методы решения дифференциальных уравнений методом конечных элементов, криптографии, логистики и т.п. связано с обработкой матриц большой размерности, имеющих малое число ненулевых элементов. Использование особых способов размещения в памяти разреженных матриц и разработка специальных алгоритмов работы с ними позволяет во многих случаях существенно снизить объем, используемых компьютерных ресурсов, и уменьшить время вычислений. Одним из рациональных способов хранения ненулевых элементов матрицы является массив из динамических списков. Эффективность работы с таким массивом определяется введением класса с продуманным набором методов и создание на этой основе действенных процедур работы с матрицами [2,4].
Простейший пример применения разреженных технологий – задача о поиске всех маршрутов заданной длины.
Рис.1
Задача:дан граф, изображенный на Рис. 1, и необходимо найти количество маршрутов длины 2.
Рис.2
Решение: матрица A, изображенная на Рис. 2 - это матрица смежности [1] данного графа. Тогда, количество маршрутов длины 2 можно определить с помощью матрицы (Рис. 3):
Рис.3
Данную задачу можно решить с помощью разреженных технологий, применяя алгоритм (в данной статье указана лишь первая его часть), указанный ниже:
На входе имеем матрицу A, заданную в РСФ [2].
IA: 1 2 4 6 7 9
JA: 4 1 5 2 4 5 1 3
AN: 1 1 1 1 1 1 1 1
А в результате получаем матрицу C =A2 в разреженном строчном формате:
IC: 1 2 5 7 9 11
JC: 5 1 3 4 1 5 1 3 2 4
AC: 1 1 1 1 1 2 1 1 1 2
Алгоритм по нахождению массивов JC и IC - символический этап:
Разобьём элементы массивов JA и AN следующим образом:
IA: 1 2 4 6 7 9
JA: 41 52 451 3
AN: 11 11 111 1
Введем массив переключателей Y и переключатель P. Число позиций Y равно 5. В начальный момент во все позиции Y засылаем нули. По умолчанию IC всегда начинается с 1.
IC: 1
P=1
Y: 0 0 0 0 0
Просматриваем 1 позицию JA
JA [1] =4 (Смотрим 4-ю строку матрицы A)
Просматриваем 6 позицию JA.
Y: 0 0 0 0 1 JC: 5
IC: 12
P=2
Просматриваем JA с 2 по 3 позиции.
JA [2] =1 (Смотрим 1-ю строку матрицы A)
Просматриваем 1 позицию JA.
Y: 0 0 0 2 1 JC: 54
JA [3] =5 (Смотрим 5-ю строку матрицы A)
Просматриваем 7 и 8 позиции JA.
Y: 2 0 2 2 1 JC: 5413
IC: 125
P=3
Просматриваем JA с 4 по 5 позиции.
JA [4] =2 (Смотрим 2-ю строку матрицы A)
Просматриваем 2 и 3 позиции JA.
Y: 3 0 2 2 3 JC: 541315
JA [5]=4(Смотрим 4-ю строку матрицы A)
Просматриваем 6 позицию JA.
Y: 3 0 2 2 3 JC: 5 4 1 3 1 5
IC: 1257
P=4
Просматриваем 6 позицию JA.
JA[6]=5(Смотрим 5-ю строку матрицы A)
Просматриваем 7 и 8 позиции JA.
Y: 4 0 4 2 3 JC: 5 4 1 3 1 5 1 3
IC: 12579
P=5
Просматриваем JA с 7 по 8 позиции.
JA[7]=1(Смотрим 1-ю строку матрицы A)
Просматриваем 1 позицию JA.
Y: 4 0 4 5 3 JC: 5 4 1 3 1 5 1 3 4
JA[8]=3(Смотрим 3-ю строку матрицы A)
Просматриваем 4 и 5 позиции JA.
Y: 4 5 4 5 3 JC: 5 4 1 3 1 5 1 3 4 2
IC: 1 2 5 7 9 11
Вторая часть алгоритма - численный этап: нахождение массива AN ненулевых элементов матрицы A.
Существует большое разнообразие задач, связанных с путями и маршрутами в графе, начиная от стандартных задач на существование, пересчет и перечисление и заканчивая задачами поиска путей, отвечающих определенным требованиям и т.п.
Теория графов применяется в различных областях современной математики и ее приложениях, в особенности это имеет отношение к экономике, технике, к управлению.
Решение широкого класса задач математической физики, математического программирования, обработки и хранения больших объемов информации сводится к операциям с матрицами очень высоких порядков, для которых непосредственное применение стандартных алгоритмов вычислительной алгебры неприемлемо из-за вычислительной трудоемкости. К счастью, во многих случаях объем вычислительной работы удается значительно сократить, если учесть структурные особенности этих матриц. Одной из таких структурных особенностей является разреженность матрицы.
Таким образом, можно сделать существенный вывод, что разреженные технологии широко применимы на практике. Они позволяют значительно беречь память ЭВМ, уменьшая время на выполнение алгоритмов.
[1] Матрица смежности - квадратная матрица, порядка n, где n – количество вершин графа, такая что M(G)=(
) и 
, где E – множество ребер исходного графа.
[2] РСФ (разреженный строчный формат) – это наиболее используемая форма хранения РМ (разреженной матрицы), где
1) AN– массив ненулевых элементов матрицы A;
2) JA– массив соответствующих столбцовых индексов ненулевых элементов матрицы A;
3) IA– массив переключателей, где i- я компонента указывает, с какой позиции массивов AN и JA начинается описание i- й строки матрицы A.
Библиографическая ссылка
Алашеева Е.А., Рогова Н.В., Туркина Н.Н. ПРИМЕНЕНИЕ РАЗРЕЖЕННЫХ ТЕХНОЛОГИЙ ДЛЯ ПОИСКА МАРШРУТА ДАННОЙ ДЛИНЫ В ГРАФЕ // Международный студенческий научный вестник. – 2018. – № 2. ;URL: https://eduherald.ru/ru/article/view?id=18111 (дата обращения: 20.04.2024).