Searching in graphs trees with Depth/Breadth first/A* algorithms

Question

I have a couple of questions about searching in graphs/trees:

Let's assume I have an empty chessboard and I want to move a pawn around from point A to B.

A. When using depth-first search or breadth-first search must we use open and closed lists? This is a list that has all the elements to check, and others with all other elements that were already checked? Is it even possible to do it without having those lists? What about A*, does it need it?

B. When using lists, after having found a solution, how can you get the sequence of states from A to B? I assume when you have items in the open and closed list, instead of just having the (x, y) states, you have an "extended state" formed with (x, y, parent_of_this_node)?

C. State A has 4 possible moves (right, left, up, down). If I do as the first move left, should I let it in the next state come back to the original state? This, is, do the "right" move? If not, must I transverse the search tree every time to check which states I've been to?

D. When I see a state in the tree where I've already been, should I just ignore it, as I know it's a dead-end? I guess to do this I'd have to always keep the list of visited states, right?

E. Is there any difference between search trees and graphs? Are they just different ways to look at the same thing?

Answer 1

1.  An Open list keeps track of what you need to do, and the Closed List keeps track of what you have already done. With DFS you deed to store at least the current path. Otherwise, you would not be able to backtrack. Whereas in BFS you are required to maintain an open list. Otherwise, the algorithm simply can't work. When you additionally maintain a closed list, you will be able to detect and avoid cycles.

2. Yes, we have an "extended state" formed with (x, y, parent_of_this_node).  The closed list should form some kind of inverse tree (pointers going towards the root node), so you can extract the solution path. You will need the closed list for doing this. For DFS, your current stack is accurately the solution path, there is no need for a closed list.

3. I'm assuming that moving left and then moving right brings you to an equivalent state. In your case, you would have already explored the original state, it would be on the closed list, and therefore should not have been put back onto the open list. 

4. To avoid cycles with a closed list you don't have to expand nodes that are already inside the closed list. You also want to check the open list to ensure you're not planning to examine a given state twice. You don't need to explore any tree as such since you typically collect these things in linear structures.

5. The basic differences between them are:

• If performing a graph search, keep a "closed" list, that is, a list of nodes where the search has been completed.

• If performing a tree search, we don't keep this closed list.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial and Artificial Intelligence Course. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.