Материал: Основы проектирования Р Э С. Комплект учебно-методической документации по дисциплине. Учебное пособие. Самойленко Н.Э., Скоробогатов В.С

Скачать файл

Заказать новую работу

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

127

где

yB1 yB2

xB1 xB 2

2 B1

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

;

a1b2

a2b1

a1 a2

Необходимо далее определить, принадлежит ли точка

Z(x*,y*) обоим отрезкам А1А2, В1В2

в соответствии с рис. 5.3.

Если точка Z принадлежит заштрихованной области,

значит она принадлежит обоим отрезкам (рис. 5):

Z [A1,A2],

Z [B1,B2].

Следовательно, она является точкой пересечения

отрезков (A1,A2), (В1,В2), т.е.

Z = (A1,A2) (B1,B2),

х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 был реализован в программе.

128

0	x
y	Рис. 4..4.

Рис. 4.5

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

1. xA1 = xA2, xB1 xB2; (рис. 4.6) Тогда x* = xA1; y* = a2x*+b2,

			129
где a		yB1	yB2	, b		y	a	x	.
где a	2			, b	2	y	a	x	.
	2	xB1	xB 2		2	B1		2 B1
		xB1	xB 2

y		A
	B	A
	B

Рис. 4.6

2. xB1 = xB2, xA1 xA2;

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

где a

yA1 yA2

, b

a x

xA1 xA2

3. yA1 = yA2, yB1 yB2.

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

y * b2

;

где a

yB1 yB2

, b

xB1 xB 2

4. yВ1 = yВ2, yA1 yA2.

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

y * b1

;

где a

yA1 yA2

, b

a x

xA1 xA2

5.xA1 = xA2,

130

, тогда 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,

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

b1 b2.

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

xA1 = xB1

(рис. 8)

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

yA1 = yB1

12. к1 = к2, , тогда оба отрезка находятся на одной наклонной

b1 = b2 прямой (рис. 9)

	131
y	A	y
	A	B
		B

b B

Рис4. 7

y B B A

b A

Рис. 4.9

Рис. 4.8 x

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

132

желательно иметь минимальное количество случаев наложения проводников друг на друга.

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

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

Из многих рассмотренных примеров приведем следующий. Исходные данные:

количество элементов = 10; количество исходных начальных размещений: 500;

схема соединений представлена матрицей смежности (табл.

4.2);

Длины отрезков вычисляются по формуле d = |xi - xj| + |yi - yj|.

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

В качестве примера решения задачи минимизации числа пересечений при оптимизации размещения модулей на коммутационном поле с помощью ПЭВМ рассмотрим следующий.

Исходные данные: количество модулей = 10

схема соединений представлена матрицей смежности (табл.

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

133

На рис. 4.10 показана схема соединений модулей, расположенных в исходных (до оптимизации) позициях с

числом пересечений 129.
			Таблица 4.2								Таблица 4.3				Таблица
	4.4
	1	2	3	4	5	6	7	8	9	1		x y		N	x y
										0
1	0	4	0	0	1	1	0	0	0	0		5	4	1	5	4

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

3	0	1	0	1	1	0	1	0	0	0		5	2	3	5	2

4	0	4	1	0	1	0	3	0	1	0		3	3	4	6	1

5	1	1	1	1	0	1	0	1	1	1		6	1	5	3	3

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

7	0	0	1	3	0	0	0	4	1	0		1	1	7	3	1

8	0	0	0	0	1	1	4	0	1	1		2	4	8	1	1

9	0	0	0	1	1	0	1	1	0	1		3	2	9	3	2

1	0	0	0	0	1	3	0	1	1	0		3	1	1	1	3

В результате решения этой задачи с помощью программы, реализующей алгоритм парных перестановок, получили новое (оптимальное) размещение модулей, указанное в табл. 4.4, с числом пересечений, равным 10 (локальный минимум; глобальный минимум, как будет показано в следующем разделе, равен 6). До оптимизации число пересечений было равно 129, то есть число пересечений уменьшилось после оптимизации почти в 13 раз. Схема соединений модулей, расположенных в позициях, после оптимизации показана на рис. 4.11 . На рис. 10 и 11 цифра у линии показывает число соединений между модулями. Цифра 1 не проставляется.

134

4.2.2. Исследование зависимости эффективности алгоритма парных перестановок от исходных начальных размещений и способы повышения его эффективности

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

Y
4		8
3	2	4

	4
2	3
2

0	1	2		3	4	5		X

Рис. 10. Схема соединений модулей

135

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

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

Y
4		2
		2
		4
3	4
3
2	3
	3
1	7	4
	7	4

0	1	2	3	4	5	X
			Рис. 4.11

		136
Результаты эксперимента и их обработка					Таблица 5
Но	Значен	Количе	Вероятн	Удалени		Сумм
мер	ие	ство	ость Pi	е		арная
мин	миниму	появле	Появлен	миниму		вероятность
иму	ма	ний	ия	ма от		Pi
ма	числа	миниму	миниму	глобаль
	пересеч	ма	ма	ного ,
	ений			%
1	6	14	0,028	0		0,028
2	7	22	0,044	16,6		0,072
3	8	89	0,178	33,3		0,250
4	9	12	0,024	50,0		0,274
5	10	43	0,086	66,6		0,360
6	11	31	0,062	83,3		0,422
7	12	22	0,044	100,0		0,466
8	13	40	0,080	116,6		0,546
9	14	65	0,130	133,3		0,676
10	15	39	0,078	150,0		0,754
11	16	18	0,036	166,6		0,790
12	17	29	0,058	183,3		0,848
13	18	11	0,022	200,0		0,870
14	19	25	0,050	216,6		0,920
15	20	7	0,014	233,3		0,934
16	21	12	0,024	250,0		0,958
17	22	3	0,006	266,6		0,964
18	23	2	0,004	283,3		0,968
19	24	5	0,010	300,0		0,978
20	25	4	0,008	316,6		0,986
21	26	3	0,006	333,3		0,992
22	27	2	0,004	350,0		0,996
23	29	1	0,002	366,6		0,998

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

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

1 Содержание стр
obz_lab2_корректные_выводы
rabochaya_tetrad_lechebny_fakultet
Анализ сцепления бетона с арматурой
Анализ экономических отношений и проблем развития аграрного сектора Республики Башкортостан
Борьба цивилизаций
Динамика и тенденция коррупционной преступности в Российской Федерации
К вопросу об оценке уровня лояльности потребителей
Коммуникативная личность
Мировое хозяйство - целостная система