astar/IDAStar.h

Header of the layer astar, in the group Searches; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
IDAStar	The iterative-deepening A* search of a Domain

Functions

template<Domain D>
Solution<state_t<D>, cost_t<D>> PBeFS_di_unipi_it::idastar(

const D &domain,

const SearchOptions &options = {}

)

searches a Domain with IDA*

Description of the header

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