Канальная трассировка соединений в БИС (1006300), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Введем следующие обозначения: — множество вершин грифа Z, не имеющих входящих дуг, упорядоченное по возрастанию абсциссы начала соответствующих этим вершинам горизонтальных отрезков; - совокупность горизонтальных отрезков цепей, назна­чаемых на магистраль с номером r.

Алгоритм канальной трассировки состоит в следующем:

1. Примем r = 0 и найдем V*.

2. Положим r= r +1; W=0; x(W)=0.

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

4. Если такой отрезок существует, то запишем , в список W, примем и перейдем к п.З, иначе к п. 5.

5. Для назначения горизонтальных отрезков цепей на магистраль r положим удалим из графа Z все вершины, составляющие , и все инцидентные им ребра и дуги. Найдем V*.

6. Если V*=0, то переходим к п. 7, иначе к п.2.

7. Для цепей, у которых все выводы находятся только на нижней стороне канала, горизонтальный отрезок цепей располагаем на нижней стороне канала.

8. Конец алгоритма.

Согласно алгоритму канальной трассировки по приведенным на рас.3.13 и 3.14 обобщенным графам ограничений получим представленные соответственно на рис.3.9 и 3.2 результаты канальной трассировки, соответствующие первому и второму способам устранения цикла.

Характеристики

Список файлов ответов (шпаргалок)