Волновой алгоритм трассировки соединений

Этапы трассировки многослойных печатных плат:
1. [Что?] Для каждой цепи (подмножества эквипотенциальных контактов) определяется порядок соединения этих контактов
2. [Где?] Определение кол-ва слоев полупроводников и распределение проводников по слоям
3. [Когда?] В каком порядке проводить соединения
4. [Как?] Выполнение собственно трассировки

	1	2	3	4	5	6	7	8
1	3	2	1	А	1
2	4	3	2	1	2
3	5	4	3
4	6	5	4		В
5	7	6	5		9	10
6	8	7	6	7	8	9	10
7	9
8	10

Рассмотрим этап 4 из [КАК?] - выполнение собственно трассировки.

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

Волновой алгоритм трассировки состоит из двух фаз: фазы распространения волны и фазы проведения трассы.

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

2. Проведение трассы начинается от цели. На каждом шаге в качестве следующего элемента выбирают ячейку с наименьшим весом.

Если при проведении трассировки несколько вариантов равнозначны, то вводят дополнительные условия, например, минимальное количество изгибов.

Недостатки:

1) Большие затраты времени (невысокое быстродействие).
2) Большие затраты памяти - на каждую ячейку требуется n = ]log₂(L+2)[ бит, где L - максимально возможный путь (максимальное число, которое можно получить, распространяя волну), еще два состояния - свободно/занято.