This class does the basic permutation calculation in lexicographical order. More...

#include <TreePermutationPDB.h>

Inheritance diagram for TreePermutationPDB< state, action, environment, bits >:

[legend]

Collaboration diagram for TreePermutationPDB< state, action, environment, bits >:

[legend]

Public Member Functions
	TreePermutationPDB (environment *e, const state &s, const std::vector< int > &distincts)

virtual uint64_t	GetPDBHash (const state &s, int threadID=0) const

virtual void	GetStateFromPDBHash (uint64_t hash, state &s, int threadID=0) const

virtual uint64_t	GetAbstractHash (const state &s, int threadID=0) const

virtual state	GetStateFromAbstractState (state &s)

std::string	GetFileName (const char *prefix)

Public Member Functions inherited from PermutationPDB< state, action, environment, 8 >
	PermutationPDB (environment *e, const state &s, const std::vector< int > &distincts)

virtual uint64_t	GetPDBSize () const

virtual state	GetStateFromAbstractState (state &s) const=0

bool	Load (FILE *f)

bool	Load (const char *prefix)

void	Save (FILE *f)

void	Save (const char *prefix)

Public Member Functions inherited from PDBHeuristic< state, action, environment, state, bits >
	PDBHeuristic (environment *e)

virtual	~PDBHeuristic ()

void	SetGoal (const state &goal)

void	SetGoal (const std::vector< state > &goals)

virtual double	HCost (const state &a, const state &b) const

void	ShuffleValues ()
	This methods randomizes the entries in the PDB. More...

void	BuildPDB (const state &goal)

void	BuildPDB (const state &goal, int numThreads)

void	BuildPDBForward (const state &goal, int numThreads, bool useCoarseOpen=true, bool verbose=false)

void	BuildPDBForward (const std::vector< state > &goal, int numThreads, bool useCoarseOpen=true, bool verbose=false)

void	BuildPDBBackward (const state &goal, int numThreads)

void	BuildPDBForwardBackward (const state &goal, int numThreads)

void	BuildAdditivePDB (const state &goal, int numThreads, bool useCourseOpen=true)

void	DivCompress (int factor, bool print_histogram)

void	ModCompress (int factor, bool print_histogram)

void	ModCompress (uint64_t newEntries, bool print_histogram)

void	ZeroLowValues (int limit)

void	DeltaCompress (Heuristic< state > *h, state goal, bool print_histogram)

void	FractionalDivCompress (uint64_t count, bool print_histogram)

void	FractionalModCompress (uint64_t factor, bool print_histogram)

void	ValueCompress (int maxValue, bool print_histogram)

void	ValueCompress (std::vector< int > cutoffs, bool print_histogram)

void	ValueRangeCompress (int numBits, bool print_histogram)

void	ValueRangeCompress (PDBHeuristic< state, action, environment, state, 5 > *, bool print_histogram)

void	ValueRangeCompress (PDBHeuristic< state, action, environment, state, 4 > *, bool print_histogram)

void	ValueRangeCompress (PDBHeuristic< state, action, environment, state, 3 > *, bool print_histogram)

void	ValueRangeCompress (PDBHeuristic< state, action, environment, state, 2 > *, bool print_histogram)

void	ValueRangeCompress (PDBHeuristic< state, action, environment, state, 1 > *, bool print_histogram)

void	CustomValueRangeCompress (std::vector< uint64_t > dist, int numBits, bool print_histogram)

double	PrintHistogram ()

double	GetAverageValue ()

void	GetHistogram (std::vector< uint64_t > &histogram)

Public Member Functions inherited from Heuristic< state >
	Heuristic ()

virtual	~Heuristic ()

Private Member Functions
uint64_t	Factorial (int val) const

uint64_t	FactorialUpperK (int n, int k) const

Private Attributes
const int	maxThreads = 32

std::vector< std::vector< int > >	dualCache

std::vector< std::vector< int > >	locsCache

std::vector< std::vector< int > >	tempCache

state	example

Additional Inherited Members
Public Attributes inherited from PDBHeuristic< state, action, environment, state, bits >
NBitArray< pdbBits >	PDB

int	vrcValues [1<< pdbBits]

PDBLookupType	type

uint64_t	compressionValue

environment *	env

std::vector< state >	goalState

Public Attributes inherited from Heuristic< state >
std::vector< HeuristicTreeNode >	lookups

std::vector< Heuristic * >	heuristics

uint64_t	histogram [256]

Protected Attributes inherited from PermutationPDB< state, action, environment, 8 >
std::vector< int >	distinct

size_t	puzzleSize

uint64_t	pdbSize

state	example

Detailed Description

template<class state, class action, class environment, int bits = 8>
class TreePermutationPDB< state, action, environment, bits >

This class does the basic permutation calculation in lexicographical order.

It uses the tree permutation scheme from Bonet http://aaaipress.org/Papers/Workshops/2008/WS-08-10/WS08-10-004.pdf to do this in n log n time instead of n^2 time.

Definition at line 21 of file TreePermutationPDB.h.

Constructor & Destructor Documentation

◆ TreePermutationPDB()

template<class state , class action , class environment , int bits>

TreePermutationPDB< state, action, environment, bits >::TreePermutationPDB	(	environment *	e,
		const state &	s,
		const std::vector< int > &	distincts
	)

Definition at line 90 of file TreePermutationPDB.h.

References PDBHeuristic< state, action, environment, state, bits >::SetGoal().

Member Function Documentation

◆ Factorial()

template<class state , class action , class environment , int bits>

uint64_t TreePermutationPDB< state, action, environment, bits >::Factorial ( int val ) const

private

Definition at line 191 of file TreePermutationPDB.h.

◆ FactorialUpperK()

template<class state , class action , class environment , int bits>

uint64_t TreePermutationPDB< state, action, environment, bits >::FactorialUpperK	(	int	n,
		int	k
	)		const

private

Definition at line 217 of file TreePermutationPDB.h.

◆ GetAbstractHash()

template<class state , class action , class environment , int bits = 8>

virtual uint64_t TreePermutationPDB< state, action, environment, bits >::GetAbstractHash	(	const state &	s,
		int	threadID = `0`
	)		const

inlinevirtual

Implements PermutationPDB< state, action, environment, 8 >.

Definition at line 27 of file TreePermutationPDB.h.

References TreePermutationPDB< state, action, environment, bits >::GetPDBHash().

◆ GetFileName()

template<class state , class action , class environment , int bits>

std::string TreePermutationPDB< state, action, environment, bits >::GetFileName ( const char * prefix )

virtual

Reimplemented from PermutationPDB< state, action, environment, 8 >.

Definition at line 203 of file TreePermutationPDB.h.

References PermutationPDB< state, action, environment, bits >::GetFileName().

◆ GetPDBHash()

template<class state , class action , class environment , int bits>

uint64_t TreePermutationPDB< state, action, environment, bits >::GetPDBHash	(	const state &	s,
		int	threadID = `0`
	)		const

virtual

Implements PermutationPDB< state, action, environment, 8 >.

Definition at line 98 of file TreePermutationPDB.h.

References mylog2().

Referenced by TreePermutationPDB< state, action, environment, bits >::GetAbstractHash().

◆ GetStateFromAbstractState()

template<class state , class action , class environment , int bits = 8>

virtual state TreePermutationPDB< state, action, environment, bits >::GetStateFromAbstractState ( state & s )

inlinevirtual

Definition at line 28 of file TreePermutationPDB.h.

◆ GetStateFromPDBHash()

template<class state , class action , class environment , int bits>

void TreePermutationPDB< state, action, environment, bits >::GetStateFromPDBHash	(	uint64_t	hash,
		state &	s,
		int	threadID = `0`
	)		const

virtual

Implements PermutationPDB< state, action, environment, 8 >.

Definition at line 145 of file TreePermutationPDB.h.

References mylog2().

Member Data Documentation

◆ dualCache

template<class state , class action , class environment , int bits = 8>

std::vector<std::vector<int> > TreePermutationPDB< state, action, environment, bits >::dualCache

mutableprivate

Definition at line 41 of file TreePermutationPDB.h.

◆ example

template<class state , class action , class environment , int bits = 8>

state TreePermutationPDB< state, action, environment, bits >::example

private

Definition at line 45 of file TreePermutationPDB.h.

◆ locsCache

template<class state , class action , class environment , int bits = 8>

std::vector<std::vector<int> > TreePermutationPDB< state, action, environment, bits >::locsCache

mutableprivate

Definition at line 42 of file TreePermutationPDB.h.

◆ maxThreads

template<class state , class action , class environment , int bits = 8>

const int TreePermutationPDB< state, action, environment, bits >::maxThreads = 32

private

Definition at line 38 of file TreePermutationPDB.h.

◆ tempCache

template<class state , class action , class environment , int bits = 8>

std::vector<std::vector<int> > TreePermutationPDB< state, action, environment, bits >::tempCache

mutableprivate

Definition at line 43 of file TreePermutationPDB.h.

The documentation for this class was generated from the following file:

/home/sturtevant/nightly/hog2/search/TreePermutationPDB.h

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class state, class action, class environment, int bits = 8> class TreePermutationPDB< state, action, environment, bits >

Constructor & Destructor Documentation

◆ TreePermutationPDB()

Member Function Documentation

◆ Factorial()

◆ FactorialUpperK()

◆ GetAbstractHash()

◆ GetFileName()

◆ GetPDBHash()

◆ GetStateFromAbstractState()

◆ GetStateFromPDBHash()

Member Data Documentation

◆ dualCache

◆ example

◆ locsCache

◆ maxThreads

◆ tempCache

template<class state, class action, class environment, int bits = 8>
class TreePermutationPDB< state, action, environment, bits >