FAIF - search

The search namespace contains the function of space search

Fast start

The examples uses the Simple class which represents the node and is able to generate the children, and is able to check if it is the final node.

    /** class to test searching method

        1---------------------
        |                     \
        2                      3
        | \                    |\
        4  5                   6 7
        |\  \
        8 9  10 (FINAL)

    */
    class SimpleTree : public Node {
    public:
        static const int MAX_N = 10;

        SimpleTree(int n = 1) : n_(n) {}
        ~SimpleTree() {}

        bool operator==(const SimpleTree& t) const { return n_ == t.n_; }
        bool operator!=(const SimpleTree& t) const { return n_ != t.n_; }

        bool isFinal() const { return n_ == MAX_N; }

        int getN() const { return n_; }

        vector > getChildren() {
            Children children;
            if(2*n_ <= MAX_N)
                children.push_back( PNode(new SimpleTree(2*n_) ) );
            if(2*n_ + 1 <= MAX_N)
                children.push_back( PNode(new SimpleTree(2*n_ + 1) ) );
            return children;
        }
        /** method required by informed search algorithms (AStar, UnifiedCost) */
        double getWeight() const { return 1.0; }
        /** method required by heuristic search algorithms (AStar) */
        double getHeuristic() const { return 1.0; }
    private:
        int n_;
    };

Depth-first search on tree-like structures:

#include <faif/search/DepthFirst.h>

SimpleTree::PNode root(new SimpleTree() );
SimpleTree::Path p = searchDepthFirst( root );
//p is the path of nodes: 10-5-2-1

Breadth-first search :

#include <faif/search/BreadthFirst.h>

SimpleTree::PNode root(new SimpleTree() );
SimpleTree::Path p = searchBreadthFirst( root );
//p is the path of nodes: 10-5-2-1

Unified-cost search :

#include <faif/search/UnifiedCost.h>
SimpleTree::PNode root(new SimpleTree() );
SimpleTree::Path p = searchUnifiedCost( root );
//p is the path of nodes: 10-5-2-1

A star search:

#include <faif/search/AStar.h>
SimpleTree::PNode root(new SimpleTree() );
SimpleTree::Path p = searchAStar( root );
//p is the path of nodes: 10-5-2-1

return to the main page