Минимизация внешних связей в процессе разрезания графа последовательным методом

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

Минимизация внешних связей в процессе разрезания графа последовательным методом

УДК 621.3.049.73.75:001.2(024)

Шандриков А.С.

Разрезание графа на отдельные, связанные между собой куски - одна из распространённых графовых задач комбинаторно-логического типа. Решение таких задач, в частности, моделирует процесс компоновки радиоэлектронных средств, то есть разбиения принципиальной электрической схемы на отдельные части. Критерием качественного решения задачи разрезания графа чаще всего является минимум рёбер, соединяющих вершины из разных кусков. Множество таких рёбер называется числом рёберного соединения [1, с. 57]. В физическом смысле число рёберного соединения представляет собой количество внешних связей между кусками графа, сформированными в процессе разрезания.

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

Последовательные алгоритмы являются самыми высокопроизводительными и наиболее экономичными с точки зрения затрат оперативной памяти электронно-вычислительных средств (ЭВС), но и самыми неэффективными по результатам решения задач компоновки с использованием критерия минимума связей между сформированными кусками (внешних связей).

Причина этого недостатка заключается в следующем. В качестве критерия выбора начальной вершины формируемого куска служит минимальное или максимальное значение локальной степени вершины. В большинстве случаев заданному критерию выбора начальной вершины формируемого куска удовлетворяют одновременно несколько вершин. В данной ситуации рекомендуется отдавать предпочтение вершине, имеющей кратные рёбра [2, с. 30], а при наличии нескольких вершин с этой характеристикой выбор осуществляется произвольно [3, с. 386].

Автоматизированное решение задачи разрезания графа исключает возможность произвольного выбора и требует чёткой конкретной формулировки критерия выбора начальной вершины из числа вершин с одинаковыми оценками. Для этой цели можно использовать индекс вершины - младший или старший номер позиции вершины в матрице смежности [4].

После выбора начальной вершины x_i выполняется построение множества Гx_i = {x_i, x_j, …, x_k}, содержащего выбранную начальную вершину x_i и все смежные ей вершины. Мощность полученного множества | Гx_i | сравнивается с количеством вершин, заданным для формируемого куска, и в случае их равенства кусок считается сформированным, а вошедшие в него вершины удаляются из исходного графа. Чаще всего оказывается, что | Гx_i | ? n_m, где m - количество вершин, заданное для формируемого куска.

Если | Гx_i | n_m, то необходимо выполнить следующие шаги [2, с. 31].

Шаг 1. Во множестве Гx_i выбрать вершину x_j, имеющую максимальное количество связей со всеми остальными вершинами множества Гx_i и связанную с вершинами множества X\ Гx_i.

Шаг 2. Построить множество Гx_j.

Шаг 3. Сформировать объединённое множество Гx_i Гx_j-.

Шаг 4 Проверить выполнение условия | Гx_i Гx_j- | = n_m и в случае его невыполнения вновь повторить описанные шаги.

Данный подход к выбору вершины сам по себе создаёт предпосылки для получения неоптимального результата по критерию минимума связей между сформированными кусками. Кроме того, методика дополнения формируемого куска недостающим количеством вершин не содержит точных рекомендаций, необходимых для составления на её основе алгоритма автоматизированного выполнения этой процедуры, а именно:

1) непонятно, как следует поступать, если критерию выбора вершины для дополнения куска соответствуют несколько вершин x_j, x_k Гx_i;

2) по каким критериям следует выбирать вершину x_p X\Гx_i.

Рассмотрим пример.

На рис. 1 представлен кусок G₁ = (X₁, U₁) графа G = (X, U), который необходимо дополнить ещё одной вершиной до значения | X₁ | = 5. На данный момент кусок G₁ содержит 6 внутренних рёбер и 6 внешних.

Рис. 1

Если следовать рекомендациям [2], выполняемым на шаге 1, то в множестве X₁ = {x₁, x₂, x₃, x₄} следует выбрать вершину x₁, имеющую максимальное количество внутренних связей среди вершин с внешними связями, и построить множество Гx₁ = {x₁, x₂, x₄, x₅}. Объединив множества X₁ и Гx₁, получим: графовый комбинаторный автоматизированный

X₁ Гx₁ = _-{x₁, x₂, x₃, x₄, x₅}.

Мощность полученного множества

| X₁ Гx₁ | = 5 = n₁,

следовательно, кусок G₁ = (X₁, U₁) считается сформированным (рис. 2).

Рис. 2

Качество полученного результата можно оценить по коэффициенту разрезания:

Д(G) = L/K,

где L - количество внутренних рёбер формируемого куска;

K - количество внешних рёбер.

В рассматриваемом примере

Д(G₁) = 7/9 = 0,78.

В результате дополнения множества X₁ по методике [2] в формируемый кусок была назначена вершина x₅, в результате чего в кусок G₁ добавилось больше внешних рёбер, чем внутренних. Как видно из приведённого примера, методика [2] не исключает ситуации создания предпосылок для получения неоптимального по количеству внешних связей результата разрезания графа.

Оптимальность результата разрезания графа последовательным методом можно существенно повысить, если изменить критерий выбора вершины для дополнения формируемого куска недостающим количеством вершин. С этой целью выбор вершины x_j для пополнения формируемого куска следует начинать не в самом множестве X₁, как предлагается в [2], а в множестве X\X₁ и использовать для этого числовую характеристику - число связности д(x_j), которое определяется по формуле:

д(x_j) = (x_j) - z(x_j) {x_i | x_j X\X₁, (1)

где (x_j) - количество внешних связей, т.е. количество рёбер, соединяющих вершину x_j X\X₁ с вершинами, ранее назначенными в формируемый кусок;

z(x_j) - количество внутренних связей, т.е. количество рёбер, соединяющих вершину x_j с вершинами множества X\X₁.

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

д(x_j) = max д(x_j), (2)

Для вершин x₅, x₆, и x₇ их связи с вершинами множества X₁ = {x₁, x₃, x₄} являются внешними, а их связи с вершинами множества X\X₁ (вершины этого множества на рис. 1-3 условно не показаны) - внутренними.

В рассматриваемом примере, представленном на рис. 1, числа связности вершин множества X\X₁

д(x₅) = 1 - 4 = -3;

д(x₆) = 3 - 2 = 1;

д(x₇) = 2 - 2 = 0.

Критерию (2) удовлетворяет вершина x₆, и, согласно предлагаемой в данной работе методике, она и назначается в формируемый кусок (рис. 3).

Рис. 3

Коэффициент разрезания в этом случае Д(G₁)ґ = 9/5 = 1,8.

По сравнению с Д(G₁) коэффициент разрезания Д(G₁)ґ увеличился в 2,3 раза. Количество внешних связей между формируемым куском и вершинами множества X\X₁ сократилось на три.

Если критерию (2) удовлетворяют одновременно несколько вершин, то из них следует назначить в формируемый кусок вершину с большей локальной степенью, т.е. с большим значением (x_j), x_j X\X₂. Покажем это на следующем примере.

На рис. 4 представлен кусок G₂ = (X₂, U₂) графа G = (X, U), который необходимо дополнить ещё одной вершиной.

Рис. 4

Критерию (2) удовлетворяют две вершины: x₆ и x₈, у которых числа связности

д(x₆) = 3 - 2 = 1;

д(x₈) = 5 - 4 = 1.

Если в кусок G₂ назначить вершину x₆, имеющую меньшую локальную степень, то количество внутренних связей в куске увеличится на три, а количество внешних связей уменьшится на одну (рис. 5). Коэффициент разрезания будет равен Д(G₂) = 9/10 = 0,9.

Рис. 5

При назначении в кусок G₂ вершины x₈ с большей локальной степенью количество внешних связей также уменьшится на одну, но зато количество внутренних связей увеличится на пять (рис. 6).

Рис. 6

Коэффициент разрезания в этом случае будет равен Д(G₂)ґ = 11/10 = 1,1, что в 1,22 раза больше по сравнению с коэффициентом разрезания Д(G₂).

В процессе формирования куска также может возникнуть ситуация, когда из куска необходимо удалить лишнюю вершину или несколько вершин, т.е. когда | Гx_i | n_i. В этом случае для удаления рекомендуется выбирать вершину с минимальным количеством внутренних рёбер [2]. Если лишних вершин несколько, то удаление производится поочерёдно несколькими шагами, по одной вершине на каждом шаге.

Данный критерий выбора удаляемой вершины также нельзя назвать удачным. Как и в предыдущем случае, из [2] неясно, как поступать, если данному критерию удовлетворяют несколько вершин. Предположим, что из формируемого куска G₃ = (X₃, U₃), содержащего 10 внутренних и 6 внешних рёбер, необходимо удалить одну лишнюю вершину (рис. 7).

Рис. 7

Минимальное количество внутренних рёбер z(x_i) имеет единственная вершина x₄. Согласно [2, 3], именно эта вершина должна быть удалена из формируемого куска. В результате удаления вершины x₄ (рис. 8) коэффициент разрезания формируемого куска будет равен Д(G₃) = 8/7 = 1,14.

Рис. 8

Если проанализировать рассматриваемую ситуацию, то можно заметить, что удаление из формируемого куска G₃ вершины x₁ обеспечит более приемлемый результат разрезания графа за счёт того, что ей инцидентно большее количество внешних рёбер, чем вершине x₄. Очевидно, что и в этом случае следует изменить методику выбора удаляемой вершины и такой методикой, как и в предыдущем случае, может стать выбор вершины для удаления по числу связности:

д(x_i) = (x_i) - z(x_i) {x_i | x_i X₃. (3)

Из (3) следует, что наиболее оптимальный результат по критерию минимизации внешних связей обеспечит удаление из куска G₃ вершины x_i X₃, удовлетворяющей условию

д(x_i) = max д(x_i), (4)

Критерию (4) удовлетворяет вершина x₁. Результат удаления этой вершины из куска G₃ представлен на рис. 9.

Рис. 9

Коэффициент разрезания Д(G₃)ґ = 7/4 = = 1,75 и по сравнению с Д(G₃) увеличился в 1,54 раза, а количество внешних связей между формируемым куском и вершинами множества X\X₁ сократилось на три.

В [4] описано разрезание графа методом последовательного назначения вершин в формируемые куски. При разрезании графа на неравные по количеству вершин куски данным методом формирование первого куска выполняется до получения | X₁ | = min n_i, где n_i - количество вершин в наименьшем куске заданного разрезания. Производится вычисление текущего коэффициента разрезания и формирование куска продолжается до следующего в порядке возрастания количества вершин, вновь вычисляется коэффициент разрезания и так далее до тех пор, пока не будут рассмотрены все варианты с разным количеством вершин в куске графа. Окончательно выбирается тот вариант, который соответствует максимальному значению коэффициента разрезания. Сформированный кусок удаляется из исходного графа, и описанная процедура повторяется для формирования каждого следующего куска графа. Для оценки вариантов приходится часто вычислять коэффициент разрезания. В результате многочисленных разрезаний графов методом [4] было установлено, что не во всех случаях удаётся получить оптимальный по критерию минимума внешних связей результат. Было выявлено неочевидное на первый взгляд обстоятельство: коэффициент разрезания не является объективным показателем качества по критерию минимума внешних связей в процессе выбора приемлемого с практической точки зрения варианта формируемого куска. При оценке различных вариантов увеличение коэффициента разрезания может иметь место при большем приращении внешних связей по сравнению с приращением внутренних связей формируемого куска графа.

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

Рис. 10

Текущий коэффициент разрезания

Д(G⁽¹⁾) = l/k = 2/7 = 0,286.

Необходимо рассмотреть ещё один вариант формируемого куска, в котором будут находиться четыре вершины и из них выбрать лучший вариант на данной стадии разрезания графа. С этой целью согласно [4] для всех внешних вершин было определено число связности и в соответствии с алгоритмом в формируемый кусок назначена вершина x₄ (рис. 11).

Рис. 11

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

Д(G⁽²⁾) = 3/9 = 0,333.

Результаты проведённого анализа показывают, что для количественной оценки возможных вариантов формируемого куска в процессе разрезания графа методом [4] вместо коэффициента разрезания следует использовать разность между количеством внешних и количеством внутренних связей:

е(r) = k - l = min(k - l)

Очевидно, что при использовании данного критерия в качестве окончательного варианта был бы выбран кусок G⁽¹⁾, представленный на рис. 10.

Выводы

1) разрезание графа последовательным алгоритмом по предлагаемой методике, то есть с использованием чисел связности, позволяет минимизировать количество внешних связей между сформированными кусками. Это способствует улучшению эксплуатационных параметров проектируемых РЭС и повышает технологичность их производства;

2) для оценки промежуточных вариантов формируемых кусков целесообразно использовать критерий минимальной разности между количеством внешних и внутренних рёбер.

Литература

1. Мелихов А.Н. Применение графов для проектирования дискретных устройств /А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик - М. : Наука, 1974 - 304 с.

2. Методы разбиения схем РЭА на конструктивно законченные части / К.К. Морозов [и др.]; под ред. К.К. Морозова. - М.: Сов. радио, 1978 - 136 с.

3. Автоматизация проектирования радиоэлектронных средств: Учеб. пособие для вузов / О.В. Алексеев [и др.]; под ред. О.В. Алексеева. - М.: Высшая школа, 2000. - 479 с.

4. Шандриков А.С. Последовательный метод разрезания графа с минимизацией внешних связей / А.С. Шандриков // Вестник Учреждения образования «Витебский государственный технологический университет» Пятый выпуск / УО «ВГТУ». - Витебск, 2003. С. 94-100.

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