Node Expansion

The frontier is the set of all generated nodes that are awaiting expansion. It is the algorithm's working memory, representing the boundary between explored and unexplored states. The order in which nodes are selected from the frontier defines the search strategy:

• Queue (FIFO): Results in Breadth-First Search.
• Stack (LIFO): Results in Depth-First Search.
• Priority Queue: Used by informed algorithms like A* and Uniform-Cost Search, where priority is determined by a cost function f(n) = g(n) + h(n).

The successor function is a problem-specific operator that defines the legal state transitions from a given node. It is the engine of state space generation. For a node representing state s, the successor function returns the set of states {s'} reachable by applying all valid actions a ∈ A(s). In a pathfinding problem, this might generate neighboring grid cells. In a puzzle like the 8-puzzle, it generates states resulting from sliding a tile into the empty space.

The explored set (or closed list) is a record of all nodes that have already been expanded. Its primary purpose is to prevent redundant work and infinite loops in graph search by ensuring the same state is not expanded multiple times. This is critical for efficiency in domains with many paths to the same state. Algorithms like A* for graph search maintain this set, while tree search variants (which assume no cycles) do not.

During expansion, each new child node is annotated with key metrics that guide the search:

• Path Cost (g(n)): The cumulative cost from the start node to the current node n. This is updated as g(child) = g(parent) + cost(action).
• Heuristic Estimate (h(n)): An admissible heuristic provides an optimistic estimate of the cost from n to the goal, informing algorithms like A*.
• Total Estimated Cost (f(n)): The sum f(n) = g(n) + h(n), which serves as the priority for node selection in best-first algorithms.

The data structure underlying the search process dictates how node expansion handles state revisits:

• Tree Search: Treats every generated node as unique, even if it represents a previously visited state. This is simpler but can lead to infinite loops in cyclic spaces. It does not use an explored set.
• Graph Search: Explicitly checks for and avoids expanding duplicate states by maintaining an explored set. This is more memory-intensive but guarantees termination in finite spaces and is essential for optimality in algorithms like A* on graphs.

The branching factor (average number of successors per node) directly impacts the cost of expansion. A high branching factor causes exponential growth in the frontier, known as combinatorial explosion. Techniques to manage this include:

• Pruning: Eliminating branches that are provably suboptimal (e.g., Alpha-Beta pruning in game trees).
• Beam Width: Limiting the number of nodes retained at each depth (Beam Search).
• Heuristic Guidance: Using h(n) to focus expansion on the most promising regions of the state space, drastically reducing the number of nodes expanded before finding a solution.

The search frontier, often called the open list, is the set of all nodes generated by a search algorithm that are candidates for expansion. It represents the boundary between explored and unexplored states. The algorithm's strategy (e.g., FIFO for BFS, priority queue for A*) determines which node is popped from the frontier for the next expansion cycle. Managing the frontier is critical for memory efficiency and search direction.

The successor function is the problem-specific operator applied during node expansion. Given a state (node), it defines all possible next states reachable by taking a single valid action. For example, in a pathfinding grid, the successor function generates adjacent cells. In chess, it generates all legal moves from the current board. The quality and efficiency of this function directly determine the branching factor and the shape of the search tree.

A heuristic function, denoted h(n), estimates the cost from a node n to the nearest goal state. It is the "intelligence" guiding informed search algorithms like A* or Greedy Best-First Search. Key properties include:

• Admissibility: Never overestimates the true cost (required for A* optimality).
• Consistency (Monotonicity): The estimated cost of reaching the goal from a node is not greater than the step cost to its successor plus the estimated cost from that successor. Effective heuristics dramatically reduce the number of nodes expanded.

The branching factor is the average number of successor states generated by the successor function when a node is expanded. A high branching factor (e.g., in Go: ~250) causes exponential growth in the search tree, making exhaustive search intractable. Search algorithm performance is often analyzed in terms of the effective branching factor, which heuristic guidance aims to reduce. Techniques like pruning and beam search explicitly limit the branching factor to control computational cost.

This distinction determines how a search algorithm handles repeated states, impacting the necessity and method of node expansion.

• Tree Search: Can expand the same state multiple times if reached via different paths, leading to redundant work and potential infinite loops in cyclic graphs. It uses only a frontier.
• Graph Search: Maintains an additional closed set (explored set) of all expanded nodes. Before adding a successor to the frontier, it checks if the state is already in the closed set, preventing re-expansion. This guarantees termination in finite spaces but increases memory overhead.

The evaluation function, f(n), is used to assign a priority to nodes in the frontier, determining the order of expansion. Its composition defines the search algorithm:

• Uniform-Cost Search: f(n) = g(n) (cost from start).
• Greedy Best-First Search: f(n) = h(n) (heuristic to goal).
• A Search*: f(n) = g(n) + h(n) (total estimated path cost). During node expansion, the node with the most promising f(n) value (e.g., lowest cost) is selected. Designing f(n) is the central challenge in creating an efficient, optimal search.