faif::search Namespace Reference

the namespace of searching algorithms and optimization algorithms More...

Classes
struct	BooleanGene
struct	compareWeight
	the comparizon used by searchUnifiedCost More...
struct	compareWeightAndHeuristic
	the comparizon used by AStar More...
struct	CrossoverCustom
	crossover policy - crossover from Space More...
struct	CrossoverNone
	crossover policy - no crossover More...
class	EvolutionaryAlgorithm
	the evolutionary algorithm More...
struct	EvolutionaryAlgorithmGeneConcept
	the concept for evolutionary algorithm gene the type gives the generateRandom method and the mutate method More...
struct	EvolutionaryAlgorithmSpace
	the typedef-s for space for evolutionary algorithm, where the population is a vector of individuals, and the fitness is the double More...
struct	EvolutionaryAlgorithmSpaceConcept
	the concept for evolutionary algorithm space More...
struct	EvolutionaryAlgorithmSpaceWithCrossoverConcept
	the concept for evolutionary algorithm space More...
struct	EvolutionaryAlgorithmSpaceWithMutationConcept
	the concept for evolutionary algorithm space More...
struct	ExpectationCustom
	expectation policy - custiom More...
class	ExpectationMaximization
	the Expectation-Maximization algorithm More...
struct	ExpectationNone
	expectation policy (empty) More...
class	HillClimbing
	the hill climbing algorithm. Search the neighbour for the better solution More...
struct	MaximizationCustom
	maximization policy - custiom More...
struct	MaximizationNone
	maximization policy (empty) n More...
struct	MutationCustom
	mutation policy - mutation from Space More...
struct	MutationNone
	mutation policy - no mutation More...
struct	NextNodeCheckAll
	the policy class for HillClimbing, check all neighbours More...
struct	Node
	the struct to create node in search space from individual More...
struct	NodeWithChildrenConcept
	the concept for node with children More...
struct	NodeWithFinalFlagConcept
	the concept for node with final flag for search in tree-like structures The function 'searchDepthFirst' and 'searchBreadthFirst' require this concept More...
struct	SelectionRanking
	succession and selection policy - the n-th best individuals survive More...
struct	SelectionRoulette
	succession and selection policy - roulette wheel (probability of selection of an idividual is equal to its normalized fitness) More...
struct	Space
	the typedef-s for space, where the fitness is defined as double More...
struct	SpaceConcept
	the concept for space with fitness More...
struct	StopAfterNSteps
	Stop condition, finish the algorithm after STEPS_NUM iterations. More...
struct	TransformationCustomTag
	trait tag, user tranformation should be executed More...
struct	TransformationNoneTag
	trait tag, no transformation should be executed More...
class	TreeNode
	the template to create the node in tree-based search methods More...
struct	TreeNodeHeuristicConcept
	the concept for heuristic search algorithms, it check the presence of 'getHeuristic' method, used by heuristic search functions e.g. 'searchAStar' More...
struct	TreeNodeWeightConcept
	the concept for informed search algorithms, it check the presence of 'getWeight' method, used by informed search functions e.g. 'searchUniformCost' More...
class	VectorIndividual
	Template to generate individual which is the vector of Genes. More...
class	VoseAlg
	helping class implemented the M.D.Vose (1991) algorithm More...

Functions
template<typename T >
Node< T >::Path	searchAStar (boost::shared_ptr< T > start, int max=200)
	A* (A star) search algorithm. More...
template<typename T >
Node< T >::Path	searchBreadthFirst (boost::shared_ptr< T > start, int max=200)
	The breadth-first search algorithm. More...
template<typename T >
Node< T >::Path	searchDepthFirst (boost::shared_ptr< T > start, int max=200)
	The depth-first search algorithm (DFS) More...
template<typename Node >
std::ostream &	operator<< (std::ostream &os, const std::vector< boost::shared_ptr< Node > > &path)
	helping function for debugging More...
template<typename T >
bool	checkNodeInPath (const TreeNode< T > &n)
template<typename T >
Node< T >::Path	searchUnifiedCost (boost::shared_ptr< T > start, int max=200)
	uniform-cost search algorithm (informed search) More...

Detailed Description

the namespace of searching algorithms and optimization algorithms

Function Documentation

template<typename T >

Node<T>::Path faif::search::searchAStar	(	boost::shared_ptr< T >	start,
		int	max = 200
	)

A* (A star) search algorithm.

heuristic searching tree-like structures, finds the least-cost path from initial node to goal node, uses a distance function which is a sum of path-cost and a heuristic estimate of the distance to the goal

Function is protected against the cycles in the graph. The maximum depth of tree is limited.

References checkNodeInPath(), faif::search::TreeNode< T >::generatePathToRoot(), faif::search::TreeNode< T >::getChildrenWithWeight(), faif::search::TreeNode< T >::getLevel(), and faif::search::TreeNode< T >::getPoint().

template<typename T >

Node<T>::Path faif::search::searchBreadthFirst	(	boost::shared_ptr< T >	start,
		int	max = 200
	)

The breadth-first search algorithm.

from starting state the function build the tree structure, explores all the nearest nodes (children), and if it not find the goal generates the nearest nodes to the children. The return is the shortest path from root node to the goal node. Function is protected against the cycles in the graph. The maximum depth of tree is limited.

References checkNodeInPath(), faif::search::TreeNode< T >::generatePathToRoot(), faif::search::TreeNode< T >::getChildren(), faif::search::TreeNode< T >::getLevel(), faif::search::TreeNode< T >::getPoint(), and searchBreadthFirst().

Referenced by searchBreadthFirst().

template<typename T >

Node<T>::Path faif::search::searchDepthFirst	(	boost::shared_ptr< T >	start,
		int	max = 200
	)

The depth-first search algorithm (DFS)

from starting state the function build the tree structure, explores as far as possible, backtracks. Function uses the protection against the cycles in the graph and the maximum depth of tree border.

Returns

the first path from the starting to the finishing state.

References checkNodeInPath(), faif::search::TreeNode< T >::generatePathToRoot(), faif::search::TreeNode< T >::getChildren(), faif::search::TreeNode< T >::getLevel(), and faif::search::TreeNode< T >::getPoint().

template<typename Node >

std::ostream& faif::search::operator<< ( std::ostream &  os, const std::vector< boost::shared_ptr< Node > > &  path  )

inline

helping function for debugging

template<typename T >

bool faif::search::checkNodeInPath

(

const TreeNode< T > &

n

)

check if the node is twice on the path

References faif::search::TreeNode< T >::getParent(), and faif::search::TreeNode< T >::getPoint().

Referenced by searchAStar(), searchBreadthFirst(), searchDepthFirst(), and searchUnifiedCost().

template<typename T >

Node<T>::Path faif::search::searchUnifiedCost	(	boost::shared_ptr< T >	start,
		int	max = 200
	)

uniform-cost search algorithm (informed search)

the uniform-cost search algorithm, traversing a tree structure, visit the next node which has the least total cost from the root. Algorithm use the 'getWeight' function of node.

Function is protected against the cycles in the graph. The maximum depth of tree is limited.

References checkNodeInPath(), faif::search::TreeNode< T >::generatePathToRoot(), faif::search::TreeNode< T >::getChildrenWithWeight(), faif::search::TreeNode< T >::getLevel(), and faif::search::TreeNode< T >::getPoint().