Search in tree graphs with depth / width algorithms of the first / A *

Question

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

Suppose I have an empty chessboard and I want to move the pawn from point A to B.

a. When you first search or search in depth, first we must use open and closed lists? Is it a list that contains all the items to check, and others with all the other items that have already been checked? Is it possible to do this without these lists? What about A *, is it necessary?

Q. When using lists, after you have found a solution, how can you get a sequence of states from A to B? I assume that when you have items in a public and private list, instead of having only (x, y) states, do you have an "extended state" generated with (x, y, parent_of_this_node)?

C. State A has 4 possible movements (right, left, up, down). If I take the first step to the left, should I allow it to return to its original state in the next state? Is this the “right” step? If not, do I have to alternate the search tree each time to check which states I was in?

D. When I see the state in the tree where I was already, should I just ignore it, because I know that this is a dead end? I assume that for this I will always have to keep a list of visited states, right?

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

Answer 1

a. When you first search for the depth or breadth of the first search, should we use open and closed lists?

With DFS, you definitely need to keep at least the current path. Otherwise, you cannot retreat. If you decide to keep a list of all visited (closed) nodes, you can detect and avoid loops (expanding the same node more than once). On the other hand, you no longer have DFS space efficiency. DFS without a private list requires space proportional to the depth of the search space.

With BFS, you need to keep an open list (sometimes called fringe). Otherwise, the algorithm simply cannot work. When you additionally maintain a closed list, you (again) will be able to detect / avoid loops. With BFS, the extra space for a private list might not be that bad, since you should still support fringe. The ratio between the size of the strip and the size of the closed list is highly dependent on the structure of the search space, so this should be considered here. For instance. for branch coefficient 2, both lists are equal in size, and the effect of having a closed list does not seem very bad compared to its advantages.

How about A *, is it necessary?

A *, since it can be considered as some special (informed) type of BFS, an open list is needed. Lowering a closed list is more delicate than with BFS; also deciding on updating costs in a closed list. Depending on these solutions, the algorithm may no longer be optimal and / or complete depending on the type of heuristic used, etc. Here I will not go into details.

IN.

Yup, a closed list should contain some kind of inverse tree (pointers go to the root of the node), so you can extract the solution path. For this, you usually need a private list. For DFS, your current stack is exactly the solution (there is no need to close the list here). Also note that sometimes you are not interested in the path, but only in the solution or its existence.

FROM.

Read the previous answers and find the parts that talk about loop detection.

D.

To avoid closed list loops: do not expand nodes that are already in the closed list. Note: given startup costs (remember A *), things can get more complicated.

E. Is there a difference between looking for trees and graphics?

You can consider a search that supports a closed list to avoid loops in the form of graphical queries and those that do not have a single tree search.

Answer 2

A) You can avoid open / closed lists - you can try all possible ways, but it will take a VERY long time.

B) Once you have reached the goal, you use the parent_of_this_node information to "walk backward" from the goal. Start with the goal, get its parent, get the parent parent, etc., until you reach the beginning.

C) I think it doesn’t matter. This is not to say that the step you described will lead to a shorter path (if your steps do not have a negative weight, in which case you cannot use Dijkstra / A *). In my A * code, I check this case and ignore it, but I do everything that is easiest to code.

D) It depends - I believe that Dijkstra will never be able to reopen the same node (can someone correct me about this?). A * can definitely go back to node - if you find a shorter path to the same node, you will save this path, otherwise you will ignore it.

E) Not sure, I never did anything specifically for trees.

There is a good introduction to * here: http://theory.stanford.edu/~amitp/GameProgramming/ which contains many details on how to implement an open set, select a heuristic, etc.

Answer 3

a. Open and closed lists are general implementation details, and not part of the algorithm itself. It usually happens that a tree search by depth is not performed by any of them, for example, the canonical path is a recursive tree traversal.

B. It is typical for nodes to refer to previous nodes, allowing you to reconstruct the plan by following the backlinks. Alternatively, you just keep the whole solution so far in every candidate, although then it would be wrong to call it node really.

C. I assume that moving to the left and then moving to the right will lead you to an equivalent state - in this case you would have already examined the initial state, it would have been in a closed list and therefore should not have been returned to the open list. You do not go through the search tree every time, because you save a closed list, which is often implemented as an O (1) structure - just for this purpose - to know which states have already been fully studied. Please note that you cannot always assume that being in the same position is the same as being in the same state - for most purposes of finding a way to a game, this is true, but for a general search it is not.

D. Yes, a list of visited states is what you call a closed list. You also want to check the open list to make sure you are not planning to double-examine this condition. You do not need to look for any tree as such, since you usually store these things in linear structures. The algorithm as a whole searches for a tree (or graph) and generates a tree (of nodes representing the state space), but you are not looking at the explicit structure at any point in the algorithm.

E. A tree is a type of graph in which there are no loops / loops. Therefore, you also use the same graph search procedure to search. Usually a tree structure is created representing your search on a graph that is implicitly represented by backlinks from each node in the node that preceded / generated it in the search. (Although, if you go down the path of saving the entire plan in each state, there will be no tree, just a list of partial solutions.)