Расчет по Волновому алгоритму Ли

На Рис.8.1 дана площадка с 2 контактами и препятствиями. Выполнить трассировку в 4 и 8 направлениях.

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

Рис. 8.1

На Рис. 8.2 из источника А моделируется распространение числовой волны до тех пор, пока ее фронт не достиг цели В. Между ячейками A и B существует путь длиной 9.

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

Рис. 8.2

На Рис. 8.3 мы видим, что трассы прокладываются только под углами в 90^о.

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

Рис. 8.3

На Рис.8.1 дана площадка с 2 контактами и препятствиями. Выполнить трассировку в 4 направлениях.

На Рис. 8.4 из источника А моделируется распространение числовой волны до тех пор, пока ее фронт не достиг цели В. Между ячейками A и B существует путь длиной 6.

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

Рис. 8.4

На Рис. 8.5 мы видим, что трассы могут проводиться под любыми углами.

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

Рис. 8.5

Машинный расчет по Волновому алгоритму Ли

На Рис.8.6 дана площадка с 2 контактами и препятствиями. Выполнить трассировку в 4 и 8 направлениях.

Рис. 8.6

На Рис.8.7 (а,б) машинный расчет по Волновому алгоритму Ли, трассировка в 4 направлениях.

Рис. 8.7, а

Рис. 8.7, б

На Рис.8.8 (а,б) машинный расчет по Волновому алгоритму Ли, трассировка в 8 направлениях.

Рис. 8.8, а

Рис. 8.8, б

Расчет по Алгоритму Акерса

На Рис.8.1 дана площадка с 2 контактами и препятствиями. Выполнить трассировку в 4 направлениях.

Для построения пути в общем случае необходимо найти требуемую подпо-следовательность отметок базовой последовательности. Это легко может быть сделано по отметке ячейки-цели и отметке соседней с ней ячейки. В нашем случае цель достигнута первой 1, поэтому надо искать ячейку с отметкой 2. Их две: внизу и слева. Воспользуемся приоритетом. Вначале просматриваем ячейку снизу от цели. Поскольку ее вес равен 2, путь строим в нее. В ней вновь анализируем соседние ячейки в порядке приоритета. Ищем ячейку с весом 2. Это опять нижняя ячейка. Далее надо аналогично искать ячейку с весом 1. (см. Рис. 8.9)

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

Рис. 8.9

Вариант соединения контактов A и B при этом заданном приоритете дан на рис.8.10.

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

Рис.8.10

Машинный расчет по Алгоритму Акерса

На Рис.8.6 дана площадка с 2 контактами и препятствиями. Выполнить трассировку в 4 направлениях.

На Рис.8.11 (а,б) машинный расчет по алгоритму Акерса, трассировка в 4 направлениях.

Рис. 8.11, а

Рис. 8.11, б

Расчет по Лучевому алгоритму

На Рис.8.12 дана площадка с 2 контактами и препятствиями.

Контакт № 1:

Луч 1: направление первичное 3, вторичное 2.

Луч 2: направление первичное 2, вторичное 3.

Контакт № 2:

Луч 1: направление первичное 1, вторичное 0.

Луч 2: направление первичное 0, вторичное 1.

 Выполнить трассировку в 4 направлениях.

Распространение лучей происходит одновременно из обоих источников до встречи двух разноименных лучей в некоторой точке C.

Путь проводится из ячейки C, в которой встретились лучи по путевым координатам, и проходит через ячейки, по которым распространялись лучи.

При распространении луча может возникнуть ситуация, когда две соседние ячейки будут заняты. В этом случае луч считается заблокированным и его распространение прекращается.

Рассмотрим работу лучевого алгоритма на примере (рис.8.13).

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

Рис. 8.12

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

Рис. 8.13