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

x_B1 = x_B2,     одной вертикальной прямой

x_A1 = x_B1          (рис 4.7)

11.   y_A1 = y_A2,     тогда  оба отрезка находятся на

y_B1 = y_B2,     одной горизонтальной прямой

y_A1 = y_B1         

12.   к₁ = к₂,

, тогда  оба отрезка находятся на одной        

b₁ = b₂,      наклонной прямой (рис. 4.8)

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

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

d_max < d_A1A2 + d_B1B2, где d_max - расстояние между самой дальней точкой одного отрезка и самой дальней точкой другого отрезка;

d_A1A2 – длина отрезка А₁А₂;

d_B1B2 – длина отрезка B₁B₂.

Длины отрезков вычисляются по формуле

d = |xi - xj| + |yi - yj|.

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

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

Исходные данные:

количество модулей = 10;

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

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

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

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

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