6CAD-CAE-23 Упорядочение (1014142), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Опять отмечаем, что эффективность алгоритма упорядочения критическим образом зависит от выбора начального узла.

Возьмем в качестве начального узла узел 3.

Мы видим, что, выбирая в качестве начального периферийный узел, получили наилучший результат. Отметим это обстоятельство.

Результаты применения обратного алгоритма Катхилла и Макки к примеру 2, рассмотренного при обсуждении прямого алгоритма Катхилла и Макки приведены ниже.

Матрицы, получившиуся в результате переупорядочения.

Для левой – полуширина равна 4, а профиль -24. Для правой полуширина также равна 4, а профиль стал равным 23.

Алгоритм Кинга. (King, 1970).

Этот алгоритм уменьшает профиль путём локальной минимизации ширины фронта. Его можно описать следующим образом.

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

Определить псевдопериферийный узел r и положить x₁ ← r.

Шаг 2 (основной цикл).

Для i=1,…..,N-1 найти узел , для которого величина

минимальна. Пометить узел y как x_i+1.

Шаг 3 (выход). Упорядочение Кинга есть x₁, x₂, ….., x_N.

Приведём другое изложение алгоритма Кинга.

Выбираем вершину, имеющую минимальную степень, и присваиваем ей номер 1. Множество вершин разбивается теперь на три подмножества: А, В к С. Множество А состоит из всех уже пронумерованных вершин графа. Множество В определяется как смежное по отношению к А, т. е. В = Adj (А) и, таким образом, состоит из всех вершин, которые смежны какой-либо вершине из А. Множество С состоит из всех остальных вершин. Тогда на каждом шаге алгоритма следующей нумеруется та вершина под­множества В, которая ведет к присоединению наименьшего коли­чества вершин из С к множеству В. После того как очередная вер­шина выбрана, производится соответствующее переопределение множеств А, В и С. Если граф не является связным, то алгоритм можно применять отдельно к каждой из его связных компонент.

Рассмотрим ранее использовавшийся для иллюстрации алгоритма Катхилла и Макки пример 2 (матрицу и граф). Напомним, что полуширина этой матрицы равна 9, а профиль-40.

Здесь минимальную степень имеют вершины 1, 10, 6, 2, 4, 8 и 5. Выбираем вершину 1 в качестве стар­товой (эта вершина является также периферийной) и

Исходная матрица и её граф

помечаем ее как первую. Исходная нумерация указывается цифрами внутри кружков, а новая — цифрами рядом с кружками. Отсутствие новой нумерации свидетельствует о том, что номер не изменился. На первом шаге три введенные выше множества определяются следующим образом (в терминах исходной нумерации):

А ={1}, В = {6, 10}, С = {все остальные вершины}.

Матрица, получившаяся в результате переупорядочения.

Таким образом, кандидатами для нумерации служат вершины 6 и 10. Если следующей пронумеровать вершину 6, то в множество В будет включена вершина 9, а если взять вершину 10, то к мно­жеству В тоже присоединится одна вершина 11. Возникшая неопре­деленность разрешается произвольным образом, и мы выбираем ту возможность, когда вершина 6 нумеруется в качестве второй. Переопределяя теперь множества А , В и С, получаем

А = (1, 6}, В = {9, 10}, С = (все остальные вершины}.

Теперь мы должны пронумеровать вершину 10, так как в этом случае к множеству В присоединяется лишь одна вершина 11 и т.д. Получающаяся в резуль­тате переупорядочения матрица показана выше. Ее про­филь равен 19, полуширина равна 6.

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

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

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

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

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

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

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

Характеристики

Список файлов лекций