Simplified Memory-Bounded A* (SMA*)

Simplified Memory-Bounded A* (SMA*) is an extension of the A* search algorithm designed to operate within a strictly constrained memory budget. While standard A* retains all generated nodes in memory leading to exponential space complexity O(b^d), SMA* proceeds like A* until memory is exhausted, at which point it prunes the worst leaf node (highest f-cost) while backing up its value to its parent. It bridges the gap between heuristic-driven optimality and physical hardware constraints, making it indispensable for memory-limited embedded environments and massive state-space planning.

struct Node {
    State state;
    double g;
    double h;
    double f;
    Node* parent;
    std::vector<Node*> children;
    bool is_leaf;
};

#include <queue>
#include <vector>
#include <algorithm>
#include <limits>

struct CompareNode {
    bool operator()(const Node* a, const Node* b) {
        return a->f > b->f;
    }
};

class SMASearch {
    size_t memory_limit;
    std::priority_queue<Node*, std::vector<Node*>, CompareNode> open_list;

public:
    SMASearch(size_t limit) : memory_limit(limit) {}

    void prune_worst() {
        // Find node with highest f-cost in open list to drop
        // In strict SMA*, maintain a secondary structure or iterate to drop worst leaf
    }
};

void run_unit_test() {
    SMASearch solver(100); // Max 100 nodes
    // Assert optimal path is found within bounds
}

if (open_list.size() >= memory_limit && all_nodes_same_f_cost()) {
    throw std::runtime_error("Memory limit too constrained: Search space thrashing detected.");
}

Algorithmic Mechanics & Memory Management

SMA* maintains the completeness and optimality guarantees of A* as long as the memory limit is large enough to store the shallowest optimal path. Each node tracks its evaluation function f(n). When generating successors, if the node limit is exceeded, SMA* selects the worst leaf node (the node with the maximum f-value) for deletion. Crucially, before discarding the node, it updates its parent's f-value with the minimum f-value of its discarded children. This ensures that the parent node 'remembers' the sub-tree it pruned, allowing the search to re-explore that path later if all alternative paths prove to have higher costs.

Comparison with Iterative Deepening A* (IDA*)

While IDA* also operates within linear space O(d), it suffers from severe performance penalties in graphs with many transpositions (reconverging paths) due to state regeneration. SMA* utilizes available memory effectively by caching as many states as possible, falling back to pruning only when limits are breached. However, SMA* incurs higher pointer-overhead and garbage collection or manual memory management complexity compared to IDA*.