Note: this asynchronous material is part of EMA (Graph Applications in AI) and EMD (Graph Applications in Robotics). Its corresponding quizzes were native in Canvas and not reproduced here.
We very briefly discussed some graph/tree search algorithms (DFS, BFS, IDS, and UCS) in class. You may have also learned about several of them in other classes.
But when is a search algorithm a graph search algorithm and when is it a tree search algorithm?
The most salient difference is graph search algorithms do not create (duplicated) vertices/nodes/states, whereas tree search algorithms do.
In other words, the search tree for graph search algorithms contains at most one copy of each vertex in the state graph.
Again let’s use the division directed graph as an example.
- Suppose we run BFS tree search starting from vertex 1 without any precautions on avoiding repetitions.
- Then every vertex, including vertex 1 itself, will appear in level 1 (because there is indeed an edge from vertex 1 to every vertex including itself). So level-1 of the BFS tree will have all 12 vertices.
- Then, since vertex 1 is also in level 1, when it gets explored again, it will lead to all 12 vertices appearing in level 2 again as children of vertex 1, and so on.
- Therefore, if none of the states is the goal, the BFS tree has infinitely many levels/vertices and the search does not terminate.
- Instead, if we run BFS graph search starting from vertex 1, while also maintaining a set of visited vertices (so that we don’t revisit vertices again):
- Then every vertex other than vertex 1 will appear in level 1 (but vertex 1 itself does not). So level-1 will have 11 vertices.
- And since every vertex gets discovered already in level 1, we will not find any more unvisited vertices while exploring the vertices in level 1.
- Therefore, if none of the states is the goal, the BFS terminates after exploring level 1 and declares failure. The resulting tree will have exactly 12 vertices.
It feels graph search is inherently better, but the catch is again that it needs to maintain the set of visited vertices, which can use a prohibitive amount of memory (depending on the size of the problem).
