State_Search_IDA_Star.H File Reference

IDA* (Iterative Deepening A*) over implicit state spaces. More...

#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <state_search_common.H>
#include <Backtracking.H>

Include dependency graph for State_Search_IDA_Star.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::IDAStarIteration< Distance >
	Result of one threshold pass of IDA*. More...
struct	Aleph::IDAStarResult< Solution, Distance >
	Aggregated result of a complete IDA* run. More...
struct	Aleph::ida_star_detail::DFSResult< Distance >
	Outcome of one recursive DFS step inside IDA*. More...
class	Aleph::IDA_Star_State_Search< Domain >
	IDA* engine for implicit state spaces with an admissible heuristic. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::ida_star_detail

Concepts
concept	Aleph::IDAStarDomain
	Minimal contract for IDA* domains.

Functions
template<typename Distance >
constexpr Distance	Aleph::ida_star_detail::distance_unreachable () noexcept
	Sentinel value representing an unreachable or pruned f-cost.
template<IDAStarDomain Domain, typename Solution , typename OnSolution > requires SearchSolutionVisitor<OnSolution, Solution>
DFSResult< typename Domain::Distance >	Aleph::ida_star_detail::dfs (Domain &domain, typename Domain::State &state, SearchPath< typename Domain::Move > &path, const typename Domain::Distance g, const typename Domain::Distance threshold, const size_t depth, IDAStarResult< Solution, typename Domain::Distance > &result, OnSolution &on_solution)
	Core recursive DFS used by IDA* for a single threshold pass.
template<IDAStarDomain Domain>
auto	Aleph::ida_star_search (Domain domain, typename Domain::State initial_state, ExplorationPolicy policy={}, SearchLimits limits={})
	Convenience wrapper for a one-shot IDA* search.
template<IDAStarDomain Domain, typename OnSolution > requires SearchSolutionVisitor<OnSolution, SearchSolution<typename Domain::State, typename Domain::Move>>
auto	Aleph::ida_star_search (Domain domain, typename Domain::State initial_state, OnSolution &on_solution, ExplorationPolicy policy={}, SearchLimits limits={})
	Convenience wrapper for IDA* with a solution callback.

Detailed Description

IDA* (Iterative Deepening A*) over implicit state spaces.

IDA* combines the memory efficiency of DFS with the optimality guarantee of A* for admissible heuristics. Each iteration performs a depth-limited DFS that prunes branches whose estimated total cost f = g + h exceeds the current threshold. The threshold is set to the minimum f-value that exceeded the limit in the previous pass. The process repeats until a goal is found or the space is exhausted.

The domain contract is given by Aleph::IDAStarDomain, which extends Aleph::BacktrackingDomain with Aleph::HeuristicEvaluator and Aleph::ActionCostProvider. Admissibility requires heuristic(state) <= true cost to goal for all states.

Author

Leandro Rabindranath León

Definition in file State_Search_IDA_Star.H.