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

- 78 - Модификация алгоритма Ли а) Использование путевых координат. Имеем четыре возможные путевые координаты ячейки: согласно приоритету ↓ , ← , ↑ , → и соответствующие им коды направлений 00, 01, 10, 11. При проведении пути движение от ячейки Я i к ячейке Я i +1 осуществляется по путевым координатам. Путевой координатой ячейки Я i k -го фронта называют ту соседнюю с ней ячейку ( k –1)-го фронта, от которой Я i получает свой вес. б) Метод встречной волны. В этом случае источниками волн будут обе ячейки, которые надо соединить. При этом на каждом k -м шаге поочерeдно строят фронты волн, распространяющихся из этих ячеек. Процесс продолжают до тех пор, пока какая-либо ячейка из фронта одной волны не попадет во фронт другой волны. Путь проводят из этой ячейки С в направлении обоих источни- ков (рис. 46). Лучевой алгоритм трассировки Этот алгоритм предложен Абрайтисом. Выбор ячеек для построения пу- ти между точками А и В происходит по заранее заданным направлениям, по- добным лучам. Тем самым сокращается число просматриваемых ячеек, однако уменьшается вероятность нахождения пути сложной конфигурации. Задают число лучей, распространяемых из точек А и В , и порядок присвоения путевых координат. Лучи распространяются одновременно из обоих источников до их встречи в некоторой ячейке С . Построение пути начинают от ячейки С к точкам А и В . Выберем для то- чек А и В по два луча с противоположными направлениями: А (1) , А (2) , В (1) , В (2 ) (рис. 47). Лучи А (1) и В (2) встречаются в ячейке С (рис.47). Обычно лучевой алго- ритм позволяет построить до 80% трасс.