gtsam::DiscreteSearch Class Reference

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.

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

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

Classes
struct	Slot
	We structure the search as a set of slots, each with a factor and a set of variable assignments that need to be chosen. More...
struct	Solution
	A solution is a set of assignments, covering all the slots. More...

Member Function Documentation

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.

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.

---

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

• /tmp/gtsam-4.3.0-doxygen.rsXPUS/source/gtsam/discrete/DiscreteSearch.h
• /tmp/gtsam-4.3.0-doxygen.rsXPUS/source/gtsam/discrete/DiscreteSearch.cpp