конечного элемента трассы в четырех направлениях.. Таким образом в состав /С-фронта входит не более 8 элементов,

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

В отличие от двухлучевого алгоритма в состав блок-схемы четырехлучевого не входит блок вычисления приоритетных направлений распространения лучей. Приоритеты выбраны постоянными. Будем считать, что установлены следующие приоритетные направления:

Лрлуч и Бглуч: вверх, вправо, вниз, влево;

Лг-луч и Бг-луч: вправо, вниз, влево, вверх;

Лз-луч и Бз-луч: вниз, влево, вверх, вправо;

Л4-ЛУЧ и В-луч: влево, вверх, вправо, вниз.

Недостаток четырехлучевого алгоритма заключается в том, что получаемое соединение не всегда кратчайшее.

Процедура присвоения путевых координат выбрана такой же, как if при двухлучевом алгоритме, путевая координата имеет направление, противоположное направлению распространенид луча.

Блок-схема алгоритма такая же, как и на рис. 1.25. Необходимо только исключить блок 2.

Иллюстрацией к действию алгоритма может служить рис. 1.27, из которого видно, что Бг-луч после 8 шагов блокирован, а соединение проведено Лз-лучом и Бз-лучом.

Полученная трасса далека от кратчайшей и прижимается к краям пространства.

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

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

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

дая длина всех проводников была наименьшей. Данная задача решается описываемым далее алгоритмом, называемым иногда 00 имени его автора Р. К. Прима.

Прим нашел решение и доказал его оптимальность для случая, когда данное множество элементов связывается сетью пря-jiibix линий. Мы заменим в своих рассуждениях понятие «прямая линия» понятием «кратчайшее расстояние», не интересуясь, каким образом будет проведена кратчайшая трасса между двумя элементами.

Рис. 1.27. Пример выполнения трассировки печатного монтажа с помощью четырехлучевого алгоритма

В основу алгоритма положены следующие основные принципы:

1. Всякий изолированный элемент соединяется с ближайшим к нему другим изолированным элементом.

2. Всякий изолированный фрагмент сети соединяется с ближайшим к нему изолированным элементом.

Под фрагментом сети будем понимать подмножество элементов, связанных между собой.

Расстояние от изолированного элемента до фрагмента определяется как расстояние от данного элемента до ближайшего к нему элемента из подмножества, входящего в состав фрагмента.

Обозначим Kij - кратчайшее расстояние между элементами с Номерами i и /;

п - число элементов, связываемых сетью; {nii} подмножество элементов, входящих в состав фрагмента сети;

lb* {г} - подмножество изолированных элементов, г

Рассмотрим структурную схему алгоритма (рис. 1.28).

1. Вычисление матрицы расстояний. По формуле r,-j=Xi- -Хз \ + \ Уг-У}\ определяем кратчайшее расстояние между всемг элементами, которые должны быть соединены. Результаты вычислений сведены в матрицу.

{Гц} =

г 12 13 Гц--т

23 г24- • -гл 34 • • • Зл

Г (л-1)л

Матрица содержит

и(«-1)

чисел. Каждое число записы-

вается в соответствующую ячейку памяти ЗУ. Кроме расстояние

Вышлете матрицы расстояний

2 Формирование подмножеств (fTti) и (ij)

Проверка выполнения условия М = 0

Останов

7 Внесение цепи Witlg в список соедц-нении сети

в Определение числа rm,,lg = min frrr,-lj)

±

5 выделение из матрицы расстояний множества ween (rm-Jj)

Рис. 1.28. Структурная схема алгоритма проведения кратчайшей связывающей сети

между элементами i и / в ячейку заносятся признаки этих элементов.

2. Формирование подмножеств {nii} и {Щ. На первом шаге алгоритма в состав {mi} может быть включен любой элемент,, так как данный алгоритм .инвариантен. При каждом последующем шаге (цикле) количество элементов, входящих в подмножество {nii}, увеличивается, а входящих в подмножество {/,} соответственно уменьшается на один.

3. Проверка выполнения условия {/г}=0. Если в состав множества элементов сети входит только один элемент, то работа алгоритма заканчивается на первом шаге. Если число элементов больше одного, то работа алгоритма происходит циклично, при-