astar/OpenList.h

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

Classes

Class	Description
OpenEntry	An entry of the OPEN list: the node and the g it had when pushed

Enumerations

enum class PBeFS_di_unipi_it::OpenKind

the kind of OPEN list a search uses

Values:

enumerator automatic: buckets for integer costs, heap otherwise

enumerator heap: HeapOpenList.

enumerator buckets: BucketOpenList (integer costs only).

Description of the header

Header file for the priority queues of the OPEN list, taken from the set of data structures chosen [see Structures.h]: the class templates HeapOpenList, a heap for any cost type, and BucketOpenList, a two-level bucket queue for integer costs, and their entries.

Both queues order the entries by increasing f and break the ties in favour of the larger g, which reaches the goal earlier inside the last f layer [see Burns et al., SoCS 2012], LIFO among the entries with the same f and g. Neither supports decrease-key: a node reached through a cheaper path is pushed again, and an entry is stale when the node is closed or its g no longer matches the g of the entry. The caller discards the stale entries as they surface. A queue over NodeT has push( node ), which pushes node with its current f and g, push( node , g ), which pushes it with the given g (and \( f = g + h \)) without reading node->g, top(), the OpenEntry with the least f and the largest g among those, top_f(), its f, pop(), which removes and returns it, empty() and size(), the number of entries, the stale ones included.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright