Применение разреженных технологий для поиска маршрута данной длины в графе

Размещено на http://www.allbest.ru/

Применение разреженных технологий для поиска маршрута данной длины в графе

Алашеева Е.А.

Рогова Н.В.

Туркина Н.Н.

Часто при математическом моделировании какого-либо экономического процесса требуется решить транспортную задачу. Например, требуется найти маршрут оптимальной длины, выделить все маршруты данной длины, найти минимальный маршрут. Для данных целей удобнее всего использовать методы теории графов. При построении математической модели реального маршрута матрица смежности моделируемого графа получается очень больших размеров. Такую матрицу неудобно хранить в памяти компьютера. Поскольку у таких матриц, как правило, много нулевых элементов, то эффективно использовать технологии разреженных матриц в данном случае. В данной работе приведён пример использования разреженных технологий для отыскания всех маршрутов данной длины у графа и разработан алгоритм решения данной задачи. Существует большое разнообразие задач, связанных с путями и маршрутами в графе, начиная от стандартных задач на существование, пересчет и перечисление и заканчивая задачами поиска путей, отвечающих определенным требованиям и т.п. Теория графовшироко применяется в различных приложениях современной математики, в особенности это имеет отношение к экономике, технике, к управлению.Однако, во многих случаях объем вычислительной работы удается значительно сократить, если учесть структурные особенности этих матриц. Одной из таких структурных особенностей является разреженность матрицы. Таким образом, можно сделать существенный вывод, что разреженные технологии широко применимы на практике. Данные технологии позволяют значительно беречь память ЭВМ, уменьшая время на выполнение различных алгоритмов, моделирующих те или иные процессы.

«Матрица» как термин имеет много значений. В различных областях науки этот термин даже звучит по-разному, например: в математике - таблица чисел; в электронике - набор проводников и т.д. [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. Алашеева Е.А. Алгоритм построения системы линейных алгебраических уравнений с псевдоразреженной матрицей при решении электродинамической задачи методом интегральных уравнений. Наука и Мир. 2014. Т. 1. № 12 (16). С. 10-12.

2. Вержбицкий В.М., «Основы численых методов», -М.: Высшая школа, 840с. (2005)

3. Рогова Н.В. Разреженные аппроксимации матриц. Наука и мир. Международный

научный журнал, № 2(18), 2015. Том 1. г. Волгоград. С. 29-32.

4. ТурчакЛ.И., Плотников П.В., «Основы численных методов»,-М.: ФИЗМАТЛИТ, 304с. (2003)

Размещено на Allbest.ru