probfd::pdbs::StateRankingFunction Class Reference

#include "probfd/pdbs/state_ranking_function.h"

Description

Implements the state ranking function for abstract states of projections.

A state ranking function is a bijective mapping from states to so-called state ranks, which are indices in \(\{ 0, \dots, N-1 \}\), where \(N\) is the total number of states. This class implements the traditional PDB (un-) ranking functions as stated in [11] .

Public Member Functions
	StateRankingFunction (const VariablesProxy &variables, Pattern pattern)
	Constructs the ranking function for a projection specified by a given pattern and the task's variables.
unsigned int	num_states () const
	Get the number of abstract states.
unsigned int	num_vars () const
	Get the number of variables considered by the projection.
const Pattern &	get_pattern () const
	Get the pattern of the projection.
const AssignmentEnumerator &	get_enumerator () const
	Get the assignment enumerator for the projection's assignments.
long long int	get_multiplier (int i) const
	Get the ranking coefficient \( N_i = \prod_{j=0}^{i-1} |\mathcal{D}_j| \) for variable \( i \) of the projection.
int	get_domain_size (int i) const
	Get the domain size for a projection variable.
StateRank	get_abstract_rank (const State &state) const
	Get the rank of the abstract state induced by a state.
int	rank_fact (int idx, int val) const
	Ranks a projection fact by multiplying the ranking coefficient of fact's variable with the fact's value.
std::vector< int >	unrank (StateRank abstract_state) const
	Unrank a given state rank and converts it into an explicit abstract state.
int	value_of (StateRank rank, int idx) const
	Compute the value of a projection variable for the abstract state of a state rank.
bool	next_rank (StateRank &s, std::span< int > mutable_variables) const
	Compute the next-highest rank that corresponds to the same abstract state modulo a given subset of projection variable values.

Constructor & Destructor Documentation

StateRankingFunction()

probfd::pdbs::StateRankingFunction::StateRankingFunction	(	const VariablesProxy &	variables,
		Pattern	pattern )

Constructs the ranking function for a projection specified by a given pattern and the task's variables.

Member Function Documentation

num_states()

unsigned int probfd::pdbs::StateRankingFunction::num_states ( ) const

nodiscard

Get the number of abstract states.

num_vars()

unsigned int probfd::pdbs::StateRankingFunction::num_vars ( ) const

nodiscard

Get the number of variables considered by the projection.

get_pattern()

const Pattern & probfd::pdbs::StateRankingFunction::get_pattern ( ) const

nodiscard

Get the pattern of the projection.

get_enumerator()

const AssignmentEnumerator & probfd::pdbs::StateRankingFunction::get_enumerator ( ) const

nodiscard

Get the assignment enumerator for the projection's assignments.

get_multiplier()

long long int probfd::pdbs::StateRankingFunction::get_multiplier ( int i ) const

nodiscard

Get the ranking coefficient \( N_i = \prod_{j=0}^{i-1} |\mathcal{D}_j| \) for variable \( i \) of the projection.

get_domain_size()

int probfd::pdbs::StateRankingFunction::get_domain_size ( int i ) const

nodiscard

Get the domain size for a projection variable.

get_abstract_rank()

StateRank probfd::pdbs::StateRankingFunction::get_abstract_rank ( const State & state ) const

nodiscard

Get the rank of the abstract state induced by a state.

Computes the value

\[ rank(s) = \sum_{i=0}^{k} N_i s[v_i] \]

where \(N_i = \prod_{j=0}^{i-1} |\mathcal{D}_j|\) is the ranking coefficient of projection variable \(i \in \{1, \dots, k\}\).

rank_fact()

int probfd::pdbs::StateRankingFunction::rank_fact ( int idx, int val ) const

nodiscard

Ranks a projection fact by multiplying the ranking coefficient of fact's variable with the fact's value.

Given the projection fact \((i, d)\), computes the value \(N_i \cdot d\) where \(N_i = \prod_{j=0}^{i-1} |\mathcal{D}_j|\) is the ranking coefficient of projection variable \(i \in \{1, \dots, k\}\).

unrank()

std::vector< int > probfd::pdbs::StateRankingFunction::unrank ( StateRank abstract_state ) const

nodiscard

Unrank a given state rank and converts it into an explicit abstract state.

The unranked abstract state \(unrank(r)\) for the rank \(r\) is computes as

\[ unrank(r)[v_i] = \lfloor \frac{r}{N_i} \rfloor \mod \mathcal{D}_i \]

where \(N_i = \prod_{j=0}^{i-1} |\mathcal{D}_j|\) is the ranking coefficient of projection variable \(i \in \{1, \dots, k\}\).

value_of()

int probfd::pdbs::StateRankingFunction::value_of ( StateRank rank, int idx ) const

nodiscard

Compute the value of a projection variable for the abstract state of a state rank.

In detail, computes the value

\[ unrank(r)[v_i] = \lfloor \frac{r}{N_i} \rfloor \mod \mathcal{D}_i. \]

next_rank()

bool probfd::pdbs::StateRankingFunction::next_rank	(	StateRank &	s,
		std::span< int >	mutable_variables ) const

Compute the next-highest rank that corresponds to the same abstract state modulo a given subset of projection variable values.

In detail, let \(r\) be the input rank and let \(\{i_1, \dots, i_m\}\) be the subset of projection variables. Define

\[ d_{i_j} = \begin{cases} unrank(r)[v_{i_j}] + 1 & unrank(r)[v_{i_j}] \neq \mathcal{D}_{i_j} - 1,\\ 0 & unrank(r)[v_{i_j}] = \mathcal{D}_{i_j} - 1. \end{cases} \]

for \(i \in \{1, \dots, m\}\). Then the returned rank is \(r' = \sum_{i=0}^{k} N_i d_i'\).

Returns

false iff the rank is already maximal, in which case the lowest rank is returned.