gtsam::DiscreteSearch Class Reference

DiscreteSearch: Search for the K best solutions. More...

#include <DiscreteSearch.h>

Classes
struct	Slot
struct	Solution

Public Member Functions
Testable
void	print (const std::string &name="DiscreteSearch: ", const KeyFormatter &formatter=DefaultKeyFormatter) const
Standard API
double	lowerBound () const
	Return lower bound on the cost-to-go for the entire search. More...
const std::vector< Slot > &	slots () const
	Read access to the slots. More...
std::vector< Solution >	run (size_t K=1) const
	Search for the K best solutions. More...

Private Member Functions
double	computeHeuristic ()

Private Attributes
double	lowerBound_
	Lower bound on the cost-to-go for the entire search. More...
std::vector< Slot >	slots_
	The slots to fill in the search. More...

Standard Constructors
static DiscreteSearch	FromFactorGraph (const DiscreteFactorGraph &factorGraph, const Ordering &ordering, bool buildJunctionTree=false)
	DiscreteSearch (const DiscreteEliminationTree &etree)
	Construct from a DiscreteEliminationTree. More...
	DiscreteSearch (const DiscreteJunctionTree &junctionTree)
	Construct from a DiscreteJunctionTree. More...
	DiscreteSearch (const DiscreteBayesNet &bayesNet)
	DiscreteSearch (const DiscreteBayesTree &bayesTree)
	Construct from a DiscreteBayesTree. More...

Detailed Description

DiscreteSearch: Search for the K best solutions.

This class is used to search for the K best solutions in a DiscreteBayesNet. This is implemented with a modified A* search algorithm that uses a priority queue to manage the search nodes. That machinery is defined in the .cpp file. The heuristic we use is the sum of the log-probabilities of the maximum-probability assignments for each slot, for all slots to the right of the current slot.

TODO: The heuristic could be refined by using the partial assignment in search node to refine the max-probability assignment for the remaining slots. This would incur more computation but will lead to fewer expansions.

Definition at line 44 of file DiscreteSearch.h.

Constructor & Destructor Documentation

DiscreteSearch() [1/4]

gtsam::DiscreteSearch::DiscreteSearch

(

const DiscreteEliminationTree &

etree

)

Construct from a DiscreteEliminationTree.

Definition at line 145 of file DiscreteSearch.cpp.

DiscreteSearch() [2/4]

gtsam::DiscreteSearch::DiscreteSearch

(

const DiscreteJunctionTree &

junctionTree

)

Construct from a DiscreteJunctionTree.

Definition at line 161 of file DiscreteSearch.cpp.

DiscreteSearch() [3/4]

gtsam::DiscreteSearch::DiscreteSearch

(

const DiscreteBayesNet &

bayesNet

)

Definition at line 191 of file DiscreteSearch.cpp.

DiscreteSearch() [4/4]

gtsam::DiscreteSearch::DiscreteSearch

(

const DiscreteBayesTree &

bayesTree

)

Construct from a DiscreteBayesTree.

Definition at line 201 of file DiscreteSearch.cpp.

Member Function Documentation

computeHeuristic()

double gtsam::DiscreteSearch::computeHeuristic ( )

private

Compute the cumulative lower-bound cost-to-go after each slot is filled.

Returns

the estimated lower bound of the cost for all slots.

Definition at line 277 of file DiscreteSearch.cpp.

FromFactorGraph()

DiscreteSearch gtsam::DiscreteSearch::FromFactorGraph ( const DiscreteFactorGraph &  factorGraph, const Ordering &  ordering, bool  buildJunctionTree = false  )

static

Construct from a DiscreteFactorGraph.

Internally creates either an elimination tree or a junction tree. The latter incurs more up-front computation but the search itself might be faster. Then again, for the elimination tree, the heuristic will be more fine-grained (more slots).

Parameters

factorGraph	The factor graph to search over.
ordering	The ordering used to create etree (and maybe jtree).
buildJunctionTree	Whether to build a junction tree or not.

Definition at line 179 of file DiscreteSearch.cpp.

lowerBound()

double gtsam::DiscreteSearch::lowerBound ( ) const

inline

Return lower bound on the cost-to-go for the entire search.

Definition at line 135 of file DiscreteSearch.h.

print()

void gtsam::DiscreteSearch::print	(	const std::string &	name = "DiscreteSearch: ",
		const KeyFormatter &	formatter = DefaultKeyFormatter
	)		const

Print the tree to cout

Definition at line 215 of file DiscreteSearch.cpp.

run()

std::vector< Solution > gtsam::DiscreteSearch::run

(

size_t

K = 1

)

const

Search for the K best solutions.

This method performs a search to find the K best solutions for the given DiscreteBayesNet. It uses a priority queue to manage the search nodes, expanding nodes with the smallest bound first. The search continues until all possible nodes have been expanded or pruned.

Returns

A vector of the K best solutions found during the search.

Definition at line 226 of file DiscreteSearch.cpp.

slots()

const std::vector<Slot>& gtsam::DiscreteSearch::slots ( ) const

inline

Read access to the slots.

Definition at line 138 of file DiscreteSearch.h.

Member Data Documentation

lowerBound_

double gtsam::DiscreteSearch::lowerBound_

private

Lower bound on the cost-to-go for the entire search.

Definition at line 161 of file DiscreteSearch.h.

slots_

std::vector<Slot> gtsam::DiscreteSearch::slots_

private

The slots to fill in the search.

Definition at line 162 of file DiscreteSearch.h.

---

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

• DiscreteSearch.h
• DiscreteSearch.cpp