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

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

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

Рис. 8.1

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

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

Рис. 8.2

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

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

Рис. 8.3

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

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

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

Рис. 8.4

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

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

Рис. 8.5

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

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

Рис. 8.6

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

Рис. 8.7, а

Рис. 8.7, б

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

Рис. 8.8, а

Рис. 8.8, б

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

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

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

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

Рис. 8.9

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

10	2	1	1	1	2					2
9	1	1	А 0	1						2
8		1	1	1	2				1	1
7		2	1	2	2	1	1	2	2
6		2		2	1		2	2	1
5	1	1							1	2
4	2	1	2				1	2	2	2
3			2			1				1
2		1	1	1	2	2	В 0
1	2	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.1 дана площадка с 2 контактами и препятствиями.

Контакт № 1:

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

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

Контакт № 2:

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

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

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

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

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

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

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

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

Рис. 8.12