Using Monte Carlo simulations, we can empirically verify some earlier conclusions about DFS and BFS search.
Test 1
10x10 labyrinth, start = (0, 0), end = (9, 9). end may not be a leaf. Fixed random seed for labyrinth generation, variable random seed for the search. Results:
DFS, empirical figures, 1000 iterations
N=10, M=10
Path length avg: 21.0, std: 0.0
Search cost avg: 96.8, std: 44.6
BFS, empirical figures, 1000 iterations
N=10, M=10
Path length avg: 21.0, std: 0.0
Search cost avg: 98.0, std: 0.0
This confirms that BFS has small variability when the labyrinth is fixed, but DFS still has high variability. Both algorithms have on average the same cost (also happens to be about the same as the number of nodes)
Test 2
10x10 labyrinth, start = (0, 0), end = (4, 4). end may not be a leaf. Variable random seed for labyrinth generation, variable random seed for the search. Results:
DFS, empirical figures, 1000 iterations
N=10, M=10
Path length avg: 15.0, std: 7.0
Search cost avg: 81.5, std: 56.3
BFS, empirical figures, 1000 iterations
N=10, M=10
Path length avg: 15.6, std: 7.5
Search cost avg: 64.4, std: 36.5
Here we see that BFS has a lower cost on average. This is reasonable, as end is typically on a lower depth when it is in the middle of the random labyrinth.
To make it possible to do so many iterations, I had to optimize connect_labyrinth:
A quick test gives that N=10000 nodes in the labyrinth takes 0.25 seconds and N=99225 (=315^2) nodes takes 7.94 seconds. With the old algorithm, connecting with N=10000 nodes took over 100 seconds.
To make it possible to do so many iterations, I had to optimize connect_labyrinth:
A quick test gives that N=10000 nodes in the labyrinth takes 0.25 seconds and N=99225 (=315^2) nodes takes 7.94 seconds. With the old algorithm, connecting with N=10000 nodes took over 100 seconds.
Inga kommentarer:
Skicka en kommentar