Документ: АиСД. Проектная работа, страницы 36-40

2.4Примеры поиска

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

•< — влево (т. е. правая ячейка — родитель текущей ячейки);

•^ — вверх (т. е. нижняя ячейка — родитель текущей ячейки);

•> — вправо (т. е. левая ячейка — родитель текущей ячейки);

•v — вниз (т. е. верхняя ячейка — родитель текущей ячейки). Пусть — стартовая ячейка, — конечная ячейка.

В следующих примерах показана сама суть поиска каждого алгоритма: какие

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

			Таблица 18

Исходный лабиринт			Итеративный поиск в ширину
███████████████			███████████████
█S	█	█	█S>>>>>█^>>>> █
█	█ █	█	█v>>>█v█^>>>>>█
█	█ █	E█	█v>>>█v█^>>>>E█ E = >
█	█	█	█v>>>█v>>>>>>>█
███████████████			███████████████
Алгоритм Дейкстры			Алгоритм A*
Алгоритм Дейкстры			(октильное расстояние)
			(октильное расстояние)
███████████████			███████████████
█S>>>>>█^>>>> █			█S>>>>>█^ ^ ^ █
█vvvv█v█^>>>>>█			█vvvv█v█^>^>^>█
█v>>>█v█^>>>>E█ E = >			█vvvv█v█^>^>^E█ E = >
█vvvv█v>>>>>>>█			█vvvv█v>>>>>>>█
███████████████			███████████████
Алгоритм A*			Алгоритм A*
(расстояние L1)			(расстояние Чебышева)
███████████████			███████████████
█S>>>>>█^ ^ ^ █			█S>>>>>█^ ^ ^ █
█vvvv█v█^>^>^>█			█vvvv█v█^>^>^>█
█v>>>█v█^>>>>E█ E = >			█vvvv█v█^>^>^E█ E = >
█vvvv█v>>>vvv █			█vvvv█v>>>>>>>█
███████████████			███████████████
		Алгоритм A*
		(расстояние Евклида)
		███████████████
		█S>>>>>█^ ^ ^ █
		█vvvv█v█^>^>^>█
		█vvvv█v█^>^>^E█ E = >
		█vvvv█v>>>>>>>█
		███████████████
Как видим, длина пути (17) одинаковая, но сами пути могут быть разными.

36

						Таблица 19

Исходный лабиринт					Итеративный поиск в ширину
█████████████████████					█████████████████████
█		█	█	█	█<<<<<<<<<<^█<<^█<<^█
███ ███ ███ ███ ███ █					███v███v███^███^███^█
█	█ █ █ █	S	█ █ █		█<<v█^█v█^█<<S>>█^█^█
█ ███ █ █ █ ███ █ █ █					█v███^█v█^█v███v█^█^█
█ █ █ █ █ █ █ █ █				█	█v█ █^█v█^█v█^█v█^>>█
███ █ █ █ ███ █ █ ███					███^█^█v█^███^█v█^███
█ █ █ █			█	█	█ █^█<<v█<<<<<<v█^>>█
█ █ █ █ █ ███ █ █ █ █					█ █^█v█v█v███v█v█^█v█
█E	█ █	█ █		█ █	█E<<<v█v█v>>█v█v>>█v█
█████████████████████					█████████████████████
Алгоритм Дейкстры					Алгоритм A*
					(октильное расстояние)

█████████████████████					█████████████████████
█<<<<<<<<<<^█<<^█<<^█					█<<<<<<<<<<^█<<^█	█
███v███v███^███^███^█					███v███v███^███^███ █
█<<v█^█v█^█<<S>>█^█^█					█<<v█ █v█ █<<S>>█ █ █
█v███^█v█^█v███v█^█^█					█v███ █v█ █v███v█ █ █
█v█ █^█v█^█v█^█v█^>>█					█v█ █^█v█^█v█^█v█	█
███^█^█v█^███^█v█^███					███ █^█v█^███^█v█ ███
█ █^█<<v█<<<<<<v█^>>█					█ █^█<<v█<<<<<<v█	█
█ █^█v█v█v███v█v█^█v█					█ █^█v█v█v███v█v█ █ █
█E<<<v█v█v>>█v█v>>█v█					█E<<<v█v█v> █v█v> █ █
█████████████████████					█████████████████████
	Алгоритм A*				Алгоритм A*
	(расстояние L1)				(расстояние Чебышева)
█████████████████████					█████████████████████
█<<<<<<<<<<^█			^█	█	█<<<<<<<<<<^█<<^█	█
███v███v███^███^███ █					███v███v███^███^███ █
█<<v█ █v█ █<<S>>█ █ █					█<<v█^█v█^█<<S>>█ █ █
█v███ █v█ █v███v█ █ █					█v███^█v█^█v███v█ █ █
█v█ █^█v█^█v█^█v█				█	█v█ █^█v█^█v█^█v█	█
███ █^█v█^███^█v█ ███					███ █^█v█^███^█v█ ███
█ █^█<<v█<<<<<<v█				█	█ █^█<<v█<<<<<<v█	█
█ █^█v█v█v███v█v█ █ █					█ █^█v█v█v███v█v█ █ █
█E<<<v█v█v		█v█v		█ █	█E<<<v█v█v> █v█v> █ █
█████████████████████					█████████████████████

Алгоритм A* (расстояние Евклида)

█████████████████████

█<<<<<<<<<<^█<<^█ █

███v███v███^███^███ █

█<<v█ █v█ █<<S>>█ █ █ █v███^█v█^█v███v█ █ █

█v█ █^█v█^█v█^█v█		█
███ █^█v█^███^█v█		███
█	█^█<<v█<<<<<<v█	█
█	█^█v█v█v███v█v█	█ █

█E<<<v█v█v> █v█v> █ █

█████████████████████

Найденный путь ( , ): (3, 13), (3, 12), (3, 11), (2, 11), (1, 11), (1, 10), (1, 9), (1, 8), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 6), (7, 5), (8, 5), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1).

Длина пути: 23.

37

										Таблица 20

Исходный лабиринт					Итеративный поиск в ширину
█████████████████████					█████████████████████
█ █			█	█	█ █<<<<<<<<<<^█<<^>>█
█ ███████ ███ ███ ███					█ ███████v███^███^███
█	E	█	█	█	█		E<<<v>>█<<^█<<^█
█ ███████████			█ █ █ █		█ ███████████v█^█v█^█
█	█	█ █	█ █ █ █		█	█	█	█<<v█^█v█^█
███ █ █ █ █ ███ ███ █					███ █ █ █			█v███^███^█
█ █	█	█	█	█	█ █		█	█v>>█<<^>>█
█ ███████ ███			███ ███		█ ███████			███v███^███
█		█	█	S█	█			█<<v█<<<<S█
█████████████████████					█████████████████████
Алгоритм Дейкстры						Алгоритм A*
					(октильное расстояние)

█████████████████████					█████████████████████
█ █<<<<<<<<<<^█<<^>>█					█ █<<<<<<<<<<^█					█
█ ███████v███^███^███					█ ███████v███^███ ███
█	E<<<v>>█<<^█<<^█				█		E<<<v> █<<^█ <^█
█ ███████████v█^█v█^█					█ ███████████v█^█ █^█
█	█	█ █<<v█^█v█^█			█	█	█	█<<v█^█ █^█
███ █ █ █ █v███^███^█					███ █ █ █			█v███^███^█
█ █	█	█v>>█<<^>>█			█ █		█	█v	█<<^>>█
█ ███████ ███v███^███					█ ███████			███	███^███
█		█<<v█<<<<S█			█			█	█<<<<S█
█████████████████████					█████████████████████
	Алгоритм A*					Алгоритм A*
(расстояние L1)					(расстояние Чебышева)
█████████████████████					█████████████████████
█ █<<<<<<<<<<^█				█	█ █<<<<<<<<<<^█					█
█ ███████v███^███ ███					█ ███████v███^███ ███
█	E<<<v> █<<^█			█	█		E<<<v> █<<^█ <^█
█ ███████████v█^█ █ █					█ ███████████v█^█ █^█
█	█ █ █ <v█^█ █ █				█	█	█	█<<v█^█ █^█
███ █ █ █ █ ███^███^█					███ █ █ █			█v███^███^█
█ █	█	█	█<<^>>█		█ █		█	█v> █<<^>>█
█ ███████ ███			███^███		█ ███████			███	███^███
█		█	█<<<<S█		█			█	█<<<<S█
█████████████████████					█████████████████████

Алгоритм A* (расстояние Евклида)

█████████████████████

█ █<<<<<<<<<<^█ █

█ ███████v███^███ ███

█ E<<<v> █<<^█ <^█

█ ███████████v█^█ █^█

█	█		█	█<<v█^█ █^█
███ █		█	█	█v███^███^█
█ █		█		█v> █<<^>>█
█ ███████				███ ███^███
█				█ █<<<<S█

█████████████████████

Найденный путь ( , ): (9, 19), (9, 18), (9, 17), (8, 17), (7, 17), (7, 16), (7, 15), (6, 15), (5, 15), (4, 15), (3, 15), (3, 14), (3, 13), (2, 13), (1, 13), (1, 12), (1, 11), (1, 10), (1, 9), (2, 9), (3, 9), (3, 8), (3, 7), (3, 6), (3, 5).

Длина пути: 25.

38

										Таблица 21

Исходный лабиринт						Итеративный поиск в ширину
█████████████████████							█████████████████████
█		█	█	█			█<<<<^>>█^>>>>> █			█
█████ ███ ███████ ███							█████^███^███████ ███
█	S █ █			█ █			█<<<S>█^█^>>>>>>> █ █
█████ █ █ █████████ █							█████v█^█^█████████ █
█	█	█		█ █			█<<^█v>>█^>>>>>>>>█ █
█ █ █ █ █ █████████ █							█v█^█v█v█^█████████ █
█ █ █ █				█			█ █^█v█v>>>>>>>>>>>>█
█ █ ███ █ █ ███			█ ███				█ █^███v█v█v███v█v███
█ █		█ █ █	█E	█			█ █<<<<v█v█v█<<v█E			█
█████████████████████							█████████████████████
Алгоритм Дейкстры								Алгоритм A*
Алгоритм Дейкстры							(октильное расстояние)
							(октильное расстояние)
█████████████████████							█████████████████████
█<<<<^>>█^>>>>> █				█			█	<<^>>█	█	█
█████^███^███████ ███							█████^███ ███████ ███
█<<<S>█^█^>>>>>>> █ █							█<<<S>█^█			█ █
█████v█^█^█████████ █							█████v█^█ █████████ █
█<<^█v>>█^>>>>>>>>█ █							█	█v>>█^		█ █
█v█^█v█v█^█████████^█							█ █ █v█v█^█████████ █
█ █^█v█v>>>>>>>>>>>>█							█ █ █v█v>>>>>>>>>>>>█
█ █^███v█v█v███v█v███							█ █ ███v█v█v███v█v███
█ █<<<<v█v█v█<<v█E				█			█ █	<<v█v█v█<<v█E		█
█████████████████████							█████████████████████
	Алгоритм A*							Алгоритм A*
(расстояние L1)							(расстояние Чебышева)
█████████████████████							█████████████████████
█	^	█	█	█			█<<<<^>>█		█	█
█████^███ ███████ ███							█████^███ ███████ ███
█ <<S>█^█				█ █			█<<<S>█^█^			█ █
█████v█^█ █████████ █							█████v█^█^█████████ █
█	█v>>█^			█ █			█	█v>>█^>>>>>>		█ █
█ █ █v█v█^█████████ █							█ █ █v█v█^█████████ █
█ █ █v█v>>>>>>>>>>>>█							█ █ █v█v>>>>>>>>>>>>█
█ █ ███v█v█v███v█v███							█ █ ███v█v█v███v█v███
█ █	<<v█v█v█<<v█E			█			█ █	<<v█v█v█<<v█E		█
█████████████████████							█████████████████████
		Алгоритм A* (расстояние Евклида)
				█████████████████████
				█	<<^>>█	█	█
				█████^███ ███████ ███
				█<<<S>█^█			█ █
				█████v█^█^█████████ █
				█	█v>>█^>		█ █
				█ █ █v█v█^█████████ █
				█ █ █v█v>>>>>>>>>>>>█
				█ █ ███v█v█v███v█v███
				█ █	<<v█v█v█<<v█E		█
				█████████████████████
Найденный путь ( , ): (3, 4), (3, 5), (4, 5), (5, 5), (5, 6), (5, 7), (6, 7), (7, 7), (7, 8),
(7, 9), (7, 10), (7, 11), (7, 12), (7, 13), (7, 14), (7, 15), (7, 16), (7, 17), (8, 17), (9, 17).
				Длина пути: 20.

39

									Таблица 22

Исходный лабиринт				Итеративный поиск в ширину
█████████████████████					█████████████████████
█	█	█	█		█<^>>>>>█<^>>>>>█				█
██S███ ███ ███ ███ ██					██S███v███^███v███ ██
█	█	█	█		█<	v	>>>>>>>>>█<^>█ █
██ ███ ███ ███ ███ ██					██v███v███v███^███^██
█			█		█<v>>>>>>>>>>>>>>>>>█
██ ███ ███ ███ ███ ██					██v███v███v███v███v██
█	█ █	█	█		█<v>>>>>█<v>█<v>█				█
██ ███ ███ ███ ███ ██					██v███v███v███v███ ██
█	█ █	E	█		█<v>█<v>█<v>>>>E				█
█████████████████████					█████████████████████
Алгоритм Дейкстры							Алгоритм A*
					(октильное расстояние)

█████████████████████					█████████████████████
█<^>>>>>█<^>>>>>█			█		█<^>>>>>█<^>			█	█
██S███v███^███v███ ██					██S███^███^███ ███ ██
█<v>>>>>>>>>█<v>█ ^ █					█<v>>>>>>>>>█ ^ █				█
██v███v███v███^███^██					██v███v███v███^███ ██
█<v>>>v>>>v>>>>>>>>>█					█<v>>>v>>>v>>>>>>>				█
██v███v███v███v███v██					██v███v███v███v███ ██
█<v>>>v>█<v>█<v>█ v █					█<v>>>v>█<v>█<v>█				█
██v███v███v███v███ ██					██v███v███v███v███ ██
█<v>█<v>█<v>>>vE			█		█<v>█<v>█<v>>>vE				█
█████████████████████					█████████████████████
	Алгоритм A*						Алгоритм A*
(расстояние L1)					(расстояние Чебышева)
█████████████████████					█████████████████████
█<^>	^ █ ^	█	█		█<^>>>>>█<^>>>			█	█
██S███^███^███ ███ ██					██S███v███^███ ███ ██
█<v>>>>>>>>>█ ^ █			█		█<v>>>>>>>>>█ ^ █				█
██v███v███v███^███ ██					██v███v███v███^███ ██
█<v>>>v>>>v>>>>>>>			█		█<v>>>v>>>v>>>>>>>				█
██v███v███v███v███ ██					██v███v███v███v███ ██
█<v>>>v>█<v>█<v>█			█		█<v>>>v>█<v>█<v>█				█
██v███v███v███v███ ██					██v███v███v███v███ ██
█<v>█<v>█<v>>>vE			█		█<v>█<v>█<v>>>vE				█
█████████████████████					█████████████████████
		Алгоритм A* (расстояние Евклида)
			█████████████████████
			█<^>>>>>█<^>	█	█
			██S███^███^███ ███ ██
			█<v>>>>>>>>>█ ^ █		█
			██v███v███v███^███ ██
			█<v>>>v>>>v>>>>>>>		█
			██v███v███v███v███ ██
			█<v>>>v>█<v>█<v>█		█
			██v███v███v███v███ ██
			█<v>█<v>█<v>>>vE		█
			█████████████████████
Как видим, длина пути (21) одинаковая, но сами пути могут быть разными.
Кратчайший путь поиска в ширину ( , ): (2, 2), (3, 2), (4, 2), (5, 2), (5, 3), (5, 4),
(5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (6, 10), (7, 10), (8, 10), (9, 10), (9, 11), (9, 12),
			(9, 13), (9, 14), (9, 15).
Кратчайший путь остальных алгоритмов ( , ): (2, 2), (3, 2), (3, 3), (3, 4), (3, 5),
(3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (4, 10), (5, 10), (5, 11), (5, 12), (5, 13), (5, 14), (6, 14),
		(7, 14), (8, 14), (9, 14), (9, 15).

40

Материал: АиСД. Проектная работа

Смотрите также: