Разрезание графа формированием инвариантных конечных массивов

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

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

Разрезание графа формированием инвариантных конечных массивов

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

Методика решения задач компоновки основана на применении математических моделей в виде графа G = (X, U), где X - множество вершин, обозначающих множество радиоэлектронных компонентов (РЭК), а U - множество связей между ними в соответствии с принципиальной электрической схемой. В результате задача компоновки сводится к решению задачи по разрезанию графа на требуемое количество кусков с заданным количеством вершин в каждом из них.

Для решения задачи компоновки граф представляется в виде матрицы смежности, матрицы цепей, матрицы инцидентности и др. [2]. Компоновка осуществляется обработкой матриц разработанными алгоритмами. На практике чаще всего используются последовательные и итерационные алгоритмы. Последовательные алгоритмы привлекают своей простотой и производительностью, однако в большинстве случаев не обеспечивают оптимальных результатов, что является их основным недостатком. Причина данного недостатка объясняется отсутствием в последовательных алгоритмах каких-либо операций, способствующих минимизации внешних связей между сформированными кусками непосредственно в процессе разрезания графа [3].

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

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

1) Построить матрицу смежности.

2) Определить количество ненулевых элементов в каждой строке матрицы смежности.

3) Выделить все возможные конечные массивы, содержащие по n_i = в(x_i) - 1, n_j = в(x_j) - 1, … вершин, где n_i, n_j, … - заданное количество вершин в формируемых кусках.

4) Для каждого полученного массива определить коэффициент связности по формуле Д(G_i) = Уl_ii/K_ij где Уl_ii - количество внутренних связей в i-м массиве, K_ij - количество внешних связей i-го массива с остальными вершинами графа.

5) Выбрать конечный массив Гx_i с максимальным значением коэффициента разрезания Д(G_i) и назначить его в один из заданных кусков, для которого выполняется условие з_j = |Гx_i|, где |Гx_i| - мощность выбранного конечного массива Гx_i.

Возможны ситуации, когда максимальный коэффициент разрезания Д(G_i) будут иметь одновременно несколько конечных массивов. В этом случае данные конечные массивы можно распределить по нескольким формируемым кускам при соблюдении условия Гx_i ? Гx_j ? Г x_k = 0.

Описываемый метод разрезания графа, также как и метод [3], неплохо зарекомендовавший себя при решении задач компоновки, предусматривает возможность более гибкого принятия решения по формированию кусков заданного разрезания. Данная методика создаёт предпосылки для получения наиболее оптимального по критерию Д(G_i) = max результата разрезания и заключается в следующем. При разрезании графа на неравные по количеству вершин куски, назначение выбранного конечного массива с максимальным коэффициентом связности в один из формируемых кусков не рассматривается как окончательный результат. Выбранный конечный массив следует дополнить (и / или сократить) его до следующего (предыдущего) в порядке возрастания (и / или убывания) количества вершин. Для каждого полученного промежуточного варианта также подсчитывается коэффициент разрезания. Окончательный вариант формирования куска графа выбирается по максимальному значению промежуточного коэффициента разрезания. Если имеется несколько одинаковых максимальных значений промежуточных коэффициентов разрезания, то формируется кусок, содержащий наибольшее по мощности множество вершин. Например, граф необходимо разрезать на четыре куска G₁, G₂, G₃ и G₄ по 5, 7, 8 и 10 вершин соответственно. Предположим, что мощность конечного массива с максимальным коэффициентом разрезания равна 7. Формально этот конечный массив может быть назначен во второй кусок G₂. Однако, для минимизации внешних связей в заданном разрезании, необходимо из выбранного конечного массива поочерёдно удалить две вершины (до значения |Гx_i| = 5) и дополнить его сначала до значения |Гx_i| = 8, а затем и до значения |Гx_i| = 10. При этом используются приёмы, изложенные в [1] и [2]. Для каждого из полученных значений |Гx_i| подсчитываются промежуточные коэффициенты разрезания. Окончательный вариант формирования куска выбирается по максимальному значению промежуточного коэффициента разрезания. В результате такого аналитического выбора может оказаться, что, например, в первый кусок вошли 8 вершин, а не 5, во второй - 5, а не 7, в третий - 10 и в четвёртый - 8 вершин. Формально приведённый в качестве примера окончательный результат разрезания графа отличается от заданного, но принципиально он удовлетворяет требованиям задания. Отличие состоит лишь в изменении номеров (индексов) кусков графа.

6) Сформированный кусок (куски) удаляется из исходного графа. Описанные действия повторяются до тех пор, пока не будет сформирован предпоследний кусок заданного разрезания.

Реализацию описанного метода рассмотрим на следующем примере.

На рис. 1 представлен граф G = (X, U), у которого |X| = 12, |U| = 35.

Рис. 1

Требуется: разрезать граф на три куска G₁, G₂ и G₃ содержащие n₁ = 3, n₂ = 4 и n₃ = 5 вершин.

Порядок решения задачи следующий.

1) Построить матрицу смежности.

радиоэлектронный граф технический

2) Определить количество ненулевых элементов в каждой строке матрицы смежности R₁. Количество ненулевых элементов указано в дополнительном столбце в(x_i) матрицы смежности R₁.

3) Сформировать конечные массивы, содержащие заданные количества вершин n₁, n₂ и n₃ для кусков G₁, G₂ и G₃. Для этого:

а) из матрицы смежности R₁ выделить вершины, соединённые с в(x_i) = n₁ - 1 = 3 - 1 = 2, в(x_i) = n₂ - 1 = 4 - 1 = 3 и в(x_i) = n₃ - 1 = 5 - 1 = 4 смежными вершинами. С двумя смежными вершинами соединены вершины x₂, x₄, x₅, x₁₀ и x₁₂. С тремя смежными вершинами соединены вершины x₁, x₃, x₆, x₈, x₉ и x₁₁. С четырьмя смежными вершинами соединена вершина x₇.

б) построить множества, содержащие выбранные вершины и все смежные им вершины. Тем самым будут сформированы конечные массивы, содержащие по n₁ = 3, n₂ = 4 и n₃ = 5 вершин, что соответствует заданному разрезанию.

X₁^I = {x₂, x₃, x₄};

X₁^II = {x₄, x₂, x₃};

X₁^III = {x₅, x₃, x₆};

X₁^IV = {x₁₀, x₁, x₈};

X₁^V = {x₁₂, x₉, x₁₁};

X₂^I = {x₁, x₇, x₈, x₁₀};

X₂^II = {x₃, x₂, x₄, x₅};

X₂^III = {x₆, x₅, x₇, x₉};

X₂^IV = {x₈, x₁, x₇, x₁₀};

X₂^V = {x₉, x₆, x₁₁, x₁₂};

X₂^VI = {x₁₁, x₇, x₉, x₁₂};

X₃^I = {x₇, x₁, x₆, x₈, x₁₁}.

В перечисленной группе конечных массивов можно выделить равные множества вершин: X₁^I = X₁^II и X₂^I = X₂^IV, следовательно, массивы X₁^II и X₂^IV можно не рассматривать.

Графические изображения конечных массивов, выделенных для формирования заданных кусков графа, представлены на рис. 2-11.

Рис. 2. Массив X₁^I

Рис. 3. Массив X₁^III

Рис. 4. Массив X₁^IV

Рис. 5. Массив X₁^V

Рис. 6. Массив X₂^I

Рис. 7. Массив X₂^II

Рис. 8. Массив X₂^III

Рис. 9. Массив X₂^V

Рис. 10. Массив X₂^VI

радиоэлектронный граф технический

Рис. 11. Массив X₃^I

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

Д(G₁^I) = 8/2 = 4;

Д(G₁^III) = 6/6 = 1;

Д(G₁^IV) = 5/6 = 0,83;

Д(G₁^V) = 8/2 = 4;

Д(G₂^I) = 9/2 = 4,5;

Д(G₂^II) = 10/4 = 2,5;

Д(G₂^III) = 6/12 = 0,5;

Д(G₂^V) = Д(G₂^VI) = 9/5 = 1,8;

Д(G₃^I) = 7/15 = 0,47.

4) Наибольший коэффициент разрезания Д(G₂^I) = 4,5 имеет конечный массив X₂^I = {x₁, x₇, x₈, x₁₀}. Этот массив предварительно назначаем во второй кусок G₂ = (X₂, U₂) заданного разрезания, где X₂ = X₂^I = {x₁, x₇, x₈, x₁₀}.

5) Граф G = (X, U) разрезается на неравные по количеству вершин куски, поэтому следует произвести проверку оптимальности выбранного результата. Полученный результат n₁ = 3 < |X₂| = 4 < n₃ = 5 означает, что из множества X₂ можно удалить одну вершину, получив в результате |X₁| = n₁ = 3, или дополнить множество X₂ ещё одной вершиной до |X₃| = n₃ = 5. Если в результате описанных преобразований кусок G₁ = (X₁, U₁) или G₃ = (X₃, U₃) будет иметь больший коэффициент разрезания, чем текущий Д(G₂) = 10/4 = 2,5, то именно этот кусок и будет считаться окончательно сформированным.

а) Для уменьшения куска G₂ до трёх вершин необходимо выбрать в множестве X₂ вершину с инцидентными ей внешними рёбрами и с максимальным числом связности б(x_i). В множестве X₂ внешние рёбра имеет только вершина x₇: |U_7внешн| = 2, количество внутренних рёбер |U_7внутр| = 3, следовательно, удаление вершины x₇ из множества X₂ уменьшит коэффициент разрезания.

б) Для дополнения множества x2 ещё одной вершиной (до |X₃| = 5) необходимо выбрать из множества X\X₂ вершину x_j, связанную с вершинами множества X₂ и также имеющую максимальное число связности б(x_i). В рассматриваемом примере с вершиной x₇ X₂ связаны вершины x₆, x₁₁ X\X₂. Числа связности этих вершин равны: б(x₆) = б(x₁₁) = 1 - 5 = -4. Назначение в кусок G₂ любой из этих вершин увеличит количество внутренних связей на 1, а внешних - на 5, т.е. коэффициент разрезания уменьшится и станет равным 1,67. Следовательно, сформированный кусок G₂ = (X₂, U₂) является оптимальным по критерию минимума внешних связей.

6) Удалить из матрицы смежности R₁ строки и столбцы x₁, x₇, x₈, x₁₀. В результате будет получена матрица смежности R₂.

7) Определить количество ненулевых элементов в каждой строке матрицы смежности R₂.

8) Сформировать конечные массивы, содержащие заданные количества вершин n₁ и n₃ для кусков G₁ и G₃. Для этого выбираем по матрице смежности R₂ вершины, у которых в(x_i) = 2 и в(x_i) = 4: x₂, x₄, x₅, x₆, x₁₁ и x₁₂. Перечисленные вершины имеют в(x_i) = 2, вершин, у которых в(x_i) = 4 в матрице смежности R₂ нет.

9) Построить множества, содержащие выбранные вершины и все смежные им вершины.

Y₁^I = {x₂, x₃, x₄};

Y₁^II = {x₄, x₃, x₂};

Y₁^III = {x₅, x₃, x₆};

Y₁^IV = {x₆, x₅, x₉};

Y₁^V = {x₁₁, x₉, x₁₂};

Y₁^VI = {x₁₂, x₉, x₁₁};

В данной группе конечных массивов имеются равные множества вершин: Y₁^I = Y₁^II и Y₁^V = Y₁^VI, поэтому массивы Y₁^II и Y₁^VI рассматриваться не будут.

Графические изображения конечных массивов Y₁^I, Y₁^III, и Y₁^V, выделенных для формирования первого и третьего кусков, представлены на рис. 2, 3 и 5, соответственно, а конечного массива Y₁^IV - на рис. 12.

Рис. 12. Массив Y₁^IV

10) Определить коэффициенты разрезания полученных конечных массивов:

Д(G₁^I) = 8/2 = 4;

Д(G₁^III) = 6/6 = 1;

Д(G₁^IV) = 5/9 = 0,55;

Д(G₁^V) = 8/2 = 4;

11) Наибольший коэффициент разрезания имеют конечные массивы Y₁^I = {x2, x3, x4} и Y₁^V = {x₉, x₁₁, x₁₂}. Оба эти множества вершин обладают одинаковым правом на назначение в формируемый кусок G₁. Окончательный выбор будет сделан после анализа каждого варианта.

12) Первый вариант. В кусок G₁ назначается множество X_1-1 = {x₂, x₃, x₄}. Мощность этого множества | X_1-1| = 3 = n₁. Дополним это множество до значения его мощности n₃ = 5. С множеством X_1-1 связана всего одна вершина из оставшегося множества вершин - это вершина x₅. Включив эту вершину в состав множества X_1-1, получим: X_1-1^* = {x₂, x₃, x₄, x₅}. С множеством X_1-1^* также связана единственная вершина x₆, поэтому безальтернативно назначаем её в это множество и получим множество вершин X_3-1 = {x₂, x₃, x₄, x₅, x₆}, которое может образовать кусок G₃ заданного разрезания графа. Коэффициент разрезания для первого варианта куска Д(G_3-1) = 14/2 = 7. Полученный результат показывает, что на данном этапе разрезания графа целесообразно осуществить формирование куска G₃ = (X_3-1, U_3-1), где X_3-1 = {x₂, x₃, x₄, x₅, x₆}.

Второй вариант. В кусок G₁ назначаем множество X_1-2 = {x₉, x₁₁, x₁₂} и тоже дополним его до мощности n₃ = 5. С множеством X_1-2 связана единственная вершина x₆ из оставшегося множества вершин. После включения её в множество X_1-2, получим: X_1-2^* = {x₆, x₉, x₁₁, x₁₂}. Далее, в множество X_1-2 назначаем вершину x₅, также единственную, связанную с этим множеством, и получим X_3-2 = {x₅, x₆, x₉, x₁₁, x₁₂}. Коэффициент разрезания для второго варианта куска Д(G_3-2) равен 13/3 = 4,33. Результат, полученный во втором варианте, также показывает, что на данном этапе оптимальным решением будет формирование куска G₃ = (X_3-2, U_3-2), где X_3-2 = {x₅, x₆, x₉, x₁₁, x₁₂}.

По результатам анализа двух вариантов состава куска G₃ окончательно выбираем первый вариант, так как Д(G_3-1) = 7 > Д(G_3-2) = 4,33, и считаем, что на данном этапе разрезания графа сформирован третий кусок G₃ заданного разрезания, содержащий множество вершин X₃ = {x₅, x₆, x₉, x₁₁, x₁₂}.

13) Так как сформированный кусок G₃ был предпоследним куском заданного разрезания, то оставшееся множество вершин автоматически образует множество вершин последнего (в порядке формирования) куска G₁ = (X₁, U₁), где X₁ = {x₉, x₁₁, x₁₂}.

Результат разрезания графа представлен на рис. 13.

Рис. 13

Коэффициент полученного разрезания Д(G) = 32/3 = 10,67.

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

Данный метод имеет и ещё одно преимущество: он позволяет сократить объём оперативной памяти, необходимый для решения задачи. Это объясняется тем, что при формировании конечных массивов вместо матрицы смежности можно использовать таблицу её кодовой реализации R_k или применить в качестве описания графа метод соответствий [1].

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

Литература

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

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

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

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