IDA* algorithm for memory-efficient shortest path search. More...

#include <IDA_Star.H>

Collaboration diagram for Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >:

Classes
struct	SearchResult

Public Types
using	Distance_Type = typename Distance::Distance_Type

using	Node = typename GT::Node

using	Arc = typename GT::Arc

Public Member Functions
	IDA_Star (Distance dist=Distance(), Heuristic h=Heuristic(), SA _sa=SA())
	Constructor.

Distance_Type	find_path (const GT &g, Node start, Node end, Path< GT > &path)
	Finds the shortest path from start to end using IDA*.

Distance_Type	operator() (const GT &g, Node start, Node end, Path< GT > &path)
	Finds shortest path (operator interface).

Private Member Functions
SearchResult	search (const GT &g, Node curr, Node end, Distance_Type g_cost, Distance_Type threshold, Path< GT > &path)
	Recursive DFS bounded by threshold.

Private Attributes
SA	sa

Distance	distance

Heuristic	heuristic

Static Private Attributes
static constexpr Distance_Type	Inf

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >

IDA* algorithm for memory-efficient shortest path search.

This class implements the Iterative Deepening A* (IDA*) algorithm, which combines the optimality of A* with the linear memory usage of iterative deepening depth-first search.

The algorithm performs repeated depth-limited DFS searches with increasing f-cost thresholds. In each iteration, nodes with f(n) = g(n) + h(n) exceeding the threshold are pruned.

The class receives the following template parameters:

GT: graph type.
Distance: weight accessor (default: Dft_Dist<GT>).
Heuristic: h(n) estimator. Must be admissible for optimality. Signature: Distance_Type operator()(Node* from, Node* to).
Itor: arc iterator template (defaults to Node_Arc_Iterator).
SA: arc filter for internal iterators.

Warning: The heuristic must be admissible (never overestimate) for the algorithm to find optimal paths.; All edge weights must be non-negative.

Note: IDA* may revisit nodes across iterations. For graphs with many distinct f-values, A* may be more efficient.

See also: AStar_Min_Path For heap-based A*.; Dijkstra_Min_Paths For Dijkstra without heuristic.

Definition at line 174 of file IDA_Star.H.

Member Typedef Documentation

◆ Arc

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Arc = typename GT::Arc

Definition at line 179 of file IDA_Star.H.

◆ Distance_Type

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Distance_Type = typename Distance::Distance_Type

Definition at line 177 of file IDA_Star.H.

◆ Node

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Node = typename GT::Node

Definition at line 178 of file IDA_Star.H.

Constructor & Destructor Documentation

◆ IDA_Star()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::IDA_Star	(	Distance	dist = `Distance()`,
		Heuristic	h = `Heuristic()`,
		SA	_sa = `SA()`
	)

inline

Constructor.

Parameters

[in]	dist	Distance functor for arc weights.
[in]	h	Heuristic functor.
[in]	_sa	Arc filter for iterators.

Definition at line 277 of file IDA_Star.H.

Member Function Documentation

◆ find_path()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::find_path	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Finds the shortest path from start to end using IDA*.

Performs iterative deepening with f-cost thresholds. Each iteration runs a depth-first search bounded by the threshold. The threshold starts at h(start) and increases to the minimum f-value that exceeded the previous threshold.

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path (empty if no path exists).

Returns: The total cost, or max value if no path exists.

Exceptions

domain_error	If start or end is nullptr, or g is empty.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(b^d) where b is branching factor and d is solution depth.; Space complexity: O(d) (linear in solution depth).

Definition at line 304 of file IDA_Star.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Path< GT >::empty(), Aleph::Find_Path, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::heuristic, Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Inf, GraphCommon< GT, Node, Arc >::reset_bit_nodes(), Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search(), and Aleph::Path< GT >::set_graph().

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::operator()().

◆ operator()()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::operator()	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Finds shortest path (operator interface).

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path.

Returns: The total cost, or max value if no path exists.

Definition at line 359 of file IDA_Star.H.

References Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::find_path().

◆ search()

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

SearchResult Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search	(	const GT &	g,
		Node *	curr,
		Node *	end,
		Distance_Type	g_cost,
		Distance_Type	threshold,
		Path< GT > &	path
	)

inlineprivate

Recursive DFS bounded by threshold.

Returns: SearchResult with found=true if goal reached, or found=false and value=minimum f-value that exceeded threshold.

Definition at line 203 of file IDA_Star.H.

References ah_domain_error_if, ah_overflow_error_if, Aleph::Path< GT >::append(), Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), Aleph::Find_Path, GraphCommon< GT, Node, Arc >::get_connected_node(), h, Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::heuristic, Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Inf, IS_NODE_VISITED, NODE_BITS, Aleph::Path< GT >::remove_last_node(), Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::sa, Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search(), and w.

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::find_path(), and Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search().

Member Data Documentation

◆ distance

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::distance

private

Definition at line 186 of file IDA_Star.H.

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search().

◆ heuristic

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Heuristic Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::heuristic

private

Definition at line 187 of file IDA_Star.H.

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::find_path(), and Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search().

◆ Inf

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr Distance_Type Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::Inf

staticconstexprprivate

Initial value:

=

std::numeric_limits<Distance_Type>::max()

Definition at line 189 of file IDA_Star.H.

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::find_path(), and Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search().

◆ sa

template<class GT , class Distance = Dft_Dist<GT>, class Heuristic = Zero_Heuristic<GT, Distance>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

SA Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::sa

private

Definition at line 185 of file IDA_Star.H.

Referenced by Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::search().

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

IDA_Star.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Distance_Type

◆ Node

Constructor & Destructor Documentation

◆ IDA_Star()

Member Function Documentation

◆ find_path()

◆ operator()()

◆ search()

Member Data Documentation

◆ distance

◆ heuristic

◆ Inf

◆ sa