Проектирование печатных плат. Овчинников В.А - 22 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

22
рестностью ячейки A — O(k) (А). Если проведение пути возможно, то на
каком-то k
+ 1 шаге окажется, что ячейка В Є O(k+1)(А). Если в следую-
щий фронт не удается включить ни одной свободной ячейки, т.е. O(k+1)
(A) = O(k) (A), то при данных условиях путь провести невозможно. Таким
образом, эта часть алгоритма определяет возможность проведения пути
между ячейками
A и В.
Во второй части алгоритма, начиная с ячейки
В, по определенным
правилам выполняется переход от ячейки k-го фронта к ячейке (k-1) фрон-
та до ячейки
А. Пройденные ячейки составляют искомый путь.
Условия, которые необходимо выполнить при проведении пути, и воз-
можность оценки его оптимальности должны быть заложены в правила, по
которым движется фронт волны. Для ячеек дискретного поля устанавли-
ваются отношения соседства. Распространение волны заключается в при-
сваивании ячейкам, соседним с ячейкой предыдущего фронта, значения
весовой
функции. Вес ячейки k-гo фронта Рk является функцией веса
ячейки (k-1) фронта. В общем случае к весу предъявляется требование Р(k-
1) ≠ Р(k)≠ Р(k+1).
В большинстве модификаций алгоритма Ли на значения веса накла-
дывается ограничение Р(k)>P(k-1). В этом случае проведение пути заклю-
чается в переходе от ячейки
В к ячейке A таким образом, чтобы значение
P(k)
монотонно убывало. При этом возможен вариант, при котором не-
сколько ячеек, соседних данной, имеют одинаковый вес. Для однозначно-
сти выбора при учете критерия минимума изгибов проводника следует со-
хранять направление движения. Если приходится делать поворот, учиты-
вается заранее заданный порядок предпочтительных направлений: вверх,
вправо, вниз, влево.
Рассмотрим случай, когда соседними к
данной являются ячейки,
имеющие с ней общее ребро, а вес ячейки k-го фронта P(k)=P(k-1)+1, т.е.
равен расстоянию k-й ячейки от исходной
А в ортогональной метрике.
Волна распространяется из ячейки
А, вес которой считаем равным нулю.
Фронт волны доходит до ячейки
В. Например, в ходе построения пути из
ячейки с весом 11 можно перейти в три соседние ячейки с весом 10. Здесь
переход осуществляется, сохраняя направление движения. Аналогично
происходит переход из ячейки с весом 10.
У ячейки с весом 9 есть две со-
седние ячейки с весом 8. Если приходится изменять направление движе-
ния, переход выполняется по предпочтительному направлению.
Так как алгоритм Ли представляет собой алгоритм нахождения крат-
чайшего пути в графе, он легко распространяется на многослойный печат-
ный монтаж при использовании модели в виде графа монтажного про-
странства. При наличии ограничений на переходы со слоя на слой можно
увеличить вес ребра, соединяющего две смежные вершины на соседних
слоях, по сравнению с весом ребра, соединяющего смежные вершины од-
ного слоя.

Страницы