BeamSearch Class Reference

#include <search.h>

Inheritance diagram for BeamSearch:

Collaboration diagram for BeamSearch:

Public Member Functions
	BeamSearch (Problem *problem, int beam_width)
std::shared_ptr< Node >	search () override
	~BeamSearch () override
Public Member Functions inherited from Search
	Search (Problem *problem)
virtual	~Search ()

Public Attributes
int	beam_width
Public Attributes inherited from Search
Problem *	problem

Detailed Description

Definition at line 89 of file search.h.

Constructor & Destructor Documentation

BeamSearch()

BeamSearch::BeamSearch ( Problem *  problem, int  beam_width  )

inline

Definition at line 91 of file search.h.

: Search(problem), beam_width(beam_width) {}

~BeamSearch()

BeamSearch::~BeamSearch ( )

override

Definition at line 132 of file search.cpp.

{ }

Member Function Documentation

search()

std::shared_ptr< Node > BeamSearch::search ( )

overridevirtual

Implements Search.

Definition at line 134 of file search.cpp.

                                       {
    // Priority queue to maintain the beam
    using Beam = std::vector<std::shared_ptr<Node>>;
    Beam beam;
 
    // Initialize the root node
    auto initial_state = problem->initial_state();
    auto root = std::make_shared<Node>(
        nullptr,
        std::shared_ptr<State>(initial_state),
        nullptr,
        0,
        problem->heuristic(initial_state)
    );
 
    beam.push_back(root);
 
    while (!beam.empty()) {
        // Sort beam nodes based on their f(n) = path_cost + heuristic
        std::sort(beam.begin(), beam.end(), [](const std::shared_ptr<Node>& a, const std::shared_ptr<Node>& b) {
            return (a->path_cost + a->heuristic) < (b->path_cost + b->heuristic);
        });
 
        // Keep only the top k nodes (beam width)
        if (beam.size() > beam_width) {
            beam.resize(beam_width);
        }
 
        Beam next_beam;
 
        // Expand each node in the current beam
        for (const auto& node : beam) {
            if (problem->goal_test(node->state.get())) {
                return node; // Goal found
            }
 
            // Generate successors
            for (const auto& action : problem->actions(node->state)) {
                auto child = std::make_shared<Node>(
                    node,
                    action->effect,
                    action,
                    node->path_cost + action->cost,
                    problem->heuristic(action->effect.get())
                );
                next_beam.push_back(child);
            }
        }
 
        beam = std::move(next_beam);
    }
 
    return nullptr;
}

References Problem::actions(), beam_width, Problem::goal_test(), Problem::heuristic(), Problem::initial_state(), and Search::problem.

Member Data Documentation

beam_width

int BeamSearch::beam_width

Definition at line 99 of file search.h.

Referenced by search().

---

The documentation for this class was generated from the following files:

• include/search.h
• src/search.cpp