Memory-bounded heuristic search

Memory-bounded heuristic search is a type of informed search algorithm that limits the amount of memory used during the search process. It is designed to efficiently find solutions in large state spaces while ensuring that the search does not exceed the available memory resources.

One common memory-bounded heuristic search algorithm is iterative-deepening A* (IDA*), which is a variant of A* search that limits the memory used by controlling the depth of the search tree.

In IDA*, the search begins with a cutoff value equal to the estimated cost of the optimal solution, as given by the heuristic function. The search then proceeds iteratively, increasing the cutoff value until a goal state is found. At each iteration, the search performs a depth-first search (DFS) starting from the initial state, but only expands nodes whose f values (f(n) = g(n) + h(n)) are less than the current cutoff value.

If a goal state is not found at the current iteration, the cutoff value is increased to the smallest f value that was greater than the previous cutoff value during the search, and the search is restarted with the new cutoff value. This process is repeated until a goal state is found.

IDA* has the advantage of using less memory than A* search, but it may expand more nodes and take longer to find a solution. It is also less efficient than A* search in terms of the number of nodes expanded, as it may re-expand nodes multiple times at different cutoff levels.

Other memory-bounded heuristic search algorithms include memory-bounded heuristic search with iterative deepening (IDS), depth-first iterative deepening (DFID), and depth-first branch-and-bound (DFBB). These algorithms have different memory and time trade-offs, and the choice of algorithm depends on the specific problem and available resources