Информационные технологии проектирования электронных средств

- 64 - Решение задачи Штейнера существенно зависит от метрики. Рассмотрим ее решение в ортогональной метрике. Сформулируем первый алгоритм построения дерева Штейнера. 1. Пусть Р ={ p 1, p 2 ,…., p n } – выводы одной цепи. Построим базовую ортого- нальную сетку магистралей, проходящих через точки р i с координатами ( x i , y i ). 2. Пронумеруем по часовой стрелке по спирали точки р i из множества Р , начиная с такой точки p i 1 , для которой координата x i 1 = i i x min и y i 1 = i i y min . 3. Присвоим каждой точке р i один из двух признаков: 0 – если трасса пой- дет вдоль оси х , и 1 – если трасса пойдет вдоль оси у . Точка p i 1 получает при- знак 0. Далее признаки присваивают всем точкам попеременно, причем точки одного участка, находящиеся на одной горизонтали (вертикали), получают один и тот же признак. 4. Для точки р i 1 = р 1 найдем такую точку р s , для которой будет справедливо: r s 1 =│ x s – x 1 │+│ y s – y 1 │→min. Строим фрагмент дерева, соединяющий точку p 1 с найденной точкой p s . 5. Всем вершинам ортогональной сетки, через которые прошел фрагмент дерева, присваиваем наименьший из номеров концевых точек фрагмента. 6. Выполним третий и четвертый пункты для всех точек р i ∈ Р в порядке возрастания их номеров. 7. Будем повторять с третьего по пятый пункты до тех пор пока все точки р i не получат номер, равный единице. Рассмотрим второй алгоритм построения дерева Штейнера. Этот алго- ритм содержит два этапа. На первом этапе с помощью алгоритма Прима стро- ится минимальное связывающее дерево T =( P , U ), где Р – множество выводов цепи, а U – ребра, реализованные кратчайшими путями. В результате получаем список L соединений для дерева Т . Второй этап состоит в совмещении путей, соответствующих ребрам u ∈ U , и содержит следующие пункты. 1. Из списка L выбирается очередная вершина р i .