Оптимизация пути по нескольким параметрам

⇐ ПредыдущаяСтр 13 из 19Следующая ⇒

Волновой алгоритм может одновременно учитывать несколько критериев: длина пути, число перегибов, число переходов со слоя на слой и т.д. Тогда вес ячейки k-го фронта будет вычисляться по формуле

где a_i - весовой коэффициент, учитывающий важность i-го критерия; f_i(k) – значение i-го параметра для рассматриваемой ячейки; n –количество учитываемых критериев.

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

Тогда, p_k= p_k_-1 + 1 + 3p₂.

На втором шаге алгоритма в ячейку после изгиба ставится метка 5 (рис. 7.29 (а)), и волна в этой ячейке «засыпает», пока есть возможность ставить метки 3, 4 и 5. После этого она становится активной и идет дальше.

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

Построен путь с двумя перегибами и длиной – 11. Минимальная возможная длина - 9 при пяти перегибах (пунктирный путь на рис. 7.29 (б)).

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

В₁₇

Рисунок 7.29. Распространение волны (а), построение пути (б)

Методы повышения быстродействия волнового алгоритма

Методы сокращают время распространения волны. Это методы:

1. Выбор источника волны.

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

а₅

Рисунок 7.30. Источники волны ячейка А (а), ячейка В (б)

2. Метод встречной волны.

Волна попеременно распространяется из двух источников (А и В) до тех пор, пока волны не встретятся (рис. 7.31 (б)). Путь строится, начиная с ячейки встречи, до источников (рис. 7.31 (в)).

Рисунок 7.31. Метод встречной волны

Площадь заштрихованной фигуры рис. 7.31 (а) S₁ = p L²_AB , афигуры рис. 7.31 (б) – S₂ = 2p (L_AB /2)² = p L²_AB/2, т.е. в два раза меньше. Время распространения волны во втором случае, с учетом потери времени на организацию попеременной волны, почти в два раза меньше.

3. Обрамление соединяемых точек.

Путь ищется не во всем коммутационном поле а в окрестности ячеек А и В (рис.7.32)

Рисунок 7.32. Обрамление области поиска пути

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

Многослойная трассировка

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

Одним из таких алгоритмов является алгоритм многослойной трассировки Хейса (S. Heiss). При распространении волны свободным ячейкам ДРП_i присваивается индекс длины пути p_i и индекс количества межслойных переходов v_i.

слой 1

слой i

слой n

межслойный переход

Рисунок 7.33. Дискретное рабочее поле для многослойной трассировки

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

Рассмотрим трассировку соединений двухслойной печатной платы. Примем цену перехода k = 1 (рис. 7.34).

В алгоритме Хейса волна распространяется независимо в каждом слое, что приводит к значительным затратам времени и памяти при реализации.

Джейер (J.M. Geyer) распространил однослойный вариант трассировки на n слоев. В алгоритме Джейера используется единственное плоское ДРП, которое отображает состояние ячеек для всех слоев. В этом ДРП реализуется процедура распространения волны. Оно происходит одновременно во всех слоях схемы.

Для каждой ячейки ДРП вводятся следующие поля описания (рис. 7.35):

р – индекс длины (вес);

А = ||a_i||_n – n признаков занятости ячейки по каждому слою;

B = ||b_i||_n – n признаков допустимости для включения ячейки в путь по каждому слою;

v – возможные переходы.

v	b_n	...	b₂	b₁	a_n	...	a₂	a₁	р
2n + 3	2n + 2		n +4	n +3	n +2				2 1

Рисунок 7.35. Формат ячейки ДРП

Для кодирования каждой ячейки ДРП требуется 2n + 3 разрядов.

Достоинство волнового алгоритма то, что он всегда строит путь, если он существует и этот путь минимальной длины.

Недостатками алгоритма являются трудоемкость, большой объем требуемой оперативной памяти и последовательный характер построения трасс. Сложность волнового алгоритма составляет О(N× M), где N – число клеток ДРП; M – число контактов.

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒