Implements Sequential_Forward_Retreating_Search and Sequential_Backward_Retreating_Search. More...

#include <search_seq_sfrs.hpp>

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

Classes
struct	OneSubset
	Structure to hold [subset,criterion value] temporary solutions in the course of search. More...

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_SFRS (const PEvaluator evaluator)
	`evaluator` must be non-null; direction defaults to FORWARD (SFRS); call set_search_direction(BACKWARD) for SBRS
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_search_direction (const SearchDirection direction)
	FORWARD selects SFRS, BACKWARD selects SBRS (do not change concurrently to running search()).
SearchDirection	get_search_direction () const
	the currently configured direction (see set_search_direction())
void	set_delta (const DIMTYPE delta)
	optional bound on how far the search's OWN direction advances the frontier: SFRS stops adding features at target_d+delta, SBRS stops removing them at target_d-delta (0 = unrestricted). The retreat in the opposite direction is unconditional and always runs to the hard 1.._n bound, delta or not. No effect when target_d==0 (best-dimensionality search)
DIMTYPE	get_delta () const
	the currently configured delta bound (see set_delta())
bool	get_result (const DIMTYPE d, RETURNTYPE &result, PSubset &sub)
	retrieves temporary solution of cardinality d that had been updated in the course of the last search (if it exists)
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 Attributes
SearchDirection	_direction
DIMTYPE	_delta
	frontier restriction around target_d (0 = unrestricted); see set_delta()
std::unique_ptr< OneSubset[]>	bsubs
	per-cardinality best-known result found in the course of the last search() (index d-1); read by get_result()
DIMTYPE	_n
	bsubs array size
std::unique_ptr< SUBSET >	pivotsub
	the subset the next advance continues from: the last subset that became the overall best during the retreat. NOTE the name means something else in Search_DOS, where "pivot" denotes the best-so-far subset - that one is called maxcritsub here
std::unique_ptr< SUBSET >	maxcritsub
	stores the subset with maximum known crit value
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_SFRS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >

Implements Sequential_Forward_Retreating_Search and Sequential_Backward_Retreating_Search.

Note: By default any initial subset contents are ignored; SFRS starts from empty set and SBRS starts from full set. Call enable_initial_subset() to let the search start from the initial sub contents.; SFRS is closely related to SFFS, but is more thorough, slower, possibly more suitable if result regularization is to be eventually applied (selection of alternative solution based on secondary criterion), because SFRS evaluates more candidate subsets than SFFS. Concretely, it differs from Search_SFFS in two points: the retreating (backtracking) phase is UNCONDITIONAL, i.e. it always retreats all the way to the opposite cardinality bound instead of stopping at the first non-improving step, and the subset the next advance continues from is updated only on a new overall best, not on every per-cardinality improvement.; Among subsets of EQUAL criterion value the search prefers the SMALLER one, both when updating the best-so-far used for the target_d==0 (optimize cardinality) answer and, implicitly, in that a per-cardinality record is only replaced by a strictly better value.

Examples: demo52t.cpp.

Member Function Documentation

◆ print()

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

std::ostream & FST::Search_SFRS< 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_SFRS< 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: demo52t.cpp.

Member Data Documentation

◆ _direction

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

SearchDirection FST::Search_SFRS< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, EVALUATOR >::_direction

protected

accepted values FORWARD for SFRS or BACKWARD for SBRS

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

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

Classes

Public Types

Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ print()

◆ search()

Member Data Documentation

◆ _direction