IDA_Star.H File Reference

IDA* (Iterative Deepening A*) shortest path algorithm. More...

#include <limits>
#include <cmath>
#include <type_traits>
#include <tpl_graph_utils.H>
#include <ah-errors.H>
#include <AStar.H>

Include dependency graph for 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::Chebyshev_Heuristic< GT, Distance >
	Chebyshev (L-infinity) distance heuristic for 8-connected grids. More...
class	Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >
	IDA* algorithm for memory-efficient shortest path search. More...
struct	Aleph::IDA_Star< GT, Distance, Heuristic, Itor, SA >::SearchResult

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

Detailed Description

IDA* (Iterative Deepening A*) shortest path algorithm.

Implements the IDA* algorithm, a memory-efficient variant of A* that uses iterative deepening with a cost threshold. Each iteration performs a depth-first search bounded by f(n) = g(n) + h(n), where g(n) is the cost from start and h(n) is the heuristic estimate.

How it works

1. Set initial threshold = h(start)
2. Perform DFS from start, pruning nodes where f(n) > threshold
3. If goal found, return the path
4. Otherwise, set threshold = minimum f(n) that exceeded the previous threshold, and repeat from step 2

Advantages over A*

• Linear memory: O(d) where d is the solution depth, vs O(b^d) for A*. This makes IDA* practical for very large search spaces.
• No priority queue overhead: Uses simple DFS recursion.

Disadvantages

• Redundant work: Nodes may be revisited across iterations.
• Not suitable for graphs with many distinct f-values: Each distinct f-value causes a new iteration.

Complexity

Aspect	Complexity
Time	O(b^d) (same as A* asymptotically)
Space	O(d) (linear in solution depth)

Usage Example

// Grid with (x,y) coordinates
struct Coord { int x, y; };
using G = List_Graph<Graph_Node<Coord>, Graph_Arc<int>>;
 
struct ManhattanH {
  using Distance_Type = int;
  int operator()(G::Node* from, G::Node* to) const {
    auto& f = from->get_info();
    auto& t = to->get_info();
    return std::abs(f.x - t.x) + std::abs(f.y - t.y);
  }
};
 
IDA_Star<G, Dft_Dist<G>, ManhattanH> ida;
Path<G> path(g);
int dist = ida(g, start, goal, path);

See also

AStar.H For heap-based A* (faster but more memory)

Dijkstra.H For shortest paths without heuristic

Author

Leandro Rabindranath Leon

Definition in file IDA_Star.H.