IDA* engine for implicit state spaces with an admissible heuristic. More...

#include <State_Search_IDA_Star.H>

Collaboration diagram for Aleph::IDA_Star_State_Search< Domain >:

Public Types
using	Domain_Type = Domain
	Type of the problem domain.

using	State = typename Domain::State
	Concrete search state type.

using	Move = typename Domain::Move
	Move type.

using	Distance = typename Domain::Distance
	Numeric distance/cost type.

using	Solution = SearchSolution< State, Move >
	Solution type containing state and path.

using	Result = IDAStarResult< Solution, Distance >
	Aggregated result type for IDA* search.

Public Member Functions
	IDA_Star_State_Search (Domain domain, ExplorationPolicy policy={}, const SearchLimits &limits={})
	Construct an engine bound to one domain adapter.

const Domain &	domain () const noexcept
	Read-only access to the bound domain adapter.

Domain &	domain () noexcept
	Mutable access to the bound domain adapter.

const ExplorationPolicy &	policy () const noexcept
	Current exploration policy.

const SearchLimits &	limits () const noexcept
	Current hard limits.

void	set_policy (const ExplorationPolicy &policy) noexcept
	Replace the exploration policy for future runs.

void	set_limits (const SearchLimits &limits) noexcept
	Replace the hard limits for future runs.

Result	search (State initial_state)
	Run IDA* from `initial_state`.

template<typename OnSolution > requires SearchSolutionVisitor<OnSolution, Solution>
Result	search (State initial_state, OnSolution &on_solution)
	Run IDA* and invoke `on_solution` when the goal is reached.

Static Public Attributes
static constexpr bool	supports_best_first = false
	Compile-time marker: IDA_Star_State_Search only supports Depth_First strategy.

Private Attributes
Domain	domain_

ExplorationPolicy	policy_

SearchLimits	limits_

Detailed Description

template<IDAStarDomain Domain>
class Aleph::IDA_Star_State_Search< Domain >

IDA* engine for implicit state spaces with an admissible heuristic.

The engine performs iterative threshold-bounded DFS. Each pass prunes branches whose estimated total cost f = g + h exceeds the current threshold. The threshold advances to the minimum cost that exceeded it in the previous pass.

Optimality

With an admissible heuristic, IDA* guarantees an optimal solution. The path returned in result.best_solution.get().path reaches the goal in exactly result.total_cost cost.

Memory

Only the current path from root to the node under expansion is stored (one SearchPath of depth at most max_depth). No open/closed lists.

Template Parameters

Domain problem adapter satisfying Aleph::IDAStarDomain.

Definition at line 285 of file State_Search_IDA_Star.H.

Member Typedef Documentation

◆ Distance

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::Distance = typename Domain::Distance

Numeric distance/cost type.

Definition at line 295 of file State_Search_IDA_Star.H.

◆ Domain_Type

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::Domain_Type = Domain

Type of the problem domain.

Definition at line 289 of file State_Search_IDA_Star.H.

◆ Move

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::Move = typename Domain::Move

Move type.

Definition at line 293 of file State_Search_IDA_Star.H.

◆ Result

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::Result = IDAStarResult<Solution, Distance>

Aggregated result type for IDA* search.

Definition at line 299 of file State_Search_IDA_Star.H.

◆ Solution

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::Solution = SearchSolution<State, Move>

Solution type containing state and path.

Definition at line 297 of file State_Search_IDA_Star.H.

◆ State

template<IDAStarDomain Domain>

using Aleph::IDA_Star_State_Search< Domain >::State = typename Domain::State

Concrete search state type.

Definition at line 291 of file State_Search_IDA_Star.H.

Constructor & Destructor Documentation

◆ IDA_Star_State_Search()

template<IDAStarDomain Domain>

Aleph::IDA_Star_State_Search< Domain >::IDA_Star_State_Search	(	Domain	domain,
		ExplorationPolicy	policy = `{}`,
		const SearchLimits &	limits = `{}`
	)

inlineexplicit

Construct an engine bound to one domain adapter.

Parameters

domain	Problem adapter.
policy	Exploration settings.
limits	Resource constraints.

Definition at line 315 of file State_Search_IDA_Star.H.

Member Function Documentation

◆ domain() [1/2]

template<IDAStarDomain Domain>

const Domain & Aleph::IDA_Star_State_Search< Domain >::domain ( ) const

inlinenoexcept

Read-only access to the bound domain adapter.

Definition at line 323 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::domain_.

◆ domain() [2/2]

template<IDAStarDomain Domain>

Domain & Aleph::IDA_Star_State_Search< Domain >::domain ( )

inlinenoexcept

Mutable access to the bound domain adapter.

Definition at line 329 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::domain_.

◆ limits()

template<IDAStarDomain Domain>

const SearchLimits & Aleph::IDA_Star_State_Search< Domain >::limits ( ) const

inlinenoexcept

Current hard limits.

Definition at line 341 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::limits_.

Referenced by Aleph::IDA_Star_State_Search< Domain >::set_limits().

◆ policy()

template<IDAStarDomain Domain>

const ExplorationPolicy & Aleph::IDA_Star_State_Search< Domain >::policy ( ) const

inlinenoexcept

Current exploration policy.

Definition at line 335 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::policy_.

Referenced by Aleph::IDA_Star_State_Search< Domain >::set_policy().

◆ search() [1/2]

template<IDAStarDomain Domain>

Result Aleph::IDA_Star_State_Search< Domain >::search ( State initial_state )

inline

Run IDA* from initial_state.

Iterates threshold passes until a goal is found, the space is exhausted or a hard limit is reached.

Parameters

[in] initial_state Root state to expand. Mutated during search and restored to its original value before this function returns.

Returns: IDAStarResult with solution, stats and per-iteration data.

Exceptions

std::invalid_argument if the policy requests Best_First strategy (IDA* is DFS-only) or if max_solutions is zero.

Note: max_depth in SearchLimits limits the depth of each pass.

Definition at line 371 of file State_Search_IDA_Star.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::IDA_Star_State_Search< Domain >::search().

Referenced by Aleph::IDA_Star_State_Search< Domain >::search(), TEST(), and TEST().

◆ search() [2/2]

template<IDAStarDomain Domain>

template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>

Result Aleph::IDA_Star_State_Search< Domain >::search	(	State	initial_state,
		OnSolution &	on_solution
	)

inline

Run IDA* and invoke on_solution when the goal is reached.

The callback receives a solution snapshot and returns true to allow the search to continue according to the exploration policy and limits, or false to stop immediately. IDA* is typically used with stop-at-first-solution. This implementation stops at the first goal reached within each threshold pass; with non-negative step costs and an admissible heuristic the first solution encountered is already optimal, so raising the threshold in later passes cannot produce a cheaper solution, only potentially explore alternative states subject to the configured limits.

Definition at line 391 of file State_Search_IDA_Star.H.

References ah_invalid_argument_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::ExplorationPolicy::Depth_First, Aleph::ida_star_detail::dfs(), Aleph::IDA_Star_State_Search< Domain >::domain_, Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::IDAStarIteration< Distance >::found_solution, Aleph::LimitReached, Aleph::SearchResult< Solution, Compare >::limits, Aleph::IDA_Star_State_Search< Domain >::limits_, Aleph::SearchLimits::max_solutions, Aleph::IDAStarIteration< Distance >::next_threshold, Aleph::NotStarted, Aleph::SearchResult< Solution, Compare >::policy, Aleph::IDA_Star_State_Search< Domain >::policy_, Aleph::reserve_search_path(), Aleph::search_elapsed_ms(), Aleph::SearchResult< Solution, Compare >::stats, Aleph::SearchResult< Solution, Compare >::status, Aleph::StoppedOnSolution, Aleph::ExplorationPolicy::strategy, Aleph::IDAStarIteration< Distance >::threshold, Aleph::SearchStats::visited_states, and Aleph::IDAStarIteration< Distance >::visited_states.

◆ set_limits()

template<IDAStarDomain Domain>

void Aleph::IDA_Star_State_Search< Domain >::set_limits ( const SearchLimits & limits )

inlinenoexcept

Replace the hard limits for future runs.

Definition at line 353 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::limits(), and Aleph::IDA_Star_State_Search< Domain >::limits_.

◆ set_policy()

template<IDAStarDomain Domain>

void Aleph::IDA_Star_State_Search< Domain >::set_policy ( const ExplorationPolicy & policy )

inlinenoexcept

Replace the exploration policy for future runs.

Definition at line 347 of file State_Search_IDA_Star.H.

References Aleph::IDA_Star_State_Search< Domain >::policy(), and Aleph::IDA_Star_State_Search< Domain >::policy_.

Member Data Documentation

◆ domain_

template<IDAStarDomain Domain>

Domain Aleph::IDA_Star_State_Search< Domain >::domain_

private

Definition at line 455 of file State_Search_IDA_Star.H.

Referenced by Aleph::IDA_Star_State_Search< Domain >::domain(), Aleph::IDA_Star_State_Search< Domain >::domain(), and Aleph::IDA_Star_State_Search< Domain >::search().

◆ limits_

template<IDAStarDomain Domain>

SearchLimits Aleph::IDA_Star_State_Search< Domain >::limits_

private

Definition at line 457 of file State_Search_IDA_Star.H.

Referenced by Aleph::IDA_Star_State_Search< Domain >::limits(), Aleph::IDA_Star_State_Search< Domain >::search(), and Aleph::IDA_Star_State_Search< Domain >::set_limits().

◆ policy_

template<IDAStarDomain Domain>

ExplorationPolicy Aleph::IDA_Star_State_Search< Domain >::policy_

private

Definition at line 456 of file State_Search_IDA_Star.H.

Referenced by Aleph::IDA_Star_State_Search< Domain >::policy(), Aleph::IDA_Star_State_Search< Domain >::search(), and Aleph::IDA_Star_State_Search< Domain >::set_policy().

◆ supports_best_first

template<IDAStarDomain Domain>

constexpr bool Aleph::IDA_Star_State_Search< Domain >::supports_best_first = false

staticconstexpr

Compile-time marker: IDA_Star_State_Search only supports Depth_First strategy.

Passing ExplorationPolicy::Strategy::Best_First to this engine raises std::invalid_argument at runtime. Check this constant before constructing a policy to detect the mismatch at compile time.

Definition at line 308 of file State_Search_IDA_Star.H.

The documentation for this class was generated from the following file:

State_Search_IDA_Star.H

Public Types

Public Member Functions

Static Public Attributes

Private Attributes

Detailed Description

Optimality

Memory

Member Typedef Documentation

◆ Distance

◆ Domain_Type

◆ Move

◆ Result

◆ Solution

◆ State

Constructor & Destructor Documentation

◆ IDA_Star_State_Search()

Member Function Documentation

◆ domain() [1/2]

◆ domain() [2/2]

◆ limits()

◆ policy()

◆ search() [1/2]

◆ search() [2/2]

◆ set_limits()

◆ set_policy()

Member Data Documentation

◆ domain_

◆ limits_

◆ policy_

◆ supports_best_first