Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Для иллюстрации решения этой задачи представим схему в виде графа (рис. 5.1),

в котором вершинами являются элементы (модули) схемы, а ребрами – соединения между элементами. Размещение позиций , в которые устанавливаются вершины графа, задается их координатами x и y, а соединения между элементами задаются матрицей связей (табл.

5.1).

Табл. 5.1. Матрица смежности.

			1	2	3	4
		1	0	0	1	1
		2	0	0	1	1
		3	1	1	0	1
		4	1	1	1	0
1	2					4	2

4 3 1 3

Рис. 5.1.	Рис. 5.2.

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

пусть граф, представленный на рис. 5.1 имеет пересечение ребер. Осуществим парную перестановку первой и четвертой вершин графа, в результате чего получим граф без пересечений (рис. 5.2).

Общее количество пересечений для графа с n вершинами можно определить по формуле :

	1 n	n	n	n
S				p[(i, j);(k, l)]mij mkl,	(5.1)
S	8 i 1			p[(i, j);(k, l)]mij mkl,	(5.1)
	8 i 1	j 1	k 1	l 1

где n – число вершин графа;

1, если между ребром (i,j) и ребром (k,l) есть пересечение

p[(i,j);(k,l)] =

0, в противном случае;

mij, mkl - элементы матрицы смежности.

В другой форме можно записать :

					62
n 1	n	n 1		n
S				p[(i, j);(k,l)]mij mkl,	(5.2)
i 1	j i	1 k 1	l	k 1

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

Пусть в некотором графе ребра, инцидентные вершине A, имеют следующее число пересечений с остальными ребрами графа:

n		n 1		n
SA				p[(A, j);(k,l)]mA jmkl, где j	B
j	1 k 1		l k 1
Аналогично, для вершины B
n		n 1		n
SB				p[(B, j);(k,l)]mB j mkl, где j	A
j	1	k 1	l	k 1

После перестановки местами вершин A и B число пересечений изменится и станет равным:

	n	n 1		n
S'A					p[(A, j); (k, l)]mB jmkl, где j				B .
j	1	k 1	l	k	1
n		n 1		n
S'					p[(	, j);(k, l)]m	m	где j	A
B					B	A j	kl,
j	1	k 1	l	k	1

Тогда изменение числа пересечений в результате перестановки вершин A и B

выразится формулой :

			S	AB	(S	S )	(S '	S ' )
				AB		A B	A	B
n	n 1		n
			{p[(A, j);(k, l)]		p[(B, j);(k, l)]}			(mA j mB j ) mkl, где j A, j B
j 1	k 1	l	k 1

Если SAB > 0, то перестановка вершин A и B целесообразна, так как ведет к уменьшению числа пересечений.

Определить наличие пересечений p[(i,j);(k,l)] между ребрами (i,j) и (k,l) можно следующим образом в соответствии с рис. 5.3, 5.4

Ребра А1А2 и В1В2 являются отрезками прямых линий. Прямая линия описывается уравнением /8/:

y = kx + b.

Прямая, на которой лежит отрезок А1А2 описывается уравнением :

y = a1x+b1, где a	yA1	yA2	, b	y	a x
						A1
1	xA1	1		A1	1
		xA2

Аналогично для В1В2:

y = a2x+b2, где a		yB1	yB2	, b		y	a	x
	2				2
		xB1	xB 2			B1		2 B1

Точка Z пересечения этих прямых имеет координаты :

x*	b2	b1	; y*	a1b2	a2b1	;

	a1	a2		a1	a2

Необходимо далее определить, принадлежит ли точка Z(x*,y*) обоим отрезкам А1А2, В1В2 в соответствии с рис. 5.3.

y	y
B1	B1

	A1	A1
0	x	0	x
	x
	Рис. 5.3. Пересечение ребер.	Рис. 5.4. Область пересечения
	Если точка Z принадлежит заштрихованной области, значит она принадлежит
обоим отрезкам :
	Z [A1,A2], Z	[B1,B2],
	следовательно является точкой пересечения отрезков (A1,A2), (В1,В2), т.е.
	Z = (A1,A2)	(B1,B2),

Это значит, что xmin < x* < xmax, ymin < y* < ymax, для каждого отрезка, где

хmin – большее значение из двух минимальных значений координаты х отрезков А1А2 и В1В2;

ymin – большее значение из двух минимальных значений координаты y отрезков А1А2 и В1В2;

хmax – меньшее значение из двух максимальных значений координат х отрезков А1А2 и В1В2;

ymax – меньшее значение из двух максимальных значений координат y отрезков А1А2 и В1В2.

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

определения принадлежности точки пересечения отрезкам А1А2

и В1В2 был реализован в

программе.

Кроме такого общего случая расположения прямых на плоскости относительно

координатных осей, возможны частные случаи :

1. xA1 = xA2, xB1

xB2; (рис. 5.5)

Тогда x* = xA1; y* = a2x*+b2,

где a2

yB1

yB2

yB1

a2 xB1

xB1

xB 2

Рис. 5.5.

2. xB1 = xB2, xA1

xA2;

Тогда x* = xB1; y* = a1x*+b1,

где a

yA1

yA2

a x

xA1

xA2

3. yA1 = yA2, yB1

yB2

Тогда y* = yA1; x*

y *

;

где a

yB1

yB2

xB1

xB 2

4. yВ1 = yВ2, yA1

yA2

Тогда y* = yB1; x*

y *

;

где a

yA1

yA2

, b

a x

xA1

xA2

5.xA1 = xA2,

,тогда x* = xA1, y* = yB1

yB1 = yB2

6.xB1 = xB2,

,тогда x* = xB1, y* = yA1

yA1 = yA2

7.xA1 = xA2,

xB1 = xB2 , тогда пересечение отсутствует

xA1 xB1

8.yA1 = yA2,

yB1 = yB2 , тогда пересечение отсутствует

yA1 yB1

9.к1 = к2,

,тогда пересечение отсутствует (рис. 5.6)

b1 b2

10.xA1 = xA2, тогда оба отрезка находятся на xB1 = xB2, одной вертикальной прямой

xA1 = xB1

(рис 5.7)

11.yA1 = yA2, тогда оба отрезка находятся на yB1 = yB2, одной горизонтальной прямой

yA1 = yB1

12.к1 = к2,

,тогда оба отрезка находятся на одной наклонной прямой (рис. 5.8)

b1 = b2

						y	B2
						y
y		A1	y	B2			A2
		A1	B1

							B1
				A2			B1
				A2
	A2
b1				B1		b1	A1
b1				B1		b1
b2	B2
b2				A1
				A1
	Рис. 5.6.		x	Рис. 5.7.	x		Рис. 5.8.	x

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

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

Это условие выражается следующим неравенством:

dmax < dA1A2 + dB1B2,

Источник: https://studfile.net/preview/16565529/

Смотрите также:

2409
3 (лекция) Метод нейтрализации
799
Zaruba_Otvety
Анализ воздействия на окружающую среду в процессе освоения территории Республики Тыва (на примере Кызыл-Таштыгского месторождения)
Внесок муніципальних органів влади міста Харкова у систему охорони здоров’я (кінець ХІХ - початок ХХ століття)
Где живут белые медведи и пингвины
Государственно-частное партнерство. Практические механизмы реализации. (На конкретном примере)
Датчики движения и удара для автомобильной сигнализации
Дело 01-0374_2017. Приговор. документ - обезличенная копия