Implements Dynamic_Oscillating_Search. More...

#include <search_seq_dos.hpp>

Inheritance diagram for FST::Search_DOS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >:

Public Types
typedef Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >	parent
	base class alias
typedef parent::parent	grandparent
	the shared Search base (output detail, result tracker)
typedef std::shared_ptr< EVALUATOR >	PEvaluator
	shared pointer to the sequential-step evaluator
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
Public Types inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
typedef Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef std::shared_ptr< EVALUATOR >	PEvaluator
	shared pointer to the sequential-step evaluator that implements Step()'s candidate generation and selection
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
Public Types inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef std::shared_ptr< Result_Tracker< RETURNTYPE, SUBSET > >	PResultTracker
	shared pointer to the result tracker enabled via enable_result_tracking()
typedef Search_Observer< RETURNTYPE, SUBSET >	OBSERVER
	the observer interface type this search reports through (see Search_Observer)
typedef std::shared_ptr< OBSERVER >	PObserver
	shared pointer to an OBSERVER, as set via set_observer()

Public Member Functions
	Search_DOS (const PEvaluator evaluator)
	`evaluator` must be non-null; initial_subset_enabled() is turned ON by construction (empty initial subset is permitted); target_d is ignored by DOS's search()
virtual bool	search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout) override
	returns found subset + criterion value
void	set_delta (const DIMTYPE delta)
	oscillating cycle depth
DIMTYPE	get_delta () const
	the currently configured oscillating cycle depth (see set_delta())
virtual std::ostream &	print (std::ostream &os) const override
	writes a human-readable identification of the search and its configuration; base default writes nothing
Public Member Functions inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
	Search_Sequential (const PEvaluator evaluator)
	`evaluator` must be non-null
bool	Step (const bool forward, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout)
	Performs one sequential step: adds (`forward`) or removes (!`forward`) the best g-tuple of features, g being the generalization level.
void	set_generalization_level (const DIMTYPE g)
	optional parameter to enlarge the number of considered candidates (g is the number of features added/removed in one Step)
DIMTYPE	get_generalization_level () const
	the currently configured generalization level (see set_generalization_level())
void	enable_initial_subset ()
	makes search() start from the caller-supplied contents of its `sub` argument instead of the concrete method's default (empty set for FORWARD, full set for BACKWARD)
void	disable_initial_subset ()
	reverts to the default: incoming `sub` contents are ignored by search()
bool	initial_subset_enabled () const
	true if enable_initial_subset() was called (and not since disabled by disable_initial_subset())
Public Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	enable_result_tracking (PResultTracker tracker)
	assigns a result tracker to the search process, i.e., enables logging of all evaluated subsets for future reuse (re-evaluation, etc.)
void	disable_result_tracking ()
	detaches any result tracker (result_tracker_active() then returns false)
bool	result_tracker_active () const
	true if a result tracker was assigned via enable_result_tracking() and not since disabled
void	set_output_detail (OutputDetail detail)
	sets the amount of information that is logged to output stream throughout the course of search
OutputDetail	get_output_detail () const
	the currently configured output detail level
bool	output_normal () const
	true unless output detail is SILENT
bool	output_detailed () const
	true only at the DETAILED output level
void	set_observer (PObserver observer)
	redirects search progress reporting away from the default syncout text output to `observer`

Protected Types
enum	SwingPhase { RESTART =0 , DOWN =1 , RETURN_UP =2 , UP =4 , RETURN_DOWN =8 }
	Oscillating-cycle phase for the DOS swing state machine driving search()'s inline switch. More...

Protected Attributes
DIMTYPE	_delta
	current oscillating cycle depth (max swing extent); see set_delta()
std::unique_ptr< SUBSET >	pivotsub
	the current pivot: the best-known subset (highest criterion value, smallest cardinality among equals), around which DOWN/UP swings are performed
std::unique_ptr< SUBSET >	pivot_top
	the subset the last UP swing ended on; when the cycle depth grows, the next UP swing resumes from here instead of repeating the steps already taken (valid only while the corresponding avail flag is set)
std::unique_ptr< SUBSET >	pivot_bottom
	the subset the last DOWN swing ended on, used the same way to resume a deeper DOWN swing without repeating steps
Protected Attributes inherited from FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >
PEvaluator	_evaluator
	the sequential-step evaluator injected at construction; drives Step()'s candidate generation and best/worst choice
DIMTYPE	_generalization_level
	number of features added/removed together in one Step() call (see set_generalization_level())
bool	_initial_subset_enabled
	by default all concrete search methods ignore the contents of supplied 'PSubset set' and initialize sub according to their definition; if enabled, then (if possible) the search() starts from supplied 'PSubset sub' contents
Protected Attributes inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
PResultTracker	_tracker
	the assigned result tracker, or null (see enable_result_tracking()/result_tracker_active())
OutputDetail	_detail
	the output detail level set via set_output_detail(); read by output_normal()/output_detailed()
PObserver	_observer
	the attached progress observer, or null (see set_observer(), report(), report_solution())

Additional Inherited Members
Protected Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	report (std::ostream &os, const msgbuf &m) const
	delivers one pre-formatted progress message: to the observer if attached, otherwise as syncout text to os
void	report_solution (std::ostream &os, const RETURNTYPE value, const SUBSET &sub, const msgbuf &m) const
	like report(), for sites announcing a new (sub-)solution; fires on_solution instead

Detailed Description

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>
class FST::Search_DOS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >

Implements Dynamic_Oscillating_Search.

Note: DOS is a purely d-optimizing procedure not permitting to specify target subset size, target_d is thus ignored.; By default sub is expected to be initialized prior to search() call, i.e., it should contain a valid initial subset of requested size from which the search will start. Empty initial subset is permitted. To ensure that any initial contents of sub are ignored and the search starts always from an empty set, call disable_initial_subset().

Warning: Non-empty init can not be used with Sequential_Step_Hybrid() parametrized _keep_perc==0 (due to initial filtercrit and crit values mix-up)

Examples: demo55.cpp.

Member Enumeration Documentation

◆ SwingPhase

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

enum FST::Search_DOS::SwingPhase

protected

Oscillating-cycle phase for the DOS swing state machine driving search()'s inline switch.

Structurally the same states as Search_OS's SwingPhase (RESTART/DOWN/ RETURN_UP/UP/RETURN_DOWN), but with one behavioral difference (marked "the DOS to OS difference" at each check site in the implementation): every Step() taken in DOWN/RETURN_UP/UP/RETURN_DOWN compares the new criterion value against the pivot immediately and jumps straight back to RESTART as soon as an improvement is found, instead of waiting for the swing to complete like Search_OS does. This eager restart-on-improvement is what makes DOS "dynamic": the oscillation depth effectively adapts as soon as a better solution turns up, and since DOS optimizes the cardinality too, an EQUAL criterion value counts as an improvement when it is reached with fewer features.

Member Function Documentation

◆ print()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

std::ostream & FST::Search_DOS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::print ( std::ostream & os ) const

overridevirtual

writes a human-readable identification of the search and its configuration; base default writes nothing

Reimplemented from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

◆ search()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class EVALUATOR>

bool FST::Search_DOS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::search	(	const DIMTYPE	target_d,
		RETURNTYPE &	result,
		const PSubset	sub,
		const PCriterion	crit,
		std::ostream &	os = std::cout )

overridevirtual

returns found subset + criterion value

Implements FST::Search_Sequential< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >.

Examples: demo55.cpp.

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

/Users/psms/dev/devtest1/_src_search/search_seq_dos.hpp

Public Types

Public Member Functions

Protected Types

Protected Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ SwingPhase

Member Function Documentation

◆ print()

◆ search()