AStarSearch Class Reference

#include <search.h>

Inheritance diagram for AStarSearch:

Collaboration diagram for AStarSearch:

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

Additional Inherited Members
Public Attributes inherited from Search
Problem *	problem

Detailed Description

Definition at line 78 of file search.h.

Constructor & Destructor Documentation

AStarSearch()

AStarSearch::AStarSearch ( Problem *  problem )

inline

Definition at line 80 of file search.h.

: Search(problem) {}

~AStarSearch()

AStarSearch::~AStarSearch

(

)

Definition at line 80 of file search.cpp.

{ }

Member Function Documentation

search()

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

overridevirtual

Implements Search.

Definition at line 82 of file search.cpp.

                                        {
    std::priority_queue<std::shared_ptr<Node>, std::vector<std::shared_ptr<Node>>, NodeComparator> frontier;
    // Initialize the root node with the problem's initial state
    std::unordered_set<std::shared_ptr<State>> explored; // Set of explored states
    auto initial_state = problem->initial_state();
    auto root = std::make_shared<Node>(
        nullptr,                    // Parent node
        std::shared_ptr<State>(initial_state), // Initial state (shared_ptr)
        nullptr,                    // No action
        0,                          // Path cost
        problem->heuristic(initial_state) // Heuristic value
    );
    frontier.push(root);
 
    while (!frontier.empty()) {
        auto node = frontier.top();
        frontier.pop();
 
        // Check if the goal state is reached
        State *state = node->state.get();
        if (problem->goal_test(state)) {
            return node;
        }
 
        // Skip the node if it has already been explored
        if (explored.find(node->state) != explored.end()) {
            continue;
        }
        explored.insert(node->state);
 
        // Expand the node by generating its child nodes
        for (const auto &action : problem->actions(node->state)) {
            auto child = std::make_shared<Node>(
                std::shared_ptr<Node>(node), // Parent node
                action->effect,
                action,                    // Pointer to the action
                node->path_cost + action->cost, // Path cost
                problem->heuristic(action->effect.get()) // Heuristic value
            );
            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