Методы повышения эффективности волнового алгоритма.

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

	•А
		•В

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

	•А
		•В

	•А
		•В

Методы повышения быстродействия:
1. Целенаправленно выбирать из двух контактов место испускания волны так, чтобы фронт волны был меньше. Так, если у нас один контакт в углу монтажного поля, а второй - в середине, то целесообразно испускать волну из первого.

2. Испускать волну из двух контактов одновременно (встречная волна)
3. Метод рамки - соединяемые контакты ограничиваются рамкой, на 15-20% превышающей минимальный прямоугольник. Волна за эту рамку не распространяется. Если путь не был найден, то рамка либо увеличивается, либо убирается совсем.

1				А	®				1. Метод путевых координат. Путевая координата - указание, откуда пришла волна (сверху(¯) /слева(®) /справа()/снизу(­)). n = ⌈log2(4+2)⌉ = 3. Для разрешения конфликтов первой фазы надо указать приоритеты направлений.
2	¯	¯	¯	¯	¯
3	¯	¯	¯
4	¯	¯	¯		В
5	¯	¯	¯		­	®
6	¯	¯	¯	®	®	®	®
7	¯
8	¯

1	3	2	1	А	1				2. Использования веса по модулю 3 (Pi-1 ≠ Pi ≠ Pi+1). Веса равны 1, 2, 3. (0 ® ячейка не занята) n = ⌈log2(3+2)⌉ = 3. Здесь, как и в предыдущем методе, надо указать приоритеты направлений. Ищем маршрут 1®3®2®1®3®2®…
2	1	3	2	1	1
3	2	1	3
4	3	2	1		В
5	1	3	2		3	1
6	2	1	3	1	2	3	1
7	3
8	1

1	2	1	1	А	1				3. Метод Акерса (самый эффективный). Веса назначаются фронтам в соответствии со следующей последовательностью: 1122112211... n = ⌈log2(2+2)⌉ = 2. У каждого элемента обязательно различаются соседи слева и справа (1 и 2 или 2 и 1). Построение трассы сводится к выделению искомой последовательности, опять же, необходима система приоритетов. Ищем маршрут 1®1®2®2®1®1®…
2	2	2	1	1	1
3	1	2	2
4	1	1	2		В
5	2	1	1		1	1
6	2	2	1	2	2	1	1
7	1
8	1

Методы снижения затрат памяти:

Алгоритм трассировки соединений по магистралям.

В данном алгоритме можно отказаться от использования дискретного представления поля.
Из двух контактов выпускаются два луча, которые будем называть магистралями. Эти магистрали - M₁^A и M₁^B - магистрали первого уровня. Если они пересекаются, то трасса найдена. Если нет, то на данных магистралях находятся базовые точки и уже из них выпускаются магистрали второго уровня и так далее, пока не будет найдено пересечение либо не будет превышен предел на уровень магистрали.
После нахождения пересечения магистралей выбирается пересечение по отрезку наименьшей длины до точки испускания. Так, если в точке P пересекаются магистрали 1-го и 2-го уровней, а в точке Q - пересекаются две магистрали второго уровня, то для проведения трассы следует выбрать точку P.

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

Пример:

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