Д. Кнут - Искусство программирования том 1 (1119450), страница 84
Текст из файла (страница 84)
е. циклически связанных строк и столбцов. Каждый узел матрицы имеет длину в три слова и содержит пять полей; Здесь КОН и СОŠ— индексы, обозначающие строку и столбец узла; УАŠ— значение, хранимое в элементе матрицы; БЕАТ и ОР— связи со следующим ненулевым элементом слева в строке или сверху в столбце соответственно. Для каждой строки и каждого столбца заданы заголовки списков ВАЯЕЕОМ[П и ВАЯЕСО1.[1З соответственно. Эти узлы идентифицируются благодаря следующим условиям: СОЕИОС[ВАЯЕЕОМ[П)) < 0 и ЕОУ[ЕОС[ВАЯЕС01.[у1)) < О. Как обычно, в циклическом списке ссылка [.ЕРТ в строке ВАЯЕЕОв [П является ад- ресом крайнего справа значения в этой строке, а ссылка ОР в строке ВАЯЕСОь[,11 указывает на последнее значение в столбце.
Например, матрица 50 0 0 0 10 0 20 0 0 0 0 0 -30 0 — 60 5 (12) при таких условиях будет иметь вид, приведенный на рис. 14. При использовании метода последователыюго распределения памяти для матрицы размера 200 х 200 потребуется 40 000 слов, что гораздо больше размера оперативной памяти большинства компьютеров. Но для представления умеренно разреженной матрицы размера 200 х 200 с помощью описанного выше способа в оперативной памяти компьютера М1Х потребуется только 4 000 слов (см, упр, 11).
При этом время досту па к произвольному элементу А [у, А] также будет вполне приемлемым, если в каждой строке и каждом столбце содержится немного ненулевых (или неодинаковых) элементов. Поскольку в большинстве алгоритмов обработки матриц используется последовательный доступ к элементам, а не произвольный, то при таком связанном представлении данных работа может выполняться гораздо быстрее, чем при последовательном представлении. Типичным примером нетривиального алгоритма работы с разреженными матрицами такого типа является осевое преобрплование (р1еог э1ер), которое является еерт пр Рис. 14. Представление матрицы (12) с узлами в виде Заголовки спнс- йОЧ Сов уАЬ ков находятся слева н сверху важнейшей частью алгоритмов для решения линейных уравнений, обращения ма- триц и решения задач линейного программирования с помощью симплекс-метода.
Осевое преобразование представляет собой следующее преобразование матрицы. Осевой столбец Осевая строка а . б 1/а 6/а -с/а г1 — бс/а (13) Любая другая строка Предполагается, что осевой элемент, а, не равен нулю. Например, применение осевого преобразования к матрице (12), где осевым элементом считается число 10 в строке 2 и столбце 1, приводит к такому результату: — 5 Π— 100 0 01 0 2 0 0 0 0 0 3 0 0 5 (14) До преобразования Любой Осевой другой столбец столбец После преобразования Любой другой столбец Цель данного исследования заключается в создании алгоритма осевой операции для разреженной матрицы, йодобной матрице, представленной на рис. 14.
Ясно, что преобразование типа (13) повлияет только на те строки матрицы, в которых есть ненулевые элементы в осевом столбце, и только на те столбцы матрицы, в которых есть ненулевые элементы в осевой строке. Алгоритм поворота во многом напоминает прямолинейное применение методов связывания, которые рассматривались выше. В частности, он во многом похож на алгоритм 2.2.4А сложения полиномов. Однако существуют дополнительные соображения, которые немного усложняют нашу задачу: если в (13) 6 ф О, с ф О, но Н = О, в представлении разреженной матрицы не будет элемента Н, то его потребуется вставить; а если 6 ~ О, с ф О, б ф О, но а' — 6с/а = О, то придется удалить элемент, который там находился прежде.
Эти операции вставки и удаления более интересны при работе с двумерным массивом, чем с одномерным. Для их выполнения необходимо знать обо всех связях, вовлеченных в данный процесс. Алгоритм обрабатывает все строки матрицы последовательно снизу вверх. Для эффективного выполнения операций вставки и удаления необходимо ввести таблицу указательных переменных РТЕ [)], по одной для каждого рассматриваемого столбца.
С помощью этих переменных совершается обход столбцов по направлению снизу вверх, в результате чего предоставляется возможность обновления соответствующих связей в обоих измерениях. Алгоритм Я (Осееое преобразование разреженной матрицы). Выполним операцию осевого преобразования (13) для матрицы, показанной на рис. 14. Предположим, что Р1ЧОТ вЂ” это переменная связи, которая указывает на осевой элемент.
В алгоритме используется вспомогательная таблица переменных связи РТЕ[у], по одной для каждого столбца матрицы. Предполагается, что переменная АЬРНА и поле ЧАЬ для каждого узла имеют тип числа с плавающей запятой или рационального числа, а все остальные — целочисленный тип. 81. [Инициализация.[ Установить АЬРНА < — 1.0/ЧАЬ(Р1ЧОТ), ЧАЬ(Р1ЧОТ) +- 1.0 и 10 +- НОЧ(Р1ЧОТ), РО +- ЬОС(ВАЯЕНОЧ[10]); 30 +- СОЬ(Р1ЧОТ), 00 +- ЬОС(ВАЯЕСОЬ[ЛО]). Б2.[Обработка осевой строки.] Установить РО +- 1.ЕРТ(РО), Л с- С01.(РО). Если 3 < О, перейти к шагу БЗ (осевая строка пройдена). В противном случае установить РТЕ[Я] +- ЬОС(ВАЯЕСОЬ[3]), ЧАЬ(РО) +- АЬРНА х ЧАЬ(РО) и повторить шаг Б2.
БЗ.[Поиск новой строки.) Установить ОО +- ОР(ОО). (В остальной части алгоритма последовательно снизу вверх перебираются все строки, которые содержат элемент данных в осевом столбце.) Установить 1 < — НОЮ(00). Если 1 < О, выполнение алгоритма прекращается. Если 1 = 10, повторить шаг БЗ (осевая строка обработана). В противном случае установить Р +- ЬОС(ВАЯЕКОЧ[1]), Р1 < — ВЕЮТ(Р). (Указатели Р и Р1 позволяют совершить проход по строке 1 справа налево так же, как РО позволяет это сделать для строки 10. Алгоритм 2.2.4А выполняется аналогично. При этом РО = ЬОС(ВАЯЕНОЫ[10]) ) Б4.
[Поиск нового столбца.) Установить РО +- 1.ЕРТ(РО), 3 +- СОЬ(РО). Если Л < О, установить ЧАЬ(00) +- -АЬРНА х ЧАЬ(00) и вернуться к шагу БЗ. Если 3 = 30, повторить шаг 84. (Таким образом, элемент осевого столбца в строке? обрабатывается после всех элементов других столбцов; причина заключается в том, что значение ЧАЬ(ЦО) потребуется на шаге 87.) 85. [Поиск элемента 1, Л.] Если СОЬ(Р1) > 1, установить Р +- Р1, Р1 <- 1.ЕРТ(Р) и повторить шаг 85. Если СОЬ(Р1) = ), перейти к шагу 87. В противном случае перейти к шагу 86 (вставить новый элемент в столбце 5 строки 1).
86. [Вставка элемента 1, 5.] Если КОМ(ОР(РТЕ[Я])) > 1, установить РТЕ[)) <— ОР(РТЕ[)]) и повторить шаг 86. (Иначе получим КОМ(ОР(РТЕ[,)))) < ?; новый элемент нужно вставить сразу над узлом МОВЕ(РТЕ[))) в вертикальном направлении и слева от узла МОРЕ(Р) в горизонталыюм направлении.) В противном случае установить Х ч= АЧА1Ь, ЧАЬ(Х) +- О, КОМ(Х) < — 1, СОЬ(Х) < — 3, 1ЕРТ(Х) с — Р1, ОР(Х) +- ОР(РТЕ[93), ЬЕРТ(Р) с — Х, ОР(РТК[53) < — Х, Р1+- Х. 87. [Осевое преобразование.! Установить ЧА1. (Р1) +- ЧА1.
(Р1) — ЧА1. (ЦО) х ЧА1. (РО). Если теперь ЧАЬ(Р1) = О, следует перейти к шагу 88. (Замечание. При использовании системы счисления с плавающей запятой условие "ЧАЬ(Р1) = 0" следует заменить условием "]ЧАЬ(Р1)] < ЕРЯ1ЬОМ" или, что еще лучше, условием "большинство значащих цифр ЧАЬ(Р1) утрачено при вычитании",) В противном случае установить РТЕ[5) < — Р1, Р +- Р1, Р1+- ЬЕРТ(Р) и вернуться к шагу 84. 88. [Удаление элемента 1, О.] Если ОР(РТК[53) ф Р1 (или, что, по сути, то же самое, если КОМ(ОР(РТЕ[)) ) ) > 1), установить РТЕ[5] +- ОР(РТЕ[)) ) и повторить шаг 88. В противном случае установить ОР(РТК[5) ) с — ОР(Р1), ЬЕРТ(Р) +- ЬЕРТ(Р1), АЧАЬЬ с.= Р1, Р1 +- ЬЕРТ(Р).
Вернуться к шагу 84. ! Читателю предлагается (в качестве очень поучительного упражнения) самостоятельно создать программу для реализации этого алгоритма (см. упр. 15). Здесь же стоит отметить, что для каждого узла ВАЯЕКОМ[1) и ВАЯЕСОЬ[)) достаточно только одного слова памяти, поскольку большинство их полей не будет востребовано (см. заштрихованные области на рис. 14, а также программу из раздела 2.2.5.) Боле того, в целях дополнительной экономии памяти значение -РТКЦ] можно хранить как КОМ(ЬОС(ВАЯЕСОЬ[33)) Время выполнения алгоритма 8 приблизительно пропорционально количеству матричных элементов, которые вовлечены в операцию осевого преобразования. Такое представление разреженных матриц с помощью ортогональных циклических списков очень поучительно, но специалисты по численному анализу разработали несколько более совершенных методов.
[См., например, работу Ггес( О. Опвтачзоп, АСМ Тгапк оп ЛХагй. Яойжаге 4 (1978), 250-269; а также алгоритмы работЫ с графами и задачами сетевого планирования в главе 7.] УПРАЖНЕНИЯ 1, [17] предложите формулу для 10с(А[у,х)), если А — это матрица типа (1), а каждый ее узел состоят из двух слов, причем все узлы хранятся последовательно в лексикографическом порядке индексов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
