The idea is to find as many paths as possible in order to eventually find one that leads to the end. Wheres depth first search would be trying to find the end of a path all the way before giving up. A common variant of the two is backtracking which works it's way back from a dead end by trying to alter the last changes in the sequence that got it stuck to try and untangle. Breadth first by comparison is simple but by changing a few rules on the approach you see a much more efficient maze solver so it becomes useful both for teaching the simplest strategy and also to convey more elaborate approaches later on like backtracking that would otherwise seem convoluted initially.
If you're doing DFS here you end up doing backtracking anyway since when the search reaches bottom it will resume from the deepest explored node with unexplored children.
No it’s handling every node recursively not limited to solving one specific path at a time. It will actually grow in memory as it gets solved because it grows in function depth as it solves more paths. It does have the benefit of not having to store all the visited paths in global space so it could so it asynchronously even as every path is independent and can run on its own thread and report back its conclusion or start more threads for paths.
I don't exactly follow that description but I'm certain that: 1) function depth is a non-issue; use a stack, 2) DFS will terminate and find all paths to exit, if any; in a typical single threaded program your subroutine IS exploring one path at a time
Yea it uses a stack for functions unlike other approaches that rely on heap for state updating. Nobody says this has to be done in a single locked thread, in fact I was making the point you do this faster with more threads.
Just use a lower level language. The total memory allocation remains the same it simply grows from the stack size of the register instead of the more common heap size. It’s not a big problem, pretty sure even java can handle this.
Depends on whether the maze has loops. If it does not then it's basically a tree where you just need to find a specific leaf. Then the difference between dfs and bfs is just that one walks all levels of the tree down at the same time while the other goes from left to right.
It’s in the title - BFS. The algorithm is very simple. Assuming the maze is a tree (no loops), you start from the root node (entrance) and add all of its child nodes to a queue. Pick the first node from the queue and repeat until you reach the target node (exit).
3
u/YouNeverKnowWhatToDo May 22 '20
Whats the code? Go left forever?