ОПТИМИЗАЦИЯ ПРОИЗВОЛЬНОГО РАЗМЕЩЕНИЯ ГРАФА В КООРДИНАТНОЙ РЕШЁТКЕ С ИСПОЛЬЗОВАНИЕМ ГРУППОВЫХ ПЕРЕСТАНОВОК

Психология и педагогика

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

Шандриков Анатолий Сергеевич

28 января 2021

448

Содержимое публикации

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

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

ОПТИМИЗАЦИЯ ПРОИЗВОЛЬНОГО РАЗМЕЩЕНИЯ ГРАФА В КООРДИНАТНОЙ РЕШЁТКЕ С ИСПОЛЬЗОВАНИЕМ ГРУППОВЫХ ПЕРЕСТАНОВОК

Для любой пары вершин x_i и x_j, занимающих текущие позиции d_i и d_j соответственно, по матрице смежностиR и матрице расстояний D можно подсчитать суммарную длину их связей

(1)

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

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

Если выполнить перестановку этой пары вершин, то вершина x_i переместится в позицию d_j, а вершина x_j – в позицию d_i. В этом случае суммарная длина их связей

(2)

Изменение суммарной длины связей вершин x_i и x_j определяется по формуле

(3)

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

Работа алгоритма производится циклически. В течение одного цикла:

1) по формуле (3) вычисляются величины приращений суммарной длины связей для всех возможных парных перестановок и строится матрица приращений;

2) из множества пар вершин, перестановка которых даст отрицательные приращения суммарной длины связей, выделяется некоторое подмножество, которое должно удовлетворять следующим условиям [1]:

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

2.2) любая вершина может менять свою позицию только один раз;

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

Несоблюдение условий 2.2 и 2.3 (особенно 2.3) может ухудшить результат размещения по сравнению с первоначальным на любой итерации.

Алгоритм реализации описанного метода содержит следующие шаги:

Шаг 1. Построить матрицу расстояний D=||d_ij||, исходя из заданных параметров решетки. Перейти на шаг 2.

Шаг 2. Построить матрицу смежности R=||r_ij|| графа G=(X,U). Перейти на шаг 3.

Шаг 3. Вычислить матрицу приращений ΔL=||Δl_ij||_n по формуле (3). Перейти на шаг 4.

Шаг 4. Проверить наличие в матрице приращений отрицательных элементов. Если отрицательные элементы обнаружены, то перейти на шаг 5, в противном случае – на шаг 7.

Шаг 5. По отрицательным элементам матрицы приращений выбрать подмножества парных перестановок. При этом вершины одного подмножества (пары) не должны иметь связей с вершинами из любого другого подмножества. Перейти на шаг 6.

Шаг 6. Переставить в матрице смежности R строки и столбцы, соответствующие выбранным вершинам подмножеств. Перейти на шаг 3.

Шаг 7. Вывод результатов размещения. Перейти на шаг 8.

Шаг 8. Конец работы алгоритма.

Работу алгоритма рассмотрим на примере.

Рис. 1

Пример. На рис 1 представлено произвольное размещение графа G=(X,U) в решетку G_r= 4х3. Вершины x₁,x₂,…,x₁₂ занимают позиции d₁,d₂, …, d₁₂ соответственно. Задача: оптимизировать размещение графа с целью минимизации суммарной длины связей.

Решение

Построить матрицу расстояний для решетки G_r= 4x3.

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	ρ(x_i)
	x₁	0	0	0	0	0	0	2	0	2	0	1	0	5
	x₂	0	0	0	0	0	0	0	0	0	1	0	1	2
	x₃	0	0	0	1	2	0	0	1	1	0	0	0	5
	x₄	0	0	1	0	0	1	0	2	1	0	0	0	5
	x₅	0	0	2	0	0	0	2	1	0	0	1	0	6
R =	x₆	0	0	0	1	0	0	0	1	0	0	0	0	2	(4)
	x₇	2	0	0	0	2	0	0	0	1	1	0	0	6
	x₈	0	0	1	2	1	1	0	0	0	0	0	1	6
	x₉	2	0	1	1	0	0	1	0	0	0	0	0	5
	x₁₀	0	1	0	0	0	0	1	0	0	0	0	1	3
	x₁₁	1	0	0	0	1	0	0	0	0	0	0	3	5
	x₁₂	0	1	0	0	0	0	0	1	0	1	3	0	6

Вычислить матрицу приращений суммарной длины связей по формуле (3). Матрица приращений имеет вид:

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	(5)
∆L=	x₁	0	1	-4	6	-3	-4	-3	4	-6	-4	6	7
	x₂		0	-1	0	-4	-2	-6	0	-11	0	1	8
	x₃			0	2	-3	-6	-1	2	-4	-2	4	3
	x₄				0	-6	-1	4	1	6	0	2	6
	x₅					0	-4	-14	4	-1	0	1	2
	x₆						0	-8	2	-2	1	2	-2
	x₇							0	6	-9	-2	3	6
	x₈								0	6	5	4	8
	x₉									0	2	0	5
	x₁₀										0	0	2
	x₁₁											0	1
	x₁₂												0

В матрице приращений (5) выбрать максимальный отрицательный элемент. Таким элементом является элемент Δl(x₅,x₇). Вершины x₅, и x₇ образуют первое подмножество переставляемых вершин. Из всех остальных 25 отрицательных перестановок только элемент Δl(x₂,x₆) определяет подмножество {x₂,x₆}, у которого ни одна из вершин не связана ни с вершиной x₅, ни с вершиной x₇ первого подмножества. Парная перестановка вершин x₂ и x₆ и вершин x₅ и x₇ позволит уменьшить суммарную длину связей графа на 16 единиц.

Поменять местами x₂ и x₆ строки и столбцы и x₅ и x₇ строки и столбцы матрицы смежности. Матрица смежности примет вид.

			x₁	x₆	x₃	x₄	x₇	x₂	x₅	x₈	x₉	x₁₀	x₁₁	x₁₂	(6)
R⁽¹⁾	=	x₁	0	0	0	0	2	0	0	0	2	0	1	0
		x₆	0	0	0	1	0	0	0	1	0	0	0	0
		x₃	0	0	0	1	0	0	2	1	1	0	0	0
		x₄	0	1	1	0	0	0	0	2	1	0	0	0
		x₇	2	0	0	0	0	0	2	0	1	1	0	0
		x₂	0	0	0	0	0	0	0	0	0	1	0	1
		x₅	0	0	2	0	2	0	0	1	0	0	1	0
		x₈	0	1	1	2	0	0	1	0	0	0	0	1
		x₉	2	0	1	1	1	0	0	0	0	0	0	0
		x₁₀	0	0	0	0	1	1	0	0	0	0	0	1
		x₁₁	1	0	0	0	0	0	1	0	0	0	0	3
		x₁₂	0	0	0	0	0	1	0	1	0	1	3	0

Размещение графа после выполненных перестановок показано на рис.2.

Рис. 2

Вычислить матрицу приращений для размещения, представленного на рисунке 2.

		x₁	x₆	x₃	x₄	x₇		x₂		x₅		x₈		x₉		x₁₀	x₁₁		x₁₂
∆L⁽¹⁾=	x₁	0	5	12	14	1		2		7		14		-6		0	18		17
	x₆		0	1	0	4		2		2		4		-3		4	7		4
	x₃			0	2	7		2		3		0		8		6	4		5
	x₄				0	12		1		4		1		12		6	4		10
	x₇						0		2		14		18		-1	6		11		16	(7)
	x₂								0		2		4		-4	-1		2		4
	x₅									0		6		5		6	7		6
	x₈											0		14		9	4		8
	x₉													0		2	8		9
	x₁₀															0	4		4
	x₁₁																0		1
	x₁₂																		0

Рис. 3

В матрице приращений (7) максимальным отрицательным элементом является элемент Δ_l(x₁,x₉), определяющий первое подмножество {x₁,x₉} переставляемых вершин. Подмножество{x₂,x₁₀} единственное из четырёх оставшихся, которое не имеет связей с первым.

Размещение графа после выполненных перестановок показано на рис. 3.

Поменять местами x₁иx₉ строки и столбцы и x₂ и x₁₀ строки и столбцы матрицы смежностиR⁽¹⁾.

Вычислить матрицу приращений суммарной длины связей для размещения, представленного на рис. 3.

		x₉	x₆	x₃	x₄	x₇	x₁₀	x₅	x₈	x₁	x₂	x₁₁	x₁₂	(7)
∆L⁽²⁾=	x₉	0	3	12	14	5	4	7	12	6	5	16	17
	x₆		0	1	0	6	3	2	4	5	4	11	4
	x₃			0	2	11	6	5	2	14	9	12	9
	x₄				0	16	6	6	3	18	8	12	14
	x₇					0	3	14	18	3	4	13	16
	x₁₀						0	3	6	0	1	6	7
	x₅							0	6	11	6	9	6
	x₈								0	22	8	6	8
	x₁									0	5	16	15
	x₂										0	3	2
	x₁₁											0	1
	x₁₂												0

В матрице приращений нет отрицательных элементов, следовательно, размещение, представленное на рис. 3 оптимизировать данным алгоритмом нельзя.

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

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

В первом случае разобьем множество Х графа G на n классов х₁, х₂, …, х_n и отнесем в них вершины, лежащие в строках решетки внутри области размещения. В каждом классе выделим внутренние и внешние соединительные ребра. Заменим класс x_iодной вершиной C₁. В результате будет получен линейно расположенный мультиграф.

Рис. 4

Факторизация размещенного в решетке графа (рис. 3) по строкам представлена на рис. 4. Класс X₁= {x₉,x₆,x₃,x₄} заменим вершиной С₁, класс X₂= {x₇,x₁₀,x₅,x₈} – вершиной С₂, а класс X₃= {x₁,x₂,x₁₁,x₁₂} заменим вершиной С₃.

Матрица смежности линейного мультиграфа

R=		C1	C2	C3
	C1	0	7	2
	C2	7	0	6	(8)
	C3	2	6	0

Матрица расстояний

D =		C1	C2	C3
	C1	0	1	2
	C2	1	0	1	(9)
	C3	2	1	0

Матрица приращений суммарной длины соединений

	C1	C2	C3
C1	0	4	0
C2		0	5	(10)
C3			0

Для факторизации по столбцам множество вершин Х графа G разобьём на m = 4 класса, и каждый класс заменим вершиной С_i. Соответствие вершин С и классов:

С₁: Х₁={х₉, х₇, х₁}; С₂: Х₂={х₆, х₁₀, х₂}; С₃: Х₃={х₃, х₅, х₁₁}; С₄: Х₄={х₄, х₈, х₁₂}

Факторизация размещенного в решетке графа (3) по столбцам представлена на рис. 5.

Рис. 5

Матрица смежности линейного мультиграфа

R =		C1	C2	C3	C4
	C1	0	1	4	1
	C2	1	0	0	4	(11)
	C3	4	0	0	6
	C4	1	4	6	0

Матрица расстояний графа

D =		C1	C2	C3	C4
	C1	0	1	2	3
	C2	1	0	1	2	(12)
	C3	2	1	0	1
	C4	3	2	1	0

Матрица приращений суммарной длины соединений

∆L =		C1	C2	C3	C4
	C1	0	-1	10	-1
	C2		0	-1	0	(13)
	C3			0	-1
	C4				0

В матрице (13) четыре элемента имеют одинаковые отрицательные значения:Δl(c₁,c₂),Δl(c₁,c₄),Δl (c₂,c₃),Δl (c₃,c₄). Выбираем элемент с наименьшим индексомΔl (c₁,c₂) и меняем местами классы c₁ и c₂.

Матрица смежности после перестановок c₁ и c₂ строк и столбцов:

	C2	C1	C3	C4
C2	0	1	0	4
C1	1	0	4	1

	(14)
C3	0	4	0	6
C4	4	1	6	0

Матрица приращений суммарной длины соединений:

	C2	C1	C3	C4
C2	0	1	4	6
C1		0	6	-6	(15)
C3			0	-1
C4				0

По результатам вычислений в матрице смежности R⁽¹⁾ (15) следует поменять местами c₁ и c₄ строки и столбцы. Получим:

	C2	C4	C3	C1
C2	0	4	0	1
C4	4	0	6	1	(16)
C3	0	6	0	4
C1	1	1	4	0

Матрица приращений суммарной длины соединений:

	C2	C4	C3	C1
C2	0	6	6	7
C4		0	7	6	(17)
C3			0	4
C1				0

В матрице приращений (17) нет ни одного отрицательного элемента, следовательно, факторизация графа по столбцам закончена. Полученное отображение графа в решетку представлено на рис. 6.

Рис. 6

Рис. 7

Примечание: в процессе реализации описанного метода вершина х₂ переставлялась дважды: на первой итерации в паре с вершиной х₆, и на второй итерации в паре с вершиной х₁₀. Если бы при решении задачи была бы принято во внимание условие 2.2, указанное в [1], то от повторной перестановки вершины х₂ на второй итерации следовало бы отказаться и тогда результат размещения был бы не таким оптимальным (рис. 7). Суммарная длина соединений была бы на единицу больше.

Литература

1.Конструирование и технология печатных плат [Текст] / А.Т. Жигалов [и др.] – Москва : Высш. шк., 1973 – С. 57-61.

2.Шандриков, А.С. Оптимизация начального размещения графа в координатной решётке методом групповых перестановок [Текст] / А.С. Шандриков // Успешен тот, кто творит:XIII открытая международная научно-практическая конференции учащихся, студентов и преподавателей учреждений среднего специального образования. / Брестский государственный технический колледж. – Брест : 2020. – С. 1-4.

Скачать

Комментировать