A rooted tree whose nodes are partial search states and whose children are possible next choices. Leaves represent completed candidates or terminated branches. Backtracking traverses this tree while storing the current path, and search pruning removes branches that cannot yield a useful completion.
The number of action edges between a search node and the root of its search tree. It is zero at the root. When every step costs more than , a positive-depth node satisfies , connecting depth finiteness to path cost bounds.
An entry in a search tree representing a particular action history. It normally stores the current state, its parent, its last action and accumulated path cost . Distinct search nodes can represent the same state; identifying them changes tree search into a form of graph search and requires an appropriate repeated-state policy.
The generated but unexpanded search nodes maintained by a search algorithm. Best-first search selects the next expansion from this frontier using a priority queue or an equivalent ordering operation. A lower-bound argument about a frontier node on an optimal path is central to A-star search correctness.
The number of children of a node in a search tree, or an upper bound on that number over the tree. With branching factor at most and depth at most , a complete traversal visits at most nodes.
Articles by others on the same topic
A **search tree** is a data structure that is used to represent different possible states or configurations of a problem, allowing for efficient searching and decision-making. It is particularly useful in algorithm design, artificial intelligence, and combinatorial problems. The structure can help in exploring paths or options systematically to find a solution or optimize a given objective. ### Characteristics of Search Trees: 1. **Nodes**: Each node in a search tree represents a potential state or configuration in the problem.