Implements Branch and Bound template method as basis for more advanced B&B implementations. More...
#include <search_branch_and_bound.hpp>
Classes | |
struct | Node |
Structure representing search tree node. More... | |
Public Types | |
typedef Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION > | parent |
typedef boost::shared_ptr < CRITERION > | PCriterion |
typedef boost::shared_ptr< SUBSET > | PSubset |
Public Member Functions | |
virtual bool | search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout) |
returns found subset of target_d features (optimizes cardinality if target_d==0) + _criterion value | |
virtual std::ostream & | print (std::ostream &os) const |
Protected Types | |
enum | NodeType { UNKNOWN, RANDOM, PREDICTED, COMPUTED } |
typedef Node * | PNode |
typedef list< Node > | ListNode |
typedef vector< ListNode > | VectorListNode |
typedef ListNode::iterator | ListNodeIter |
typedef vector< ListNode > ::iterator | TreeLevelIter |
typedef vector< Node > | VectorNode |
Protected Member Functions | |
PCriterion const & | get_criterion () const |
RETURNTYPE | get_bound_value () const |
bool | is_bound_valid () const |
int | get_k () const |
DIMTYPE | get_n () const |
DIMTYPE | get_d () const |
bool | getFirstNode (PNode &nod) |
bool | getNextNode (PNode &nod) |
bool | getFirstAvailable (PNode &avail) |
bool | getNextAvailable (PNode &avail) |
bool | getAvailable (DIMTYPE idx, PNode &avail) |
PSubset & | get_currentset () |
Node & | get_parent_node () |
Node & | get_current_node () |
void | setup_default_structures (const DIMTYPE d, const DIMTYPE n) |
initializes tree memory | |
void | update_bound (const RETURNTYPE val, const PSubset &sub) |
void | make_tree_level () |
void | process_rightmost_path () |
virtual void | process_leafs () |
can be overridden to implement prediction information learning, threading etc. | |
virtual void | initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit)=0 |
called before search - enables set-up of additional structures in descendants | |
virtual void | pre_evaluate_availables ()=0 |
assign values to each feature in _available - to be used for node ordering | |
virtual void | post_process_tree_level ()=0 |
enables to substitute missing COMPUTED values in nodes just after level creation, if needed | |
virtual bool | cut_possible ()=0 |
tests _currentset node for the possibility to cut its sub-branch | |
Protected Attributes | |
std::ostream * | shared_os |
to enable sharing the same stream across the methods below | |
boost::shared_ptr< StopWatch > | swatch |
Private Member Functions | |
DIMTYPE | get_available_size () |
void | available_add (const DIMTYPE feature) |
void | available_remove (const DIMTYPE feature) |
void | currentset_add (const DIMTYPE feature) |
void | currentset_remove (const DIMTYPE feature) |
Private Attributes | |
PCriterion | _criterion |
VectorListNode | _tree |
ListNodeIter | _nodeiter |
used in get*Node() | |
DIMTYPE | _availiter |
VectorNode | _available |
Node::feature takes the role of 1-selected/0-unselected indicator. | |
PSubset | _currentset |
_currentset subset to be evaluated | |
PSubset | _tempset |
temporary copy of _currentset subset to be modified and evaluated | |
PSubset | _boundset |
RETURNTYPE | _boundvalue |
bool | _boundvalid |
DIMTYPE | k |
current tree level | |
DIMTYPE | n |
no. of all features | |
DIMTYPE | d |
no. of features to be selected |
Implements Branch and Bound template method as basis for more advanced B&B implementations.
This is the abstract basis of concrete Branch & Bound implementations.