IDAStar.h File Reference

Header file for the class template IDAStar, the iterative-deepening A* of Korf (1985), which finds an optimal path with a memory linear in its length: a depth-first search bounded by \( f = g + h \), repeated with the bound raised each time to the least \( f \) that exceeded it. More...

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>
#include "PBeFS/astar/Domain.h"
#include "PBeFS/astar/Node.h"
#include "PBeFS/core/SearchUtils.h"
#include "PBeFS/astar/Solution.h"

Go to the source code of this file.

Classes
class	IDAStar< D >
	the iterative-deepening A* search of a Domain More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Functions
template<Domain D>
Solution< state_t< D >, cost_t< D > >	idastar (const D &domain, const SearchOptions &options={})
	searches a Domain with IDA*

Detailed Description

Header file for the class template IDAStar, the iterative-deepening A* of Korf (1985), which finds an optimal path with a memory linear in its length: a depth-first search bounded by \( f = g + h \), repeated with the bound raised each time to the least \( f \) that exceeded it.

With the notation of the page "Best-first search and A*" of the documentation, and \( h \) admissible:

1  procedure IDA*(s₀)
2     β ← h(s₀)
3     loop
4        β' ← ∞
5        if DFS(s₀, 0, β) then return the path
6        if β' = ∞ then return unsolvable
7        β ← β'
 
1  function DFS(u, g, β)
2     if g + h(u) > β then β' ← min(β', g + h(u)); return false
3     if u is a goal then return true
4     for each successor v of u but the parent of u do
5        push v on the path
6        if DFS(v, g + c(u, v), β) then return true
7        pop v from the path
8     return false

The parent is skipped by its operator in an OperatorDomain [see Domain.h], and otherwise by comparing the successor with the state two places back on the path; no other duplicate is detected, so that the search fits the domains whose graph has few short cycles, such as the sliding-tile puzzles, where IDA* with a pattern database is the method of Korf and Felner (2002) for the 24-puzzle. The costs must be positive on every cycle, or an iteration may not end; and when no goal is reachable the search proves it only on an acyclic graph, since on one with cycles the bound grows without end, unless the node limit stops it.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli