State-Space Search

Step 1

cmake_minimum_required(VERSION 3.20)
project(StateSpaceSearchEngine CXX)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wextra -Werror -O3 -fsanitize=address,undefined")

add_executable(search_engine main.cpp)

Step 2

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <memory>
#include <concepts>
#include <algorithm>

template<typename T>
concept StateConcept = requires(T a, T b) {
    { a.hash() } -> std::convertible_to<size_t>;
    { a == b } -> std::convertible_to<bool>;
    { a.get_cost() } -> std::convertible_to<double>;
    { a.get_heuristic() } -> std::convertible_to<double>;
};

template<StateConcept State>
struct SearchNode {
    State state;
    double g_cost;
    double f_cost;
    std::shared_ptr<SearchNode> parent;

    bool operator>(const SearchNode& other) const {
        return f_cost > other.f_cost;
    }
};

template<StateConcept State>
class AStarSearch {
public:
    struct StateHash {
        size_t operator()(const std::shared_ptr<SearchNode<State>>& node) const {
            return node->state.hash();
        }
    };

    struct StateEqual {
        bool operator()(const std::shared_ptr<SearchNode<State>>& a, const std::shared_ptr<SearchNode<State>>& b) const {
            return a->state == b->state;
        }
    };

    std::vector<State> solve(State initial_state) {
        auto start_node = std::make_shared<SearchNode<State>>(
            initial_state, 0.0, initial_state.get_heuristic(), nullptr
        );

        std::priority_queue<std::shared_ptr<SearchNode<State>>, 
                            std::vector<std::shared_ptr<SearchNode<State>>>, 
                            bool(*)(const std::shared_ptr<SearchNode<State>>&, const std::shared_ptr<SearchNode<State>>&)> 
                            open_set([](const auto& a, const auto& b){ return a->f_cost > b->f_cost; });

        std::unordered_set<std::shared_ptr<SearchNode<State>>, StateHash, StateEqual> closed_set;

        open_set.push(start_node);

        while (!open_set.empty()) {
            auto current = open_set.top();
            open_set.pop();

            if (current->state.is_goal()) {
                return reconstruct_path(current);
            }

            if (closed_set.find(current) != closed_set.end()) {
                continue;
            }
            closed_set.insert(current);

            for (auto& neighbor_state : current->state.get_neighbors()) {
                double tentative_g = current->g_cost + neighbor_state.transition_cost();
                
                auto neighbor_node = std::make_shared<SearchNode<State>>(
                    neighbor_state, tentative_g, tentative_g + neighbor_state.get_heuristic(), current
                );

                open_set.push(neighbor_node);
            }
        }
        return {};
    }

private:
    std::vector<State> reconstruct_path(std::shared_ptr<SearchNode<State>> node) {
        std::vector<State> path;
        while (node != nullptr) {
            path.push_back(node->state);
            node = node->parent;
        }
        std::reverse(path.begin(), path.end());
        return path;
    }
};

Step 3

#include <cassert>

struct MockState {
    int value;
    size_t hash() const { return std::hash<int>{}(value); }
    bool operator==(const MockState& o) const { return value == o.value; }
    double get_cost() const { return 1.0; }
    double get_heuristic() const { return 0.0; }
    bool is_goal() const { return value == 5; }
    double transition_cost() const { return 1.0; }
    std::vector<MockState> get_neighbors() const { return {MockState{value + 1}};
 }
};

int main() {
    AStarSearch<MockState> solver;
    auto path = solver.solve(MockState{0});
    assert(!path.empty());
    assert(path.back().value == 5);
    std::cout << "State-space search verification passed successfully.n";
    return 0;
}

Step 4

// Example pattern for memory-bounded search thresholds
class BoundedAStarSearch {
    size_t max_node_allocations;
public:
    explicit BoundedAStarSearch(size_t limit) : max_node_allocations(limit) {}
    // Enforce strict memory limits during expansion loops to prevent OOM termination
};