BreadthFirstSearch Class Reference

Breadth-first search algorithm implementation. More...

#include <search.h>

Inheritance diagram for BreadthFirstSearch:

Collaboration diagram for BreadthFirstSearch:

Public Member Functions
	BreadthFirstSearch (Problem *problem)
std::shared_ptr< Node >	search () override
	Breadth-first search algorithm implementation. The breadth-first search algorithm explores a graph by visiting all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
	~BreadthFirstSearch ()
Public Member Functions inherited from Search
	Search (Problem *problem)
virtual	~Search ()

Additional Inherited Members
Public Attributes inherited from Search
Problem *	problem

Detailed Description

Breadth-first search algorithm implementation.

This class implements the breadth-first search algorithm, which explores a graph by visiting all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Definition at line 67 of file search.h.

Constructor & Destructor Documentation

BreadthFirstSearch()

BreadthFirstSearch::BreadthFirstSearch ( Problem *  problem )

inline

Definition at line 69 of file search.h.

: Search(problem) {}

~BreadthFirstSearch()

BreadthFirstSearch::~BreadthFirstSearch

(

)

Definition at line 26 of file search.cpp.

{ }

Member Function Documentation

search()

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

overridevirtual

Breadth-first search algorithm implementation. The breadth-first search algorithm explores a graph by visiting all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Implements Search.

Definition at line 45 of file search.cpp.

                                               {
    std::queue<std::shared_ptr<Node>> frontier;
    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)
    );
    frontier.push(root);
    while (!frontier.empty()) {
        auto node = frontier.front();
        frontier.pop();
 
        State *state = node->state.get();
        if (problem->goal_test(state)) {
            return node;
        }
        #pragma omp parallel for shared(frontier) schedule(dynamic) if (frontier.size() > 1000)
        for (const auto &action : problem->actions(node->state)) {
            auto child = std::make_shared<Node>(
                std::shared_ptr<Node>(node),
                action->effect,
                action,
                node->path_cost + action->cost,
                problem->heuristic(action->effect.get())
            );
            frontier.push(child);
        }
    }
    // Return nullptr if no solution is found
    return nullptr;
}

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

---

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

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