РАЗРЕЗАНИЕ ГРАФА ИТЕРАЦИОННЫМ МЕТОДОМ СЕЧЕНИЙ

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

Витебский государственный политехнический колледж учреждения образования «Витебский государственный технологический университет»

РАЗРЕЗАНИЕ ГРАФА ИТЕРАЦИОННЫМ МЕТОДОМ СЕЧЕНИЙ

На этапе компоновки радиоэлектронных средств (РЭС) решается задача распределения элементов i-го уровня по элементам (i + 1)-го уровня конструктивной иерархии. На самом низком – первом уровне, находятся минимальные конструктивные единицы – радиоэлектронные компоненты (РЭК) – микросхемы, транзисторы, конденсаторы и т.п., которые в процессе эксплуатации РЭС можно заменить в случае их выхода из строя [1]. Решение данной задачи осуществляется с использованием математической модели принципиальной электрической схемы в виде графа G = (X, U), где множество вершин X – совокупность всех РЭК, входящих в состав проектируемого РЭС, а множество U – совокупность соединений между РЭК в соответствии с принципиальной электрической схемой. Разрезание графа на заданное количество  связанных между собой кусков моделирует процесс компоновки.

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

В данной работе описывается разрезание графа итерационным методом сечений. Описываемый метод использует процедуру отсечения кусков, содержащих заданное количество вершин, и обеспечивает получение наиболее приемлемых результатов при разрезании мультиграфов с большим количеством пар вершин, связанных кратными рёбрами. Разработанный метод основан на использовании результатов направленной оптимизации текущего размещения вершин графа в координатной решётке заданных размеров G_r = s × t, где s – количество узлов координатной решётки по оси абсцисс, t - количество узлов координатной решётки по оси ординат. Математическое обоснование направленной оптимизации размещения графа в решётке подробно описано в [4].

Реализация метода осуществляется в следующем порядке.

1. Исходный граф произвольно отобразить в одномерную координатную решётку G_r = n × 1, где n – количество вершин графа.

2. Построить матрицу смежности графа R = ||r_ij|| и матрицу расстояний между узлами заданной координатной решётки D = ||d_ij|. Шаг решётки, т.е. расстояние между двумя соседними позициями, в которых размещаются вершины графа, принимается равным единице.

3. Вычислить величины приращений суммарной длины связей для всех возможных парных перестановок по формуле [4]:

  (1)

где –  длина связей вершины x_i с вершиной x_m;

 – длина связей вершины x_j с вершиной x_n;

  – длина связей между вершинами x_i и x_j;

M – количество вершин, связанных с вершиной x_i;

N – количество вершин, связанных с вершиной x_j;

 – суммарная длина связей вершин x_i и x_j со всеми остальными вершинами графа до их парной перестановки;

 – суммарная длина связей вершины x_i и x_j со всеми остальными вершинами графа после их парной перестановки.

По результатам полученных вычислений построить матрицу приращений суммарной длины связей для всех возможных парных перестановок.

Отрицательное значение ΔL_ij означает уменьшение суммарной длины связей.

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

- выбранное подмножество перестановок максимально уменьшает суммарную длину связей;

- любая пара вершин из выбранного подмножества не должна иметь связей с другими парами.

Несоблюдение указанных условий может ухудшить результат размещения по сравнению с первоначальным на любой итерации. В [4] приводится ещё одно условие: любая вершина может менять свою позицию только один раз, однако автор в процессе чтения лекций, освещающих вопросы алгоритмизации размещения РЭС по курсу «Системы автоматизированного проектирования», неоднократно доказывал, в том числе и на примерах, что данное условие деструктивно. Недопустимой следует считать повторную перестановку одной и той же пары вершин. Такая перестановка свидетельствует о зацикливании программы для автоматизированного решения задачи размещения из-за текстовой ошибки при её написании. Повторная и, возможно неоднократная, перестановка одной вершины с вершиной (вершинами) из другой пары способствует минимизации суммарной длины связей между размещаемыми элементами любого иерархического уровня [5].

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

6. Повторно вычислить величины приращений суммарной длины связей для всех возможных парных перестановок по формуле (1).

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

7. Провести сечения между всеми рядом расположенными узлами d_i и d_j координатной сетки в диапазоне , где n_min – количество вершин, заданное для наименьшего куска требуемого разрезания.

8. Подсчитать количество рёбер в каждом сечении.

9. Выбрать сечение с минимальным количеством находящихся в нём рёбер. Это сечение будем считать входным.

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

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

11. Удалить из матрицы смежности строки и столбцы, соответствующие выбранным вершинам. В результате будет получена матрица смежности R´.

12. Построить новую матрицу расстояний D´ = ||d´_ij||, размерность которой соответствует размерности матрицы смежности R´.

13. Повторно выполнить действия 3-11. Описанные действия повторяются до тех пор, пока не будет получено заданное разрезание.

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

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

Рис. 1

Решение данной задачи описанным методом выполняется в следующей последовательности.

1) Отобразить граф в координатную решётку размерностью 12 × 1. Результат отображения графа в координатную решётку представлен на рис. 2.

Рис. 2

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

		x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12
	x1	0	0	0	0	0	0	3	1	0	1	0	0
	x2		0	3	4	0	0	0	0	0	0	0	0
	x3			0	1	2	0	0	0	0	0	0	0
	x4				0	0	0	0	0	0	0	0	0
	x5					0	4	0	0	0	0	0	0
R =	x6						0	1	0	1	0	0	0	(2)
	x7							0	1	1	0	1	0
	x8								0	0	4	0	0
	x9									0	0	3	3
	x10										0	0	0
	x11											0	2
	x12												0

3) Построить матрицу расстояний для заданного набора позиций.

		d1	d2	d3	d4	d5	d6	d7	d8	d9	d10	d11	d12
	d1	0	1	2	3	4	5	6	7	8	9	10	11
	d2		0	1	2	3	4	5	6	7	8	9	10
	d3			0	1	2	3	4	5	6	7	8	9
	d4				0	1	2	3	4	5	6	7	8
	d5					0	1	2	3	4	5	6	7
D =	d6						0	1	2	3	4	5	6
	d7							0	1	2	3	4	5
	d8								0	1	2	3	4
	d9									0	1	2	3
	d10										0	1	2
	d11											0	1
	d12												0

Матрица смежности графа R и матрица расстояний между узлами заданной координатной решётки D симметричны, поэтому можно ограничиться треугольными подматрицами, расположенными над главной диагональю.

4) По формуле (1) вычислить величины приращений суммарной длины связей для всех возможных парных перестановок и по результатам вычислений построить матрицу перестановочных коэффициентов. После первой итерации матрица перестановочных коэффициентов имеет вид:

		l1	l2	l3	l4	l5	l6	l7	l8	l9	l10	l11	l12
	l1	0	2	–4	–18	–4	–3	10	11	28	6	22	20
	l2		0	–1	0	9	22	16	42	73	42	75	76
	l3			0	–3	14	18	16	38	64	37	66	67
	l4				0	7	14	16	34	55	32	57	58
	l5					0	4	4	20	38	21	44	47
ΔL =	l6						0	3	12	30	12	32	36
	l7							0	5	16	2	26	24
	l8								0	2	2	2	6
	l9									0	–9	0	5
	l10										0	3	4
	l11											0	1
	l12												0

В полученной матрице ΔL отрицательные перестановочные коэффициенты имеют 7 элементов. Оптимальное для парной перестановки значение имеет элемент ΔL(l₁, l₄) = –18. Парная перестановка вершин x₁ и x₄ сократит суммарную длину связей между вершинами графа на 18 шагов. Больше в матрице ΔL не содержится ни одного отрицательного перестановочного коэффициента, соответствующего вершинам, не связанным с вершинами x₁ и x₄.

5) Переставить в матрице смежности (2) x₁ и x₄ строки и столбцы и повторно вычислить перестановочные коэффициенты для всех возможных парных перестановок вершин графа и пересчитать элементы матрицы приращений. Процедура повторяется до тех пор, пока в матрице приращений не останется ни одного отрицательного элемента.

Для решения данной задачи потребовалось выполнить четыре итерации. По результатам вычислений на второй итерации были переставлены x₉ и x₁₀, на третьей итерации – вершины x₁ и x₆ и на четвёртой итерации – вершины x₆ и x₅. Как видно из результатов выполнения итерационной части описываемого метода, на третьей итерации была повторно переставлена вершина x₁, а на четвёртой итерации – вершина x₆, но эти перестановки были выполнены в паре с другими вершинами. Это подтверждает несостоятельность запрета на повторную перестановку какой-либо вершины в процессе оптимизации текущего размещения вершин графа в узлах координатной решётки, изложенного в [4, с 57].

В результате выполнения парных перестановок было получено отображение графа в решётку, представленное на рис. 3. Суммарная длина связей между вершинами графа сократилась при этом со 102 до 47 шагов.

Рис. 3

6) Провести сечения между соседними узлами координатной решётки. Так как минимальный кусок заданного разрезания графа должен содержать три вершины, то первое сечение следует провести между третьим и четвёртым узлами. Последнее сечение должно быть проведено между девятым и десятым узлами. Данный диапазон соседних узлов координатной решётки, между которыми проводятся сечения, обеспечивает отсчёт количества вершин, заданного для минимального куска, от первого (влево) и от последнего (вправо) узла. Количество соединений между вершинами графа в каждом сечении показано на рис. 3.

7) Минимальное количество рёбер u_min = 2 содержится в сечениях s(d₃, d₄) и s(d₅, d₆). Сечения s(d₃, d₄) и s(d₅, d₆) отсекают влево три и пять вершин соответственно, удаление которых из решётки обеспечивает формирование минимального и максимального куска заданного разрезания. С целью минимизации временных затрат на выполнение процесса разрезания графа рекомендуется выбрать сечение s(d₅, d₆), отсекающее наибольшее количество вершин, входящих в состав одного из формируемых кусков, в данном примере в кусок G₃=(X₃, U₃), где X₃ = {x₂, x₃, x₄, x₅, x₆}.

8) Удалить вершины подмножества X₃ из координатной решётки и соответствующие им строки и столбцы из матрицы смежности (2). Матрица смежности графа после удаления указанных строк и столбцов имеет вид:

		x1	x7	x8	x10	x9	x11	x12
	x1	0	3	1	1	0	0	0
	x7		0	1	0	1	1	0
	x8			0	4	0	0	0
R´ =	x10				0	0	0	0
	x9					0	3	3
	x11						0	2
	x12							0

9) После удаления вершин подмножества X₃ сократился набор позиций координатной решётки для отображения графа G´ = (X´, U´), где X´ = X\X₃. Матрица расстояний D´ имеет вид:

		d1	d2	d3	d4	d5	d6	d7
	d1	0	1	2	3	4	5	6
	d2		0	1	2	3	4	5
	d3			0	1	2	3	4
D´ =	d4				0	1	2	3
	d5					0	1	2
	d6						0	1
	d7							0

Отображение графа в координатную решётку после удаления вершин подмножества X₃ представлено на рис. 4.

Рис. 4

10) Для полученного отображения графа вычислить величины приращений суммарной длины связей для всех возможных парных перестановок и по результатам вычислений построить матрицу перестановочных коэффициентов.

Минимизация суммарной длины связей между вершинами графа G´ была достигнута после первой итерации путём парной перестановки вершин x₉ и x₁₁. Результат представлен на рис. 5.

Рис. 5

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

Минимальное количество рёбер u_min = 2 содержится в сечении s(d₄, d₅), которое отсекает вершины множества X₁ = {x₉, x₁₁, x₁₂}, входящие в первый кусок. Остальные вершины образуют множество X₂ = {x₁, x₇, x₈, x₁₀}, назначаемое во второй кусок. На этом разрезание графа считается законченным. Результат разрезания графа представлен на рис. 6.

Рис. 6

Литература

1. Автоматизация проектирования радиоэлектронных средств : Учеб. пособие для вузов / О.В. Алексеев, А.А. Головков, И.Ю. Пивоваров [и др.] ; под ред. О.В. Алексеева. – М. : Высш. шк., 2000. – 479 с. : ил. – ISBN 5-06-002691-4.

2. Абрайтис, Л.Б. Автоматизация проектирования ЭВМ : Автоматизированное техническое проектирование конструктивных узлов цифровых устройств / Л.Б. Абрайтис, Р.И. Шейнаускас, В.А. Жилевичюс ; под ред. Л.Б. Абрайтиса. – М. : Сов. радио, 1978. – 272 с. : ил.

3. Автоматизация схемотехнического проектирования : Учеб. пособие для вузов / В.Н. Ильин, В.Т. Фролкин, А.И. Бутко [и др.] ; под ред. В.Н. Ильина. – М. : Радио и связь, 1987. – 368 с. : ил.

4. Конструирование и технология печатных плат : Учеб. пособие для радиотехнических специальностей вузов / А.Т. Жигалов, Е.П. Котов, К.Н. Шихаев [и др.]. – М. : Высш. шк., 1973. – 216 с. : ил.

5. Шандриков, А.С. Разрезание графа итерационным методом сечений // IX Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям : 28-30 октября 2008 года, г. Кемерово [Электрон. ресурс] – Режим доступа: http://www.nsc.ru/ws/show_abstract.dhtml?ru+189+14257.