qeM на каждом цикле определяется одна из цепей сети. Так как число цепей равно (п-1), то вся задача решается за (п-1) циклов.

4. Выделение из матрицы расстояний множества чисел-{rmih}> Т. е. из всего множества чисел матрицы выделяются числа, определяющие расстояния каждого элемента фрагмента сО всеми изолированными элементами.

Если на первом шаге в состав фрагмента включен первый элемент, то на первом цикле блоком 5 будет выделена первая, строка матрицы.

5. Определение числа Гт lg=miii {гтЛ]}- Из множества чисел, выделенных блоком 5, находится наименьшее число, которое соответствует длине новой цепи фрагмента. Признаки этого числа определяют номера элементов, между которыми эта цепь должна быть проведена, и номер нового элемента, который войдет б множество {nii}.

6. Блоком 7 новая цепь заносится в список кратчайших соединений сети.

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

Маршрутные алгоритмы трассировки. Маршрутные алгоритмы TpaiOCHpoB,KH получили такое название потому, что при их применении ЦВМ строит соединение по маршруту, определяемому координатами конечных элементов трассы и математическими методами, положенными в основу данного алгоритма.

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

Рассмотрим некоторые примеры маршрутных алгоритмов. На рис. 1.29,0; изображена структурная схема алгоритма, на

каждом цикле работы которого происходит определение координат очередного элемента трассы, удовлетворяющего условиям:

1. Элемент должен быть соседним по отношению к последнему по номеру элементу искомой трассы.

2. Выбранный элемент должен быть наименее удаленным от конечного элемента трассы.

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

Вбод данных

4 Определение rib minfqtj. Запись элемента J= В список элементов трассы

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

Останов

Ввод данных

Условный переход, если пронладыВаемая трасса встретилась с препятствием

2 Вычисление координат второго элемента трассы

Определение признаков

точек огибания ранее проложенной трассы

3 Вычисление координат очередного элемента трассы по ретурентным формулам

Проверка Выполнения усповия

Хк=Хв fo) = У6

2 Определение координат точек огибания ранее проложенной трассы

3 Вычисление приоритетных чисел и определения приоритета огибания точек

Переодресация

5 Вывод

результатов решения задачи размеихрния

Переход к основном/) маршрутному алгоритму

Рис. 1.29. Структурная схема маршрутного алгоритма трассировки (fl, б, в)

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

1. Ввод данных. С помощью этого блока оперативное запоминающее устройство ЦВМ заносит координаты начального и конечного элементов трассы А (ха, уа) и В (хв, г/в).

2. Выделение множества элементов {Fj}, соседних последнему элементу трассы, т. е. из всех элементов 1-окрестности последнего по номеру элемента трассы выделяются свободные для прокладки пути элемента. На первом цикле алгоритма последним элементом трассы будет исходный элемент А.

3. Вычисление множества чисел {пЬ}. С помощью этого блока по формуле ГгЬ~\Хг - Хв\ + \Уг~Ув\ ВЫЧИСЛЯЮТСЯ кратчайшис в выбранной геометрии расстояния от всех элементов, выделенных блоком 2, до конечного элемента трассы В.

4. Определение ближайшего к элементу В элемента из 1-окрестности последнего по номеру элемента трассы и занесение его координат (номера) в список элементов искомого пути.

5. С помощью блока 5 проверяется: не достиг ли конечный элемент трассы В. Признаком выполнения условия может быть соотношение гф = 0.

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

Возможно построение маршрутного алгоритма на основе применения рекуррентного уравнения вида:

F{K)=2F{x±h)-F{x±2h)-\-b., (1.13)

где X- абсцисса элемента, занимаемого трассой "на данном шаге; F{x)-ордината элемента, занимаемого трассой на данном шаге; F{x±h) -ордината элемента, занимаемого трас-

1СОЙ на предыдущем шаге; F{x±2h)-ордината элемента,, отстоящего от вычисляемого на два шага; Л - функция, определяющая вид прокладываемой трассы: при А=0 - строится прямолинейная трасса, при А = const-алгоритм генерирует семейство парабол; h - величина изменения абсциссы элементов трассы на каждом шаге h=\, 2, 3. Работа алгоритма производится циклически, причем в течение каждого цикла вычисляются координаты очередного элемента трассы и определяется, не достигла ли трасса конечного элемента.

Ордината очередного элемента трассы вычисляется в соответствии с выражением (1.13), а абсцисса по формуле:

х,=Хк 1 + /г. (1.14)

Как видно из выражения (1.13), для определения ординаты очередного элемента трассы необходимо знать ординаты двух предыдущих элементов. Поэтому вычисление трассы по (1.13) возможно, начиная с третьего элемента. Первым элементом трассы является исходный элемент А, ордината второго элемента может быть вычислена для линейной трассы по формуле:

F {X)=F (х) -f ( ~ (" h. (1.15)

Вк Структурная схема алгоритма приведена на рис. 1.29,6. Осо-Ve достоинство данного алгоритма - простота формул вычис-ННия координат элементов трассы.

ЩВ отличие от волнового и лучевого алгоритмов маршрутные алгоритмы не дают возможности обхода встретившегося на пути