why & how are BFS nodes goal tested when they are generated?

Question

In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?

Answer 1

The question makes sense as is and it, indeed, stands for a very important difference in how search algorithms are implemented.

Before moving further, let us refer to basic concepts that were certainly defined in your course material:

Definition 1 [Generation of a node] A node $n$ is generated when a data structure representing its contents is created, i.e., when it is allocated in main memory.

Definition 2 [Expansion of a node] A node $n$ is expanded when all its children are generated.

In general, all brute-force search algorithms (or uninformed as they are usually termed in modern literature) "goal test" nodes when they are generated. There is no reason to modify this decision as it suffices for preserving the main properties of search algorithms. Since you mention Breadth-First Search (BFS), let us review its main properties:

Lemma 1 [Completeness of BFS] Breadth-First Search is complete, i.e., it is guaranteed to find a solution, provided that any exists.

The proof is very simple. It just suffices to observe that by storing nodes in a queue, nodes at depth $d$ are expanded only if all nodes at depth $(d-1)$ have been expanded. Conversely, nodes at depth $d$ will surely be expanded, immediately after all nodes at depth $(d-1)$ have been expanded. Hence, it does not matter where the solution node hides, it will be certainly found even if the graph is infinite (but not locally infinite, i.e., solutions might not be found if there are nodes with an infinite number of descendants).

Lemma 2 [Admissibility of BFS] Breadth-First Search is admissible, i.e., it is guaranteed to find optimal solutions provided that any exist.

This is true if edge costs are neglected. Thus, cost of a solution path equals its depth. Since BFS only expands nodes at depth $d$ after expanding all nodes at the preceding depths, once a solution is found, it can be guaranteed to be optimal since we already tested all paths of shorter lengths (or, equivalently, costs).

There's the trick! If edge costs are neglected, then there is a correspondence between path cost and path length.

Now, what about searching in graphs with arbitrary costs? Best-First Search algorithms (termed also as BFS, but I will not to avoid confusion with the preceding algorithm) are devised to handle this case specifically. Dijkstra is one among many algorithms in the family of Best-First Search algorithms.

In this case (i.e., with arbitrary costs), there is not a correspondence anymore between path length and path cost. Hence, an algorithm can not stop once a goal has been generated if admissibility if desired (i.e., the property that guarantees that solutions found are also optimal). Instead, we keep on generating nodes and inserting them in ascending order of cost. This way, once a goal is about to be expanded (and only when it is about to be expanded!) we can certainly ensure that it is an optimal solution, because: (1) all the other nodes in open have a cost which is larger or equal; (2) path cost is assumed to grow monotonically (i.e., negative edge costs are not allowed).

As I said at the beginning, the stopping condition (whether to stop when the goal is generated, or when it is about to be expanded) is critical for the good behaviour of search algorithms. Indeed, many people believe that A$^*$ (which is also a Best-First Search algorithm) with a null heuristic ($h(n)=0, \forall n$) is equivalent to Breadth-First Search. This is not true as there is a critical difference in the stopping condition.

For more details about this, I would recommend you to look at Robert C. Holte. Common Misconceptions Concerning Heuristic Search. Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS-2010), pp. 46-51 and, specifically, to page 49.

Hope this helps,