A star search algorithm. More...
#include <astar.hxx>
Classes | |
| struct | Parameter |
Public Types | |
| enum | Heuristic { DEFAULT_HEURISTIC = 0, FAST_HEURISTIC = 1, STANDARD_HEURISTIC = 2 } |
| typedef GM | GraphicalModelType |
| graphical model type | |
| typedef GraphicalModelType::template Rebind< true >::RebindType | EditableGraphicalModelType |
| typedef ACC | AccumulationType |
| accumulation type | |
| typedef std::vector< LabelType > | ConfVec |
| configuration vector type | |
| typedef ConfVec::iterator | ConfVecIt |
| configuration iterator | |
| typedef VerboseVisitor< AStar < GM, ACC > > | VerboseVisitorType |
| visitor | |
| typedef TimingVisitor< AStar < GM, ACC > > | TimingVisitorType |
| typedef EmptyVisitor< AStar < GM, ACC > > | EmptyVisitorType |
Public Member Functions | |
| AStar (const GM &gm, Parameter para=Parameter()) | |
| constructor | |
| virtual std::string | name () const |
| const GraphicalModelType & | graphicalModel () const |
| virtual InferenceTermination | infer () |
| virtual void | reset () |
| reset | |
| template<class VisitorType > | |
| InferenceTermination | infer (VisitorType &vistitor) |
| inference with visitor | |
| ValueType | bound () const |
| return a bound on the solution | |
| virtual InferenceTermination | marginal (const size_t, IndependentFactorType &out) const |
| output a solution for a marginal for a specific variable | |
| virtual InferenceTermination | factorMarginal (const size_t, IndependentFactorType &out) const |
| output a solution for a marginal for all variables connected to a factor | |
| virtual InferenceTermination | arg (std::vector< LabelType > &v, const size_t=1) const |
| output a solution | |
| virtual InferenceTermination | args (std::vector< std::vector< LabelType > > &v) const |
Public Attributes | |
| OPENGM_GM_TYPE_TYPEDEFS | |
A star search algorithm.
Kappes, J. H. "Inference on Highly-Connected Discrete Graphical Models with Applications to Visual Object Recognition". Ph.D. Thesis 2011 Bergtholdt, M. & Kappes, J. H. & Schnoerr, C.: "Learning of Graphical Models and Efficient Inference for Object Class Recognition", DAGM 2006 Bergtholdt, M. & Kappes, J. H. & Schmidt, S. & Schnoerr, C.: "A Study of Parts-Based Object Class Detection Using Complete Graphs" IJCV 2010
Within this implementation of the AStar-Algo the user has to set the the node order and a acyclic graph for the calculation of the heuristic. A good choice for both is critical for good performance! A heuristic which select these parameters automatically will be added in the next version
The AStar-Algo transform the problem into a shortest path problem in an exponentially large graph. Due to the problem structure, this graph can be represented implicitly! To find the shortest path we perform a best first search and use a admissable tree-based heuristic to underestimate the cost to a goal node. This lower bound allows us to reduce the search to an manageable subspace of the exponentially large search-space.
Definition at line 63 of file astar.hxx.
| typedef ACC opengm::AStar< GM, ACC >::AccumulationType |
accumulation type
Reimplemented from opengm::Inference< GM, ACC >.
| typedef std::vector<LabelType> opengm::AStar< GM, ACC >::ConfVec |
| typedef ConfVec::iterator opengm::AStar< GM, ACC >::ConfVecIt |
| typedef GraphicalModelType::template Rebind<true>::RebindType opengm::AStar< GM, ACC >::EditableGraphicalModelType |
| typedef EmptyVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::EmptyVisitorType |
| typedef GM opengm::AStar< GM, ACC >::GraphicalModelType |
graphical model type
Reimplemented from opengm::Inference< GM, ACC >.
| typedef TimingVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::TimingVisitorType |
| typedef VerboseVisitor<AStar<GM, ACC> > opengm::AStar< GM, ACC >::VerboseVisitorType |
| enum opengm::AStar::Heuristic |
| opengm::AStar< GM, ACC >::AStar | ( | const GM & | gm, | |
| Parameter | para = Parameter() | |||
| ) | [inline] |
| virtual InferenceTermination opengm::AStar< GM, ACC >::arg | ( | std::vector< LabelType > & | arg, | |
| const | argIndex = 1 | |||
| ) | const [virtual] |
output a solution
| [out] | arg | labeling |
| argIndex | solution index (0=best, 1=second best, etc.) |
Reimplemented from opengm::Inference< GM, ACC >.
| virtual InferenceTermination opengm::AStar< GM, ACC >::args | ( | std::vector< std::vector< LabelType > > & | v | ) | const [virtual] |
Reimplemented from opengm::Inference< GM, ACC >.
| ValueType opengm::AStar< GM, ACC >::bound | ( | ) | const [inline, virtual] |
return a bound on the solution
Reimplemented from opengm::Inference< GM, ACC >.
Definition at line 128 of file astar.hxx.
| virtual InferenceTermination opengm::AStar< GM, ACC >::factorMarginal | ( | const | factorIndex, | |
| IndependentFactorType & | out | |||
| ) | const [inline, virtual] |
output a solution for a marginal for all variables connected to a factor
| factorIndex | index of the factor | |
| [out] | out | the marginal |
Reimplemented from opengm::Inference< GM, ACC >.
| const AStar< GM, ACC >::GraphicalModelType & opengm::AStar< GM, ACC >::graphicalModel | ( | ) | const [inline, virtual] |
Implements opengm::Inference< GM, ACC >.
| InferenceTermination opengm::AStar< GM, ACC >::infer | ( | VisitorType & | visitor | ) | [inline] |
| InferenceTermination opengm::AStar< GM, ACC >::infer | ( | ) | [inline, virtual] |
Implements opengm::Inference< GM, ACC >.
| virtual InferenceTermination opengm::AStar< GM, ACC >::marginal | ( | const | variableIndex, | |
| IndependentFactorType & | out | |||
| ) | const [inline, virtual] |
output a solution for a marginal for a specific variable
| variableIndex | index of the variable | |
| [out] | out | the marginal |
Reimplemented from opengm::Inference< GM, ACC >.
| virtual std::string opengm::AStar< GM, ACC >::name | ( | ) | const [inline, virtual] |
Implements opengm::Inference< GM, ACC >.
| void opengm::AStar< GM, ACC >::reset | ( | ) | [inline, virtual] |
| opengm::AStar< GM, ACC >::OPENGM_GM_TYPE_TYPEDEFS |
1.6.3
