LEC-30 (Материалы к лекциям), страница 3

Если выбрать в качестве стартовой вершину 8, хотя и имеющую минимальную степень, но не являющуюся периферийной, то получается упорядочение, показанное ниже с профилем, также равным 19. Полуширина станет равной 10.

Другие выборы стартовой вершины приводят к следующим результатам: для вершины 4 профиль равен 22, для вершин 5 или 10 профиль опять равен 19; заметим, однако, что эти значения могут зависеть от принятой стратегии разрешения возникающих неопределенностей. Полуширина ленты, получае­мая для указанных трех упорядочений, составляет 6, 5 и 10 соот­ветственно, а для примеров, показанных выше, полуширина равна 6 и 10; видно, что все эти значения превосходят полуширину ленты, равную 4, полученную в результате примене­ния обратного алгоритма Катхилл—Макки. Таким образом, можно заключить, что ценой увеличения ширины ленты удается добиться уменьшения профиля; заметим, что обратный алгоритм Катхилл—Макки не использует эту возможность. Следует, однако, предостеречь от того, чтобы на основе анализа приведен­ных простых примеров прийти к выводу, что алгоритм Кинга всегда работает лучше, чем обратный алгоритм Катхилл—Макки.

Дополнительные сведения

Обратный алгоритм Кинга был предложен Катхиллом в 1972году, однако обнаружилось, что он ничем не лучше исходного алгоритма Кинга. Вариант алгоритма Кинга, предло­женный Леви в 1971, на каждом шаге использует в качестве кандидатов для нумерации вершины как из В, так и из С. Мето­дом Леви можно получать дополнительное уменьшение профиля, однако вычислительные затраты при этом увеличиваются.

Формулировка проблемы минимизации профиля в виде задачи целочисленного программирования [Газз, 1969] была предложена Тьюарсоном в 1967году. Итерационный метод минимиза­ции профиля также был предложен в работе Акьюца и Утку в 1968 году. Этот метод неэкономичен, если использовать его независимо от других подходов, однако он дает неплохие результаты, если доступно хорошее начальное приближение к искомому упорядочению. Таким образом, его можно применять для улуч­шения упорядочений, полученных каким-либо другим методом.

12.4.3. Универсальные разреженные методы.

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

Алгоритм минимальной степени.

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

Логика алгоритма.

Пусть в графе помечены узлы {x1,…,xi-1}. Число ненулевых элементов в этих столбцах графа заполнения в дальнейшем не меняется. Для уменьшения числа ненулевых элементов i-го столбца в еще не факторизованной подматрице на место i-го столбца нужно перевести столбец с наименьшим числом ненулевых элементов. Другими словами алгоритм минимальной степени можно рассматривать, как метод уменьшения заполненности путем локальной минимизации.

Описание алгоритма.

Пусть есть непомеченный граф G₀ = (X,E).

Шаг 1 (инициализация). i←1.

Шаг 2(выбор минимальной степени). В графе исключения G_i-1 = (X_i-1 ,E_i-1) выбрать узел x_i имеющий в G_i-1 наименьшую степень.

Шаг 3 (преобразование графа). Построить новый граф исключения G_i= (X_i,E_i), исключая из G_i-1 узел x_i.

Шаг 4 (цикл или остановка). i←i+1. Если I> |X| - остановка. В противном случае перейти к шагу 2.

В качестве иллюстрации приведем таблицу.

Примечание. На отдельных шагах может быть несколько узлов с минимальной степенью. В таком случае мы выбираем произвольный из таких узлов. Однако различные стратегии выбора в подобной стратегии неоднозначности дают различные варианты алгоритма минимальной степени.