solve a maze by using DFS, BFS, A*

Question

I want to know the change in results when we use open maze or closed maze for the DFS, BFS, and A* search algorithms? Is there any big difference in the output like increase in number of expanded nodes, cost, etc.?

Answer 1

A naive DFS can go into an infinite loop on certain open mazes, whereas on a closed maze it will always finish. I don't think BFS or A* can fall into that trap. (By "naive DFS" I mean one that doesn't mark nodes as "visited" as it traverses them.) Edit: Daniel's comment has forced me to rethink this answer in the light of day rather than the sleepy moments before I went to bed. I will concede that A* marks nodes as visited as part of its basic functioning. However, I still think BFS can solve even open mazes without marking nodes. It won't be efficient, but if there is a solution to the maze, BFS will find it. By definition, it is trying all possible paths at a certain depth before moving onto the next depth. So if a solution exists with length 10, BFS will find it before trying any solutions of depth 11.

Answer 2

Yes. There is a big difference as the different strategies traverse the maze in totally different orders

Answer 3

A* can be quite efficient compared to naive dfs and bfs. But you need to find a good function to evaluate the cost from your current position to the target.