namespace for the Parallel Best-First Search library More...

Classes
class	AStar
	sequential A* over a Domain, with the OPEN list Open More...
struct	DDDOptions
	the options of DDDAStar, besides those of all the searches More...
class	DDDAStar
	the A* search of a Domain with delayed duplicate detection on the disk More...
class	ZobristDistribution
	HDA*[Z]: Zobrist hashing of the features of the state. More...
class	AbstractZobristDistribution
	HDA[Z,Afeature]: Zobrist hashing of the abstract features (AZHDA). More...
class	AbstractStateDistribution
	HDA[Z,Astate]: the abstract state of the Domain, hashed (AHDA). More...
class	PerfectHashDistribution
	HDA*[P]: the perfect hash of the Domain modulo p. More...
class	StateHashDistribution
	the hash of the closed list, remixed with a seed More...
class	RandomDistribution
	a random worker for each generated state More...
struct	OperatorOf
	the operator that generated a state, kept in a message [see OperatorDomain]; an empty type, with op always no_op, when D is not an OperatorDomain, so that a message with [[no_unique_address]] on it does not grow More...
struct	OperatorOf< D >
class	ExplicitGraph
	a weighted graph given explicitly, searched from a source to a target More...
class	FarmAStar
	a master-worker parallel A* on a farm with feedback More...
class	GridMap
	a rectangular map of cells, each with a cost of traversal More...
class	Grid
	pathfinding on a GridMap with 4 (Moves == 4) or 8 (Moves == 8) moves More...
struct	ParallelOptions
	the options of the parallel searches: those of the sequential search, and the parameters of the parallel ones [see ParallelParams], with batches of 64 nodes flushed every 64 expansions More...
class	HDAStar
	Hash Distributed A* on a shared-memory machine. More...
class	HDAStarMPI
	Hash Distributed A* with one MPI process per worker. More...
class	IDAStar
	the iterative-deepening A* search of a Domain More...
class	MissionariesCannibals
	the missionaries and cannibals problem More...
class	MQAStar
	MultiQueue A*: one relaxed OPEN list and one CLOSED list shared by the workers. More...
struct	Node
	a node of the search graph More...
class	NQueens
	the n-queens problem, with at most 32 queens More...
struct	OpenEntry
	an entry of the OPEN list: the node and the g it had when pushed More...
struct	PASEOptions
	the options of PASE More...
class	PASE
	Parallel A* for Slow Expansions. More...
struct	PDBOptions
	the options of the construction of an AdditivePDB More...
class	TilePattern
	a pattern of the sliding-tile puzzle and the ranking of its placements More...
class	ByteEntries
	the entries of a pattern table, one byte each: the distance itself More...
class	NibbleEntries
	the entries of a pattern table, 4 bits each: the excess over Manhattan More...
class	Mod3Entries
	the entries of a pattern table, the distance modulo 3, five in a byte More...
class	ParityBitEntries
	the entries of a pattern table, the second bit of the distance, eight in a byte More...
class	MinNibbleEntries
	the entries of a pattern table, the least excess of each group of ranks More...
class	SparseEntries
	the entries of a pattern table whose excess is nonzero, by rank More...
class	PatternTable
	the distances of a pattern of the sliding-tile puzzle, encoded by Enc More...
class	AdditivePDB
	the additive heuristic of disjoint pattern tables More...
class	SlidingTilePDB
	the sliding-tile puzzle with an additive pattern database heuristic More...
class	Romania
	a trip on the road map of Romania More...
struct	PBNFOptions
	the options of SafePBNF More...
class	SafePBNF
	Safe Parallel Best-NBlock-First search. More...
class	SequenceScore
	the sliding-tile puzzle with the sequence score heuristic of Nilsson More...
struct	Word128
	an unsigned integer of 128 bits, as two words of 64 More...
class	SlidingTile
	the sliding-tile puzzle on a board of at most 25 cells More...
class	SlowDomain
	a Domain whose expansions cost a given amount of extra work More...
struct	SearchStats
	the counters of a search More...
struct	Solution
	a path from the initial state to a goal, and its cost More...
struct	SearchOptions
	the options shared by all the searches More...
class	SPAStar
	Simple Parallel A*: one OPEN and one CLOSED list shared by the workers. More...
class	ConcurrentClosed
	the closed list shared by the workers, a lock-free set of the nodes More...
class	ExplicitAdjacency
	the arcs of a weighted graph, on the GraphBuilder and ArrayGraph of ADS More...
class	GridAdjacency
	the moves from a cell of a GridMap and their costs, on the GridGraph of ADS More...
class	NodePool
	the arena of the nodes, on the Arena of ADS, on huge pages More...
class	NodeTable
	the closed list, on the PointerTable of ADS, on huge pages More...
class	HeapOpenList
	the OPEN list on the DaryHeap of ADS More...
class	BucketOpenList
	the OPEN list on the BucketQueue of ADS, for integer costs More...
class	TravelingSalesman
	the traveling salesperson problem on at most 32 cities More...
class	VacuumWorld
	the vacuum world on a row of at most 32 cells More...
class	WaterJugs
	the water jugs problem, with up to 4 jugs of at most 65535 units More...
struct	BasicEvaluation
	the outcome of the evaluation of a node, with values of type V More...
struct	BBLeaf
	a leaf of the tree explored, or a node to start a search from More...
struct	BBValueTraits
	what the B&B needs to know of the type V of its values More...
struct	BasicBBOptions
	the options of a B&B with values of type V More...
struct	BBStats
	the counters of a B&B More...
struct	BBSolution
	the outcome of a B&B More...
class	BBQueue
	the open nodes of a B&B, ordered by a key More...
class	BranchAndBoundSearch
	the sequential best-first search with an incumbent More...
class	DeterministicBranchAndBound
	the parallel B&B by synchronous rounds More...
class	FarmBranchAndBound
	the master-worker B&B on a farm with feedback More...
struct	BasicKnapsack
	a 0-1 knapsack, its items sorted by decreasing ratio of profit to weight More...
class	MPIBranchAndBoundSearch
	the distributed B&B with one MPI process per worker More...
class	MultiQueueBranchAndBound
	the parallel B&B on the MultiQueue of ADS More...
struct	BasicParallelBBOptions
	the options of the parallel B&B with values of type V More...
class	BBIncumbent
	the incumbent shared by the workers of a parallel B&B More...
class	SharedBranchAndBound
	the parallel B&B with one queue shared by the workers More...
class	DistributedBranchAndBound
	the parallel B&B with a queue per worker and the children sent to their owners More...
class	SelfSplitBranchAndBound
	the parallel B&B by a split of the tree after a sampling More...
class	StealingBranchAndBound
	the parallel B&B by work stealing More...
struct	ParallelParams
	the parameters shared by the parallel searches More...
class	Stopwatch
	a wall-clock stopwatch, started at construction More...

Concepts
concept	DiskDomain
	a Domain that DDDAStar can search: integer costs, since a bucket is a pair of values, and states that are trivially copyable, since they are written to the disk as their bytes
concept	IncrementalDistribution
	a distribution whose owners follow the moves
concept	Domain
	a search domain
concept	FeatureDomain
	a Domain whose states are described by a set of features
concept	IncrementalFeatureDomain
	a FeatureDomain that also gives the features changed by a move
concept	AbstractFeatureDomain
	a FeatureDomain that also provides a feature projection
concept	AbstractStateDomain
	a Domain with a state abstraction
concept	NBlockDomain
	a Domain whose state space is partitioned into nblocks
concept	PairwiseDomain
	a Domain with a heuristic between any two states
concept	OperatorDomain
	a Domain that knows the operator by which a state was generated
concept	PerfectHashDomain
	a Domain with a perfect hash of its states
concept	BBValue
	a type of values of a B&B: signed, totally ordered, made from an int, and with its BBValueTraits
concept	BBEvaluator
	what evaluates and branches the nodes of a B&B
concept	BranchAndBound
	a B&B problem
concept	HashedBranchAndBound
	a B&B problem that gives a hash of its nodes
concept	EstimatingBranchAndBound
	a B&B problem that estimates the best feasible value under a node
concept	MPIBranchAndBound
	a B&B problem whose nodes and values can travel between processes
concept	MultiQueueValue
	the values that the MultiQueue of ADS takes as keys: arithmetic, with a greatest value, and atomic with no lock

Typedefs
template<Domain D>
using	state_t = typename D::state_type
	the state type of a Domain
template<Domain D>
using	cost_t = typename D::cost_type
	the cost type of a Domain
using	Partition = std::vector< std::vector< int > >
	a partition of the tiles into disjoint patterns
using	EightPuzzle = SlidingTile< 3 , 3 >
	the 8-puzzle
using	FifteenPuzzle = SlidingTile< 4 , 4 >
	the 15-puzzle
using	TwentyFourPuzzle = SlidingTile< 5 , 5 >
	the 24-puzzle
using	Evaluation = BasicEvaluation<>
	the outcome of the evaluation of a node, with values of type double
template<class P>
using	bb_value_t = typename detail::bb_value< P >::type
	the type of the values of the B&B problem P: its value_type, or double
using	BBOptions = BasicBBOptions<>
	the options of a B&B with values of type double
using	Knapsack = BasicKnapsack<>
	the 0-1 knapsack with values of type double
using	ParallelBBOptions = BasicParallelBBOptions<>
	the options of the parallel B&B with values of type double

Enumerations
enum class	OpenKind { automatic , heap , buckets }
	the kind of OPEN list a search uses More...
enum class	BlankRule : std::uint8_t { ignored , minimized }
	how the abstraction of a pattern treats the blank More...
enum class	Status { solved , unsolvable , node_limit }
	how a search ended More...
enum class	Sense { minimize , maximize }
	the sense of the optimization More...
enum class	Selection { best_first , depth_first , breadth_first , best_estimate , plunging }
	the order in which the open nodes are extracted More...
enum class	BBStatus { optimal , infeasible , node_limit , time_limit }
	how a B&B ended More...
enum class	BBLeafKind { open , pruned , feasible , infeasible }
	why a node is a leaf of the tree explored More...
enum class	BBScheme { sequential , shared , distributed , deterministic , selfsplit , stealing , multiqueue }
	the schemes of the B&B of the core More...

Functions
template<Domain D>
Solution< state_t< D >, cost_t< D > >	astar (const D &domain, OpenKind open=OpenKind::automatic, const SearchOptions &options={})
	searches a Domain with A*, choosing the OPEN list at run time
template<DiskDomain D>
Solution< state_t< D >, cost_t< D > >	ddd_astar (const D &domain, const SearchOptions &options={}, const DDDOptions &ddd={})
	searches a Domain with A* and delayed duplicate detection on the disk
unsigned	reduce (std::uint64_t h, unsigned p) noexcept
	the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 64-bit hash value
unsigned	key_owner (std::uint32_t k, unsigned p) noexcept
	the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 32-bit key
template<Domain D, class X>
std::uint32_t	distribution_key (const X &x, const state_t< D > &s)
	the key of s for x, 0 if X is not an IncrementalDistribution
template<Domain D, class X>
auto	successor_owners (const X &x, const state_t< D > &s, std::uint32_t k, unsigned p)
	the owner among p workers and the key of each successor of s
template<Domain D, class F>
void	for_each_child (const D &d, const state_t< D > &s, cost_t< D > h, std::uint8_t op, F &&f)
	the successors of s but its parent, when D knows the operators
template<Domain D>
Solution< state_t< D >, cost_t< D > >	idastar (const D &domain, const SearchOptions &options={})
	searches a Domain with IDA*
template<class Cost>
constexpr Cost	infinite_cost (void) noexcept
	the largest value of a cost type, used as "no incumbent yet"
template<class Cost> requires std::is_integral_v< Cost >
constexpr std::uint64_t	packed_fg (Cost g, Cost h) noexcept
	with integer costs, f = g + h in the high half of a word and the complement of g in the low one, so that the smaller word has the smaller f and, on the ties of f, the larger g, as the OPEN of AStar
template<class NodeT>
auto	trace_path (const NodeT *goal)
	the states from the root to goal, following the parent pointers
Partition	partition_15_7_8 (void)
	the partition 7-8 of the 15-puzzle of Korf and Felner (AIJ 2002)
Partition	partition_15_5_5_5 (void)
	the partition 5-5-5 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
Partition	partition_15_6_6_3 (void)
	the partition 6-6-3 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)
Partition	partition_24_6_6_6_6 (void)
	the partition 6-6-6-6 of the 24-puzzle of Korf and Felner (AIJ 2002)
template<BranchAndBound P>
BBSolution< typename P::node_type, bb_value_t< P > >	branch_and_bound (const P &problem, const BasicBBOptions< bb_value_t< P > > &o={})
	the sequential B&B of a problem, with the given options
template<BranchAndBound P>
BBSolution< typename P::node_type, bb_value_t< P > >	branch_and_bound (const P &problem, std::vector< BBLeaf< typename P::node_type, bb_value_t< P > > > seeds, const BasicBBOptions< bb_value_t< P > > &o={})
	the sequential B&B of the subtrees of the given nodes [see BranchAndBoundSearch::solve()], with the given options
std::string_view	bb_scheme_name (BBScheme s)
	the name of the scheme s
BBScheme	bb_scheme (std::string_view name)
	the scheme of the given name; throws std::invalid_argument if there is none
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
BBSolution< typename P::node_type, bb_value_t< P > >	parallel_branch_and_bound (const P &problem, BBScheme s, const BasicParallelBBOptions< bb_value_t< P > > &o={}, std::optional< std::vector< BBLeaf< typename P::node_type, bb_value_t< P > > > > seeds=std::nullopt)
	the B&B of the problem by the scheme s on the given runtime, with the given options, from the given nodes [see BranchAndBoundSearch::solve()] or from the root if none; throws std::invalid_argument for the scheme multiqueue if the values are not atomic with no lock [see MultiQueueValue]
void	pin_worker (unsigned i) noexcept
	pins the calling thread to the i-th CPU it may run on, if PBEFS_PIN is set
template<ADS::WorkerExecutor Executor, class F>
void	run_workers (Executor *ex, unsigned p, F &&f)
	runs the workers f( 0 ) , ... , f( p - 1 ) at once on an Executor
void	prefetch (const void *p) noexcept
	hints the processor to bring the cache line of p in, for reading
template<class Gen>
double	random_unit (Gen &gen)
	a real number in [ 0 , 1 ) from the next word of a 64-bit generator
template<class Gen>
std::uint64_t	random_below (Gen &gen, std::uint64_t n)
	an integer in [ 0 , n ) from the next word of a 64-bit generator, n > 0

Variables
constexpr std::uint8_t	no_op = 0xFF
	the operator of the root, which no state was generated by
constexpr double	grid_sqrt2 = 1.41421356237309504880
	\( \sqrt{2} \), the cost of a diagonal move per unit of cost of a cell
constexpr std::size_t	cache_line = 64
	the size of a cache line, used to keep the data of the workers apart

Detailed Description

namespace for the Parallel Best-First Search library

Typedef Documentation

◆ bb_value_t

template<class P>

using bb_value_t = typename detail::bb_value< P >::type

the type of the values of the B&B problem P: its value_type, or double

◆ BBOptions

using BBOptions = BasicBBOptions<>

the options of a B&B with values of type double

◆ cost_t

template<Domain D>

using cost_t = typename D::cost_type

the cost type of a Domain

◆ EightPuzzle

using EightPuzzle = SlidingTile< 3 , 3 >

the 8-puzzle

◆ Evaluation

using Evaluation = BasicEvaluation<>

the outcome of the evaluation of a node, with values of type double

◆ FifteenPuzzle

using FifteenPuzzle = SlidingTile< 4 , 4 >

the 15-puzzle

◆ Knapsack

using Knapsack = BasicKnapsack<>

the 0-1 knapsack with values of type double

◆ ParallelBBOptions

using ParallelBBOptions = BasicParallelBBOptions<>

the options of the parallel B&B with values of type double

◆ Partition

using Partition = std::vector< std::vector< int > >

a partition of the tiles into disjoint patterns

◆ state_t

template<Domain D>

using state_t = typename D::state_type

the state type of a Domain

◆ TwentyFourPuzzle

using TwentyFourPuzzle = SlidingTile< 5 , 5 >

the 24-puzzle

Enumeration Type Documentation

◆ BBLeafKind

enum class BBLeafKind

strong

why a node is a leaf of the tree explored

Enumerator
open	left open by a limit
pruned	its bound cannot improve the incumbent
feasible	evaluated with a feasible value, and not branched
infeasible	found infeasible

◆ BBScheme

enum class BBScheme

strong

the schemes of the B&B of the core

Each has a name, given by bb_scheme_name() and read by bb_scheme().

Enumerator
sequential	one worker [see BranchAndBoundSearch]
shared	one shared queue [see SharedBranchAndBound]
distributed	a queue per worker [see DistributedBranchAndBound]
deterministic	synchronous rounds [see DeterministicBranchAndBound]
selfsplit	a split of a sampling [see SelfSplitBranchAndBound]
stealing	work stealing [see StealingBranchAndBound]
multiqueue	a MultiQueue [see MultiQueueBranchAndBound]

◆ BBStatus

enum class BBStatus

strong

how a B&B ended

Enumerator
optimal	the incumbent is optimal within the tolerance
infeasible	no feasible solution exists (nor was given)
node_limit	the limit on the evaluated nodes was reached first
time_limit	the time limit was reached first

◆ BlankRule

enum class BlankRule : std::uint8_t

strong

how the abstraction of a pattern treats the blank

Enumerator
ignored	the blank is not in the abstract state: consistent tables
minimized	the blank is, and the table keeps the least distance

◆ OpenKind

enum class OpenKind

strong

the kind of OPEN list a search uses

Enumerator
automatic	buckets for integer costs, heap otherwise
heap	HeapOpenList.
buckets	BucketOpenList (integer costs only).

◆ Selection

enum class Selection

strong

the order in which the open nodes are extracted

Enumerator
best_first	the least bound first
depth_first	the deepest node first
breadth_first	the shallowest node first, the oldest among those
best_estimate	the least estimate( n ) of the problem first
plunging	a dive into the children, then best-first

◆ Sense

enum class Sense

strong

the sense of the optimization

Enumerator
minimize	the least value is sought
maximize	the largest value is sought

◆ Status

enum class Status

strong

how a search ended

Enumerator
solved	an optimal path has been found
unsolvable	OPEN emptied without reaching a goal.
node_limit	the limit on the stored nodes was reached first

Function Documentation

◆ astar()

template<Domain D>

Solution< state_t< D >, cost_t< D > > astar	(	const D &	domain,
		OpenKind	open = OpenKind::automatic,
		const SearchOptions &	options = {} )

nodiscard

searches a Domain with A*, choosing the OPEN list at run time

Searches domain with A*; the OPEN list is the bucket queue for integer costs and the heap otherwise, unless open asks for the heap.

◆ bb_scheme()

BBScheme bb_scheme ( std::string_view name )

inlinenodiscard

the scheme of the given name; throws std::invalid_argument if there is none

◆ bb_scheme_name()

std::string_view bb_scheme_name ( BBScheme s )

inlinenodiscard

the name of the scheme s

◆ branch_and_bound() [1/2]

template<BranchAndBound P>

BBSolution< typename P::node_type, bb_value_t< P > > branch_and_bound	(	const P &	problem,
		const BasicBBOptions< bb_value_t< P > > &	o = {} )

nodiscard

the sequential B&B of a problem, with the given options

◆ branch_and_bound() [2/2]

template<BranchAndBound P>

BBSolution< typename P::node_type, bb_value_t< P > > branch_and_bound	(	const P &	problem,
		std::vector< BBLeaf< typename P::node_type, bb_value_t< P > > >	seeds,
		const BasicBBOptions< bb_value_t< P > > &	o = {} )

nodiscard

the sequential B&B of the subtrees of the given nodes [see BranchAndBoundSearch::solve()], with the given options

◆ ddd_astar()

template<DiskDomain D>

Solution< state_t< D >, cost_t< D > > ddd_astar	(	const D &	domain,
		const SearchOptions &	options = {},
		const DDDOptions &	ddd = {} )

nodiscard

searches a Domain with A* and delayed duplicate detection on the disk

◆ distribution_key()

template<Domain D, class X>

std::uint32_t distribution_key	(	const X &	x,
		const state_t< D > &	s )

nodiscard

the key of s for x, 0 if X is not an IncrementalDistribution

◆ for_each_child()

template<Domain D, class F>

void for_each_child	(	const D &	d,
		const state_t< D > &	s,
		cost_t< D >	h,
		std::uint8_t	op,
		F &&	f )

the successors of s but its parent, when D knows the operators

Calls f( t , c , h_t , op_t ) for every successor t of s, s having been generated by the operator op: without the one that the inverse of op leads to and with op_t the operator of t if D is an OperatorDomain, with all of them and op_t = no_op otherwise.

◆ idastar()

template<Domain D>

Solution< state_t< D >, cost_t< D > > idastar	(	const D &	domain,
		const SearchOptions &	options = {} )

nodiscard

searches a Domain with IDA*

◆ infinite_cost()

template<class Cost>

Cost infinite_cost ( void )

nodiscardconstexprnoexcept

the largest value of a cost type, used as "no incumbent yet"

◆ key_owner()

unsigned key_owner	(	std::uint32_t	k,
		unsigned	p )

inlinenodiscardnoexcept

the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 32-bit key

reduce( k \( 2^{32} \) , p ), i.e., \( \lfloor k p / 2^{32} \rfloor \), the key standing for the high bits of a hash.

◆ packed_fg()

template<class Cost>
requires std::is_integral_v< Cost >

std::uint64_t packed_fg	(	Cost	g,
		Cost	h )

nodiscardconstexprnoexcept

with integer costs, f = g + h in the high half of a word and the complement of g in the low one, so that the smaller word has the smaller f and, on the ties of f, the larger g, as the OPEN of AStar

Precondition: \( 0 \leq g \) and \( 0 \leq g + h < 2^{32} \)

◆ parallel_branch_and_bound()

template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>

BBSolution< typename P::node_type, bb_value_t< P > > parallel_branch_and_bound	(	const P &	problem,
		BBScheme	s,
		const BasicParallelBBOptions< bb_value_t< P > > &	o = {},
		std::optional< std::vector< BBLeaf< typename P::node_type, bb_value_t< P > > > >	seeds = std::nullopt )

nodiscard

the B&B of the problem by the scheme s on the given runtime, with the given options, from the given nodes [see BranchAndBoundSearch::solve()] or from the root if none; throws std::invalid_argument for the scheme multiqueue if the values are not atomic with no lock [see MultiQueueValue]

◆ partition_15_5_5_5()

Partition partition_15_5_5_5 ( void )

inlinenodiscard

the partition 5-5-5 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)

◆ partition_15_6_6_3()

Partition partition_15_6_6_3 ( void )

inlinenodiscard

the partition 6-6-3 of the 15-puzzle of Felner, Korf and Hanan (JAIR 2004)

◆ partition_15_7_8()

Partition partition_15_7_8 ( void )

inlinenodiscard

the partition 7-8 of the 15-puzzle of Korf and Felner (AIJ 2002)

◆ partition_24_6_6_6_6()

Partition partition_24_6_6_6_6 ( void )

inlinenodiscard

the partition 6-6-6-6 of the 24-puzzle of Korf and Felner (AIJ 2002)

◆ pin_worker()

void pin_worker ( unsigned i )

inlinenoexcept

pins the calling thread to the i-th CPU it may run on, if PBEFS_PIN is set

If the environment variable PBEFS_PIN is set to a non-empty value other than 0, binds the calling thread to the i-th CPU (modulo their number) of the affinity mask of the process, where the system allows it [see ADS::pinThread()]; otherwise does nothing. The workers of every search call it at their start, so that they are placed the same way on every executor.

◆ prefetch()

void prefetch ( const void * p )

inlinenoexcept

hints the processor to bring the cache line of p in, for reading

◆ random_below()

template<class Gen>

std::uint64_t random_below	(	Gen &	gen,
		std::uint64_t	n )

nodiscard

an integer in [ 0 , n ) from the next word of a 64-bit generator, n > 0

◆ random_unit()

template<class Gen>

double random_unit ( Gen & gen )

nodiscard

a real number in [ 0 , 1 ) from the next word of a 64-bit generator

The distributions of <random> are not the same on every standard library, while the words of std::mt19937_64 are; this and random_below() draw from those words directly, so that a seed gives the same instance on every platform.

◆ reduce()

unsigned reduce	(	std::uint64_t	h,
		unsigned	p )

inlinenodiscardnoexcept

the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 64-bit hash value

Maps h to \( \lfloor h p / 2^{64} \rfloor \), the multiply-high reduction of Lemire, which uses the high bits of \( h \) and is unbiased for a uniform \( h \).

◆ run_workers()

template<ADS::WorkerExecutor Executor, class F>

void run_workers	(	Executor *	ex,
		unsigned	p,
		F &&	f )

runs the workers f( 0 ) , ... , f( p - 1 ) at once on an Executor

Calls f( i ) for i = 0 , ... , p - 1 by the run() of *ex, or, if ex is nullptr, of an Executor of p threads built for the purpose, each call on a thread of its own after pin_worker( i ) but on the thread of the caller, which stays where it is, and returns when all the calls have returned.

◆ successor_owners()

template<Domain D, class X>

auto successor_owners	(	const X &	x,
		const state_t< D > &	s,
		std::uint32_t	k,
		unsigned	p )

nodiscard

the owner among p workers and the key of each successor of s

Returns a callable that maps a successor t of s to the pair of x.owner( t , p ) and distribution_key( x , t ), computed from the key k of s if X is an IncrementalDistribution; s and x must outlive it.

◆ trace_path()

template<class NodeT>

auto trace_path ( const NodeT * goal )

nodiscard

the states from the root to goal, following the parent pointers

Variable Documentation

◆ cache_line

std::size_t cache_line = 64

inlineconstexpr

the size of a cache line, used to keep the data of the workers apart

◆ grid_sqrt2

double grid_sqrt2 = 1.41421356237309504880

inlineconstexpr

\( \sqrt{2} \), the cost of a diagonal move per unit of cost of a cell

◆ no_op

std::uint8_t no_op = 0xFF

inlineconstexpr

the operator of the root, which no state was generated by

Classes

Concepts

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ bb_value_t

◆ BBOptions

◆ cost_t

◆ EightPuzzle

◆ Evaluation

◆ FifteenPuzzle

◆ Knapsack

◆ ParallelBBOptions

◆ Partition

◆ state_t

◆ TwentyFourPuzzle

Enumeration Type Documentation

◆ BBLeafKind

◆ BBScheme

◆ BBStatus

◆ BlankRule

◆ OpenKind

◆ Selection

◆ Sense

◆ Status

Function Documentation

◆ astar()

◆ bb_scheme()

◆ bb_scheme_name()

◆ branch_and_bound() [1/2]

◆ branch_and_bound() [2/2]

◆ ddd_astar()

◆ distribution_key()

◆ for_each_child()

◆ idastar()

◆ infinite_cost()

◆ key_owner()

◆ packed_fg()

◆ parallel_branch_and_bound()

◆ partition_15_5_5_5()

◆ partition_15_6_6_3()

◆ partition_15_7_8()

◆ partition_24_6_6_6_6()

◆ pin_worker()

◆ prefetch()

◆ random_below()

◆ random_unit()

◆ reduce()

◆ run_workers()

◆ successor_owners()

◆ trace_path()

Variable Documentation

◆ cache_line

◆ grid_sqrt2

◆ no_op