astar
The graph searches of A*, sequential and parallel, with their domains, work distributions and data structures.
Header |
Description |
|---|---|
Graph searches of PBeFS save the one that needs MPI, HDAStarMPI.h. |
Header |
Description |
|---|---|
Sequential A* over a Domain, with the OPEN list Open |
|
The iterative-deepening A* search of a Domain |
|
The A* search of a Domain with delayed duplicate detection on the disk |
|
Hash Distributed A* on a shared-memory machine. |
|
Simple Parallel A*: one OPEN and one CLOSED list shared by the workers. |
|
MultiQueue A*: one relaxed OPEN list and one CLOSED list shared by the workers. |
|
Safe Parallel Best-NBlock-First search. |
|
Parallel A* for Slow Expansions. |
|
A master-worker parallel A* on a farm with feedback |
|
Hash Distributed A* with one MPI process per worker. |
Header |
Description |
|---|---|
Work distribution functions of hash-based parallel A*: each one maps a state to its owner among p workers [see section 6 of Fukunaga et al., 2017, and Jinnai and Fukunaga, JAIR 2017]. |
Header |
Description |
|---|---|
Concepts a search problem has to satisfy in order to be searched by the algorithms of the library, and for the few type helpers built upon them. |
|
The sliding-tile puzzle on a board of at most 25 cells |
|
Pattern databases of the sliding-tile puzzles, i.e., the heuristics that store the exact distances of an abstraction of the puzzle. |
|
Pathfinding on a GridMap with 4 (Moves == 4) or 8 (Moves == 8) moves |
|
A weighted graph given explicitly, searched from a source to a target |
|
A Domain whose expansions cost a given amount of extra work |
|
The sliding-tile puzzle with the sequence score heuristic of Nilsson |
|
A trip on the road map of Romania |
|
The n-queens problem, with at most 32 queens |
|
The vacuum world on a row of at most 32 cells |
|
The missionaries and cannibals problem |
|
The water jugs problem, with up to 4 jugs of at most 65535 units |
|
The traveling salesperson problem on at most 32 cities |
Header |
Description |
|---|---|
A node of the search graph |
|
Class template NodeTable, the closed list of the searches: a map from the generated states to their canonical Node, taken from the set of data structures chosen [see Structures.h]. |
|
The closed list, on the PointerTable of ADS, on huge pages |
|
The closed list shared by the workers, a lock-free set of the nodes |
|
Class template ConcurrentClosed, the closed list that the workers of SPAStar and MQAStar share, taken from the set of data structures chosen [see Structures.h]. |
|
Priority queues of the OPEN list of the set of data structures of ADS [see Structures.h], HeapOpenList and BucketOpenList, on the DaryHeap and the BucketQueue of ADS; OpenList.h includes it in place of its own, with the same order of the entries but for the ties of f and g. |
|
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. |
|
Choice of the set of data structures of A*: the arena of the nodes (NodePool), the closed list (NodeTable), the OPEN lists (HeapOpenList and BucketOpenList) and the adjacency of the explicit graphs and of the grids. |
Header |
Description |
|---|---|
A path from the initial state to a goal, and its cost |
Header |
Description |
|---|---|
The arcs of a weighted graph, on the GraphBuilder and ArrayGraph of ADS |
|
The moves from a cell of a GridMap and their costs, on the GridGraph of ADS |
|
The arena of the nodes, on the Arena of ADS, on huge pages |
Documentation
Page |
Description |
|---|---|
The search problem, A* with its invariants and guarantees, and the cost of its operations on the data structures of the library. |
|
The overheads of a parallel best-first search, and what SPA*, HDA* with its distributions, SafePBNF, PA*SE and the farm guarantee and pay. |
|
The abstraction of a pattern, the admissibility and the consistency of the additive tables and of the reflection, and the encodings of the entries down to one bit. |