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

Sidewinder algorithm: 5.890625 Wilson's algorithm: 6.03125 Kruskal's algorithm: 6.1875 Growing tree algorithm: 6.40625 Eller's algorithm: 6.984375 Aldous-Broder algorithm: 7.578125 Division algorithm: 8.125 Backtracking algorithm: 8.15625

##############################

Function: Dijkstra algorithm Backtracking algorithm: 5.609375 Aldous-Broder algorithm: 5.90625 Kruskal's algorithm: 6.140625 Eller's algorithm: 6.15625 Prim's algorithm: 6.234375 Sidewinder algorithm: 6.28125 Wilson's algorithm: 6.46875 Growing tree algorithm: 6.546875 Division algorithm: 6.90625 Binary tree algorithm: 7.015625

Prim's algorithm (modified): 7.1875

=== Imperfect algorithms ===

Enter the number of tests (1-100000):100

Enter the minimum length of the maze (odd number) (5-100000):200 Enter the maximum length of the maze (odd number) (5-100000):200 Time of execution of maze generation algorithms

Serpentine algorithm: 0.5 Small rooms algorithm: 1.484375 Spiral algorithm: 5.375

Time of execution of algorithms to find the shortest paths in the mazes (briefly) BFS algorithm: 10.796875

A* algorithm (Manhattan heuristic): 13.4375 A* algorithm (Octile heuristic): 16.40625

A* algorithm (Chebyshev heuristic): 16.515625 Dijkstra algorithm: 17.8125

A* algorithm (Euclidean heuristic): 17.921875

Time of execution of algorithms to find the shortest paths in the mazes (in detail)

##############################

Function: BFS algorithm Serpentine algorithm: 3.453125 Spiral algorithm: 3.53125 Small rooms algorithm: 3.8125

##############################

Function: A* algorithm (Manhattan heuristic) Small rooms algorithm: 1.59375

Spiral algorithm: 5.8125 Serpentine algorithm: 6.03125

##############################

Function: A* algorithm (Octile heuristic) Small rooms algorithm: 3.125

Spiral algorithm: 6.5 Serpentine algorithm: 6.78125

##############################

Function: A* algorithm (Chebyshev heuristic) Small rooms algorithm: 3.796875

Serpentine algorithm: 6.359375 Spiral algorithm: 6.359375

##############################

Function: Dijkstra algorithm Serpentine algorithm: 5.25 Spiral algorithm: 5.734375 Small rooms algorithm: 6.828125

##############################

Function: A* algorithm (Euclidean heuristic) Small rooms algorithm: 3.28125

Spiral algorithm: 7.171875 Serpentine algorithm: 7.46875

61

СПИСОК ЛИТЕРАТУРЫ

1.Think Labyrinth: Maze algorithms [Электронный ресурс]. – Режим доступа: https://www.astrolog.org/labyrnth/algrithm.htm, свободный – (28.05.2020).

2.Implementation of A* [Электронный ресурс]. – Режим доступа: https://www.redblobgames.com/pathfinding/a-star/implementation.html, свободный – (28.05.2020).

3.Aldous–Broder algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm.html, свободный – (28.05.2020).

4.Wilson's algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm, свободный

–(28.05.2020).

5.Backtracking algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking, свободный – (28.05.2020).

6.Binary Tree algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/2/1/maze-generation-binary-tree-algorithm.html, свободный – (28.05.2020).

7.Division algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm, свободный – (28.05.2020).

8.Eller's algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm, свободный

–(28.05.2020).

9.Growing Tree algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm, свободный – (28.05.2020).

10.Kruskal's algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm, свободный

– (28.05.2020).

11.Prim's algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm.html, свободный – (28.05.2020).

12.Sidewinder algorithm [Электронный ресурс]. – Режим доступа: https://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-algorithm.html, свободный – (28.05.2020).

62