+ всегда строит путь, если он существует и этот путь минимальной длины. - в процессе распределения волны каждая ячейка может быть свободна, запрещена, либо в ней может стоять L. - необходим большой объем оперативной памяти для хранения ДРП. Модификация алгоритма.
Кодирование по модулю 3 (mod 3). 01201201
N = ] log2 (5) [=3 и не зависит от размера платы.
Метод путевых координат. Путевой координатой ячейки ci будем называть ячейку предыдущего фронта, от которой ci получает свой вес. До трассировки задается правило просмотра →↓←↑. Второй недостаток: трудоемкость алгоритма. 90% - I этап, 10% - восстановление пути.
Способы уменьшения трудоемкости. 1) Выбор источника волны – источник точка А – источник точка В
Время пропорционально заштрихованным областям. То есть выбирается ячейка, находящаяся ближе к краю коммутационного поля. 2) Метод встречной волны
T ~ ПR2 T = 2ПR2 = 2ПR2/4 = ПR2/2 Обрамление.
Волна проводится не по всему полю, а в рамке. Если сначала волна не достигает В (препятствия), то рамка увеличивается на ∆ (дельта). Чаще всего требуется не более трех расширений. Трудоемкость критична. В волновом алгоритме можно учитывать несколько параметров: длина перехода, число перегибов, количество переходов между слоями. Лучевые алгоритмы. Цель: сокращение времени работы. Лучевой алгоритм Арбайтиса
Восстановление в обратном направлении стрелок. Удачно проводятся до 60% трасс, остальные с помощью волнового алгоритма. Лучше работает в заполненном поле.
Малоповоротный алгоритм Микам Табуки.
Обычно не больше 3 поворотов. Скорость на 2 порядка выше, чем у волнового
Недостаток: последовательный характер.
Канальный алгоритм. Основан на представлении рабочего поля в виде вертикальных и горизонтальных каналов, кот характеризуется количеством трасс или разрешающей способностью.
Алгоритм состоит из 2 частей: 1) распределение соединений по каналам; 2) распределение соединений по магистралям. В канале 6 интервалов. G (S) – граф интервалов – граф, вершинами которого являются интервалы Mi, а ребро соединяет вершины, если магистрали имеют одинаковые координаты.
Задача сводится к раскраске графа. Один цвет – следовательно могу располагаться интервалы на одной магистрали. Алгоритм левого конца. Необходимо упорядочить вершины графа по неубыванию координаты левого конца. M1 M5 M2 M4 M6 M3. M1 помещается на верхнюю магистраль Первая магистраль: M1 M4 Вторая магистраль: M5 M6 Третья магистраль: M2 M3 Возникает проблема: необходимо учитывать граф вертикальных пересечений. Достоинства канального алгоритма.
+ скорость выше на 1-2 порядка чем у волнового
+ не надо хранить одновременно все дискретное поле
+ проводя проводники проявляется параллельность (то есть проводим один с учетом другого) Недостатки.
- используется только для регулярных структур
- если в ПП есть сильно разногабаритные структуры, то этот алгоритм бесполезен. Алгоритм Винтера.
· Оптимизирует последовательностный характер, локализуя отдельные трассы. Алгоритм многократного повторения шага построения всех трасс. На каждом шаге сохраняется не вся трасса, а лишь часть. За конечное число шагов строятся все трассы. Алгоритм SPECCTRA.
Новый принцип представления графической информации, Бессеточный адаптивный алгоритм, Многоповторный, На первом шаге проводятся все трассы, На втором пытается уменьшить число конфликтов двумя методами:
1. вставка и расталкивание (PUSH AND SHORT)
2. разрывание и проталкивание (RIP UP AND RETRY)
Информация о конфликтах на текущем шаге используется для следующего шага (весовые коэффициенты). Ни один алгоритм не обеспечивает 100% разводки. То есть необходима итерационная разводка. Требование к алгоритму: не количество проводников, а простота конфигурации трасс.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.