Материал: АиСД. Проектная работа
|
|
|
|
|
|
|
|
Таблица 23 |
|
|
|
||||||
Исходный лабиринт |
|
Итеративный поиск в ширину |
||||||
█████████████████████ |
|
█████████████████████ |
||||||
█ █ |
|
█ |
█ |
█ |
|
█^█ |
|
█<<<<^█<<<<^█ |
█ █ ███ █ ███ █ ███ █ |
|
█^█ ███ █v███^█v███^█ |
||||||
█ █ |
|
█E |
█ █ █ |
█ |
|
█^█ |
|
█E<v█^█<<v█^>>█ |
█ ███ █████ █████ ███ |
|
█^███ █████^█████^███ |
||||||
█ |
█ |
█ |
█ |
█ █ |
|
█^>>█ |
█<<<<^█^>>█^█ |
|
█ █ █████ ███ █ ███ █ |
|
█^█v█████v███^█^███^█ |
||||||
█ █ █ |
|
█ █ █ █ |
█ |
|
█^█v█<<<<v█^█^█^█<<^█ |
|||
█ ███ █████ █ █ █ █ █ |
|
█^███v█████^█^█^█v█^█ |
||||||
█ |
|
|
█ |
█S█ |
|
█<<<<v>>>>>>█<<<<v█S█ |
||
█████████████████████ |
|
█████████████████████ |
||||||
Алгоритм Дейкстры |
|
|
Алгоритм A* |
|||||
|
(октильное расстояние) |
|||||||
|
|
|
|
|
|
|||
█████████████████████ |
|
█████████████████████ |
||||||
█^█ |
|
█<<<<^█<<<<^█ |
|
█ █ |
|
█<<<<^█<<<<^█ |
||
█^█ ███ █v███^█v███^█ |
|
█ █ ███ █v███^█v███^█ |
||||||
█^█ |
|
█E<v█^█<<v█^>>█ |
|
█ █ |
|
█E<v█^█<<v█^>>█ |
||
█^███ █████^█████^███ |
|
█ ███ █████^█████^███ |
||||||
█^>>█ |
█<<<<^█^>>█^█ |
|
█ |
█ |
█<<<<^█^>>█^█ |
|||
█^█v█████v███^█^███^█ |
|
█ █ █████v███^█^███^█ |
||||||
█^█v█<<<<v█^█^█^█<<^█ |
|
█ █ █<<<<v█ █^█^█<<^█ |
||||||
█^███v█████^█^█^█v█^█ |
|
█^███v█████ █^█^█v█^█ |
||||||
█<<<<v>>>>>>█<<<<v█S█ |
|
█<<<<v>>>>>>█<<<<v█S█ |
||||||
█████████████████████ |
|
█████████████████████ |
||||||
|
Алгоритм A* |
|
|
|
Алгоритм A* |
|||
(расстояние L1) |
|
(расстояние Чебышева) |
||||||
█████████████████████ |
|
█████████████████████ |
||||||
█ █ |
|
█<<<<^█<<<<^█ |
|
█ █ |
|
█<<<<^█<<<<^█ |
||
█ █ ███ █v███^█v███^█ |
|
█ █ ███ █v███^█v███^█ |
||||||
█ █ |
|
█E<v█^█<<v█^>>█ |
|
█ █ |
|
█E<v█^█<<v█^>>█ |
||
█ ███ █████^█████^███ |
|
█ ███ █████^█████^███ |
||||||
█ |
█ |
█<<<<^█^>>█^█ |
|
█ |
█ |
█<<<<^█^>>█^█ |
||
█ █ █████v███^█^███^█ |
|
█^█ █████v███^█^███^█ |
||||||
█ █ █<<<<v█ █^█^█<<^█ |
|
█^█ █<<<<v█ █^█^█<<^█ |
||||||
█ ███v█████ █^█^█v█^█ |
|
█^███v█████^█^█^█v█^█ |
||||||
█ <<<v>>>>> █<<<<v█S█ |
|
█<<<<v>>>>>>█<<<<v█S█ |
||||||
█████████████████████ |
|
█████████████████████ |
||||||
|
|
|
Алгоритм A* (расстояние Евклида) |
|||||
|
|
|
|
█████████████████████ |
|
|
||
|
|
|
|
█ █ |
█<<<<^█<<<<^█ |
|
|
|
|
|
|
|
█ █ ███ █v███^█v███^█ |
|
|
||
|
|
|
|
█ █ |
█E<v█^█<<v█^>>█ |
|
|
|
|
|
|
|
█ ███ █████^█████^███ |
|
|
||
|
|
|
|
█ |
█ █<<<<^█^>>█^█ |
|
|
|
|
|
|
|
█ █ █████v███^█^███^█ |
|
|
||
|
|
|
|
█ █ █<<<<v█ █^█^█<<^█ |
|
|
||
|
|
|
|
█^███v█████^█^█^█v█^█ |
|
|
||
|
|
|
|
█<<<<v>>>>>>█<<<<v█S█ |
|
|
||
|
|
|
|
█████████████████████ |
|
|
||
Найденный путь ( , ): (9, 19), (8, 19), (7, 19), (7, 18), (7, 17), (8, 17), (9, 17), (9, 16), |
||||||||
(9, 15), (8, 15), (7, 15), (6, 15), (5, 15), (5, 16), (5, 17), (4, 17), (3, 17), (3, 18), (3, 19), |
||||||||
(2, 19), (1, 19), (1, 18), (1, 17), (1, 16), (1, 15), (2, 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) |
|||||||
|
|
|
|
Длина пути: 39. |
|
|
||
41
|
3. РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ |
|
|||
|
ВРЕМЯ РАБОТЫ АЛГОРИТМОВ ГЕНЕРАЦИИ |
|
|||
|
|
ИДЕАЛЬНЫХ ЛАБИРИНТОВ |
|
||
|
|
КОЛИЧЕСТВО ТЕСТОВ: 100 |
|
||
.) |
200 |
|
|
|
|
180 |
|
|
|
|
|
(СЕК |
|
|
|
|
|
160 |
|
|
|
|
|
140 |
|
|
|
|
|
РАБОТЫ |
|
|
|
|
|
120 |
|
|
|
|
|
100 |
|
|
|
|
|
80 |
|
|
|
|
|
60 |
|
|
|
|
|
ВРЕМЯ |
|
|
|
|
|
40 |
|
|
|
|
|
20 |
|
|
|
|
|
0 |
50 |
100 |
150 |
200 |
|
|
|
||||
|
Бинарное дерево |
0,125 |
0,625 |
1,3125 |
2,625 |
|
Sidewinder |
0,140625 |
0,515625 |
1,09375 |
3,390625 |
|
Рекурсивное деление |
0,328125 |
1,34375 |
2,78125 |
5,515625 |
|
Backtracking |
0,59375 |
2,484375 |
5,859375 |
11,046875 |
|
Эллер |
0,484375 |
2,65625 |
6,9375 |
15,609375 |
|
Прим (мод) |
1,34375 |
5,59375 |
13,84375 |
29,890625 |
|
Олдос-Бродер |
4,0625 |
26,34375 |
73,046875 |
165,359375 |
|
Прим |
2,953125 |
17,921875 |
61,796875 |
180,84375 |
|
Краскал |
1,796875 |
17,484375 |
77,890625 |
283 |
|
Растущее дерево |
3,015625 |
31,078125 |
127,875 |
385,71875 |
|
Уилсон |
3,40625 |
30,1875 |
166,96875 |
525,765625 |
|
|
|
РАЗМЕР КВАДРАТНЫХ ЛАБИРИНТОВ |
|
|
|
ВРЕМЯ РАБОТЫ АЛГОРИТМОВ ГЕНЕРАЦИИ |
|
|||
|
|
НЕИДЕАЛЬНЫХ ЛАБИРИНТОВ |
|
||
|
|
КОЛИЧЕСТВО ТЕСТОВ: 100 |
|
||
.) |
6 |
|
|
|
|
|
|
|
|
|
|
(СЕК |
5 |
|
|
|
|
|
|
|
|
|
|
РАБОТЫ |
4 |
|
|
|
|
3 |
|
|
|
|
|
2 |
|
|
|
|
|
ВРЕМЯ |
1 |
|
|
|
|
0 |
50 |
100 |
150 |
200 |
|
|
|
||||
|
Змеевидный лабиринт |
0,0625 |
0,15625 |
0,390625 |
0,5 |
|
Маленькие комнаты |
0,140625 |
0,4375 |
0,96875 |
1,484375 |
|
Спиральный лабиринт |
0,53125 |
1,46875 |
3,125 |
5,375 |
|
|
|
РАЗМЕР КВАДРАТНЫХ ЛАБИРИНТОВ |
|
|
42
|
ВРЕМЯ РАБОТЫ АЛГОРИТМОВ ПОИСКА |
|
|||
|
КРАТЧАЙШИХ ПУТЕЙ В ИДЕАЛЬНЫХ ЛАБИРИНТАХ |
||||
|
|
КОЛИЧЕСТВО ТЕСТОВ: 100 |
|
||
.) |
70 |
|
|
|
|
|
|
|
|
|
|
(СЕК |
60 |
|
|
|
|
50 |
|
|
|
|
|
РАБОТЫ |
|
|
|
|
|
40 |
|
|
|
|
|
30 |
|
|
|
|
|
20 |
|
|
|
|
|
ВРЕМЯ |
|
|
|
|
|
10 |
|
|
|
|
|
0 |
50 |
100 |
150 |
200 |
|
|
|
||||
|
Поиск в ширину |
2,4375 |
9,5 |
20,8125 |
41,546875 |
|
A* Манхэттен |
2,828125 |
11,734375 |
27,296875 |
53,65625 |
|
A* Октиль |
3,53125 |
13,859375 |
31,65625 |
63,8125 |
|
A* Чебышев |
3,265625 |
14 |
32,0625 |
64,265625 |
|
A* Евклид |
3,765625 |
15,34375 |
34,953125 |
70,34375 |
|
Дейкстра |
3,671875 |
14,953125 |
34,8125 |
70,453125 |
|
|
|
РАЗМЕР КВАДРАТНЫХ ЛАБИРИНТОВ |
|
|
|
ВРЕМЯ РАБОТЫ АЛГОРИТМОВ ПОИСКА |
|
|||
|
КРАТЧАЙШИХ ПУТЕЙ В НЕИДЕАЛЬНЫХ |
|
|||
|
|
|
ЛАБИРИНТАХ |
|
|
|
|
КОЛИЧЕСТВО ТЕСТОВ: 100 |
|
||
.) |
18 |
|
|
|
|
16 |
|
|
|
|
|
СЕК |
|
|
|
|
|
14 |
|
|
|
|
|
( |
12 |
|
|
|
|
РАБОТЫ |
|
|
|
|
|
10 |
|
|
|
|
|
8 |
|
|
|
|
|
6 |
|
|
|
|
|
ВРЕМЯ |
4 |
|
|
|
|
2 |
|
|
|
|
|
0 |
50 |
100 |
150 |
200 |
|
|
|||||
|
|
||||
|
Поиск в ширину |
0,71875 |
2,8125 |
5,8125 |
10,796875 |
|
A* Манхэттен |
0,96875 |
3,34375 |
7,140625 |
13,4375 |
|
A* Октиль |
1,265625 |
3,90625 |
8,828125 |
16,40625 |
|
A* Чебышев |
1,171875 |
3,765625 |
8,59375 |
16,515625 |
|
Дейкстра |
1,375 |
4,28125 |
9,640625 |
17,8125 |
|
A* Евклид |
1,453125 |
4,3125 |
9,734375 |
17,921875 |
|
|
|
РАЗМЕР КВАДРАТНЫХ ЛАБИРИНТОВ |
|
|
43
|
ВРЕМЯ РАБОТЫ АЛГОРИТМОВ ПОИСКА |
|
|||||
|
КРАТЧАЙШИХ ПУТЕЙ В ЛАБИРИНТАХ РАЗМЕРА 200 |
||||||
|
|
КОЛИЧЕСТВО ТЕСТОВ: 100 |
|
|
|||
.) |
8 |
|
|
|
|
|
|
СЕК |
7 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
( |
|
|
|
|
|
|
|
РАБОТЫ |
5 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
ВРЕМЯ |
1 |
|
|
|
|
|
|
0 |
Поиск в |
A* |
|
|
|
|
|
|
A* Октиль |
A* Чебышев |
Дейкстра |
A* Евклид |
|||
|
ширину |
Манхэттен |
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
Бинарное дерево |
3,984375 |
4,265625 |
5,4375 |
5,4375 |
7,015625 |
5,8125 |
|
Sidewinder |
3,578125 |
4,171875 |
5,3125 |
5,609375 |
6,28125 |
5,890625 |
|
Рекурсивное деление |
4 |
6,78125 |
7,5625 |
7,234375 |
6,90625 |
8,125 |
|
Backtracking |
3,65625 |
6,359375 |
7,21875 |
6,65625 |
5,609375 |
8,15625 |
|
Эллер |
3,640625 |
5,5625 |
6,46875 |
6,3125 |
6,15625 |
6,984375 |
|
Прим |
3,578125 |
2,796875 |
3,828125 |
4,21875 |
6,234375 |
4,234375 |
|
Прим (мод) |
4,171875 |
3,140625 |
4,453125 |
4,734375 |
7,1875 |
4,9375 |
|
Краскал |
3,5625 |
4,90625 |
5,59375 |
5,78125 |
6,140625 |
6,1875 |
|
Уилсон |
3,8125 |
4,71875 |
5,46875 |
5,828125 |
6,46875 |
6,03125 |
|
Олдос-Бродер |
3,625 |
6,140625 |
6,78125 |
6,671875 |
5,90625 |
7,578125 |
|
Растущее дерево |
3,9375 |
4,8125 |
5,6875 |
5,78125 |
6,546875 |
6,40625 |
|
Змеевидный лабиринт |
3,453125 |
6,03125 |
6,78125 |
6,359375 |
5,25 |
7,46875 |
|
Спиральный лабиринт |
3,53125 |
5,8125 |
6,5 |
6,359375 |
5,734375 |
7,171875 |
|
Маленькие комнаты |
3,8125 |
1,59375 |
3,125 |
3,796875 |
6,828125 |
3,28125 |
|
|
|
РАЗМЕР КВАДРАТНЫХ ЛАБИРИНТОВ |
|
|||
Параметры тестирования
Язык: Python 3.7.6 (default) [MSC v.1916 64 bit (AMD64)] on win32. Операционная система: Microsoft © Windows 8.1 для одного языка.
Комментарий
Как можно заметить, алгоритм Олдоса – Бродера значительно обогнал по скорости алгоритм Уилсона на больших размерах лабиринтов (при 50 не обогнал). Это связано:
1.С хорошим распределением псевдослучайных чисел генератора (в случае алгоритма Олдоса – Бродера).
2.Со значительными накладными расходами на память (в случае алгоритма
Уилсона), в том числе на работу с памятью посредством самого языка.
Также можно заметить, что алгоритм поиска в ширину быстрее всех остальных в большинстве случаев, хотя A* имеет хорошие эвристики. Это связано:
1.С простотой работы самого алгоритма поиска в ширину.
2.С накладными расходами на память (в случае A* и Дейкстры) и на работу с памятью посредством самого языка.
3.С узкоспециализированными тестами. В случае с сеткой, имеющей гораздо большее количество свободных ячеек, накладные расходы A* будут гораздо меньше по сложности, чем обход в ширину алгоритмом поиска в ширину.
44
4.ВЫВОДЫ
Врезультате проделанной работы были проанализированы и реализованы:
•Алгоритмы создания идеальных лабиринтов (алгоритм бинарного дерева, алгоритм Sidewinder, алгоритм рекурсивного деления, алгоритм Эллера, алгоритм Recursive Backtracking, алгоритм Прима, модифицированный алгоритм Прима, алгоритм Краскала, алгоритм растущего дерева, алгоритм Олдоса–Бродера, алгоритм Уилсона).
•Алгоритмы создания неидеальных лабиринтов (алгоритм змеевидного лабиринта, алгоритм маленьких комнат, алгоритм спирального лабиринта).
•Алгоритмы поиска кратчайшего пути в лабиринтах (алгоритм поиска в ширину, алгоритм Дейкстры, алгоритм A*).
Все алгоритмы успешно справились со своей задачей.
Далее приведены распределения мест на основе результатов.
|
|
Таблица 24. Результаты |
|
|
|
Алгоритмы создания |
Алгоритмы создания |
Алгоритмы поиска |
идеальных лабиринтов |
неидеальных лабиринтов |
кратчайших путей |
(отсортированы по |
(отсортированы по |
(отсортированы по кол-ву |
увеличению времени |
увеличению времени |
возможностей настройки |
выполнения) |
выполнения) |
поиска) |
Sidewinder |
|
|
|
|
A* (расстояние Манхэттена) |
Алгоритм бинарного |
|
|
|
|
|
дерева |
Алгоритм змеевидного |
/ |
|
лабиринта |
|
|
||
|
|
|
Алгоритм рекурсивного |
|
A* (расстояние «Octile») |
деления |
|
|
|
|
|
|
|
/ |
Алгоритм Recursive |
|
|
Backtracking |
|
|
Алгоритм Эллера |
Алгоритм маленьких |
A* (расстояние Чебышёва) |
|
||
|
/ |
|
Алгоритм Прима |
комнат |
|
(модифицированный) |
|
|
|
|
A* (расстояние Евклида) |
Алгоритм Олдоса – |
|
|
|
|
|
Бродера |
|
|
Алгоритм Прима |
|
|
|
|
Алгоритм Дейкстры |
|
|
|
Алгоритм Краскала |
|
|
|
Алгоритм спирального |
|
Алгоритм растущего |
лабиринта |
|
|
|
|
дерева |
|
Поиск в ширину |
|
|
|
Алгоритм Уилсона. |
|
|
|
|
|
45