- Generated by
1.15.0
|
PBeFS
Parallel Best-First Search
|
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. More...
#include <algorithm>#include <cstddef>#include <type_traits>#include <vector>#include "PBeFS/astar/Structures.h"Go to the source code of this file.
Classes | |
| struct | OpenEntry< NodeT > |
| an entry of the OPEN list: the node and the g it had when pushed More... | |
Namespaces | |
| namespace | PBeFS_di_unipi_it |
| namespace for the Parallel Best-First Search library | |
Enumerations | |
| enum class | OpenKind { automatic , heap , buckets } |
| the kind of OPEN list a search uses More... | |
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.
1.15.0