Best-First Search

Best-First Search is a class of search algorithms which explores a regular undirected graph. Its central organizing principle is the ordering of frontier nodes by an evaluation function , which determines which node is selected at each iteration.

State-Space Graphs and Induced Search Trees

While most problems are defined over a state-space graph whose vertices are states and edges correspond to actions, many domains of interest have no explicit graph representation available a priori. This setting is often referred to as implicit graph search, since the reachable portion of the state space is revealed only through successor generation during search.

It is useful to distinguish a state from a search node. A state represents a configuration of the environment, whereas a search node represents a particular path (i.e. a sequence of actions). We often use the phrase “the state represented by node ” to denote the state reached by executing the actions sequence associated with from the initial state.

Tip

This distinction matters because the same state may be reachable via multiple action sequences, leading to multiple distinct search nodes that correspond to the same underlying state.

This also motivates the distinction between the state-space graph and the search tree. The state-space graph contains a single vertex per state and edges induced by the transition dynamics. In contrast, the search procedure induces a (conceptual) search tree whose nodes correspond to action sequences: the root corresponds to the empty sequence at the initial state, and each tree edge corresponds to appending one action to a partial path. Consequently, the same underlying state can appear multiple times in the search tree at different nodes.

In an implicit setting, search proceeds by incrementally constructing a partial search tree rooted at the initial state. At any point in time, the current (partial) search tree consists of all search nodes that have been generated so far during exploration. We refer to generated but unexpanded nodes as the frontier (or OPEN list), and expanded nodes as the CLOSED set. With this convention, the leaves of the current partial search tree are the frontier nodes in OPEN (though a node in CLOSED may also be a leaf if it has no applicable actions and therefore generates no children).

The Best-First Search Framework

Best-first search provides a general template for implicit graph search. It maintains OPEN as a priority-ordered set of frontier nodes and repeatedly selects the node with the minimum evaluation value under an ordering rule given by an evaluation function , where denotes the set of search nodes.

Applications

There are several search algorithms which are instantiations of best-first search:

• A*
• Levin Tree Search
• Policy Guided Heuristic Search

Implementation

// Concept for environment state
template <typename T>
concept IsSearchEnv = std::equality_comparable<T> && requires (T t, const T ct) {
    // apply action and return step cost
    { t.apply_action(std::declval<int>()) } -> std::same_as<double>;  
    { ct.is_solution() } -> std::same_as<bool>;
    { ct.is_terminal() } -> std::same_as<bool>;
    { std::hash<T>{}(ct) } -> std::convertible_to<std::size_t>;
    { auto(T::num_actions) } -> std::same_as<int>;
};
 
// Concept for search node
template <typename T, IsSearchEnv Env>
concept IsSearchNode = requires (T t, const T ct) {
    { ct.generate_child(std::declval<int>()) } -> std::same_as<T>;
    { auto(t.parent) } -> std::same_as<T*>;
    { auto(t.state) } -> std::same_as<Env>;
    { auto(t.cost) } -> std::same_as<double>;
    { auto(t.generated_step) } -> std::same_as<int>;
    { auto(t.expanded_step) } -> std::same_as<int>;
};
 
// Node hashing
template <IsSearchEnv Env, typename Node>
    requires IsSearchNode<Node, Env>
struct NodeHasher {
    auto operator()(const Node *node) const -> std::size_t{
        assert(node);
        using State = std::remove_cvref_t<decltype(node->state)>;
        return std::hash<State>{}(node->state);
    }
};
 
// Node equality
template <IsSearchEnv Env, typename Node>
    requires IsSearchNode<Node, Env>
struct NodeEquality {
    auto operator()(const Node *lhs, const Node *rhs) const -> bool {
        assert(lhs && rhs);
        return lhs->state == rhs->state;
    }
};
 
template <IsSearchEnv Env, typename Node>
    requires IsSearchNode<Node, Env>
auto best_first_search(
    Node root, 
    std::function<double(const Node&)> eval_func
) -> bool 
{
    // Search data structures
    std::vector<std::unique_ptr<Node>> nodes;
    // Comparison by node cost, tie break on generation number
    auto node_compare = [&](const Node *lhs, const Node *rhs) {
        assert (lhs && rhs);
        if (lhs.cost != rhs.cost) {
            return lhs.cost > rhs.cost;
        }
        return lhs.generated_step > rhs.generated_step;
    };
    std::priority_queue<
        Node*, 
        std::vector<Node*>, 
        decltype(node_compare)
    > open(node_compare);
    std::unordered_multiset<
        Node *, 
        NodeHasher<Env, Node>, 
        NodeEquality<Env, Node>
    > closed;
    
    root.generated_step = 0;
    root.expanded_step = 0;
    int num_expanded = 0;
    int num_generated = 0;
    
    nodes.emplace_back(std::make_unique<Node>(std::move(root)));
    open.push(nodes.back().get());
    while (!open.empty()) {
        // Expand
        auto current = open.top();
        open.pop();
        closed.insert(current);
        current->expanded_step = ++num_expanded;
        
        // Check for solution and terminal states
        if (current->state.is_solution()) {
            return true;
        }
        if (current->state.is_terminal()) {
            continue;
        }
        
        // Generate children
        for (auto a : std::views::indices(Env::num_actions)) {
            auto child = std::make_unique<Node>(current->generate_child(a));
            if (closed.contains(child.get())) {
                continue;
            }
            child->generated_step = ++num_generated;
            child->cost = eval_func(*(child.get()));
            nodes.emplace_back(std::move(child));
            open.push(nodes.back().get());
        }
    }
    return false;
}