faif
Classes | Functions
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)
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().