#include <GeneralizedAStar.h>
Classes | |
| struct | Node |
Public Member Functions | |
| GeneralizedAStar (const S &start) | |
| void | SetStart (const S &start) |
| Resets the search from the given start state. | |
| bool | Search () |
| Performs search until a goal is reached. | |
| bool | SearchStep () |
| Performs a single iteration of search. | |
| bool | SearchFailed () |
| Returns true if search failed. | |
| int | NumNodes () const |
| Returns the number of nodes in the tree. | |
| int | NumExpanded () const |
| Returns the number of previously expanded nodes. | |
| int | NumDescendents (const Node &n) const |
| Returns the number of descendents of n. | |
| C | TopPriority () const |
| Returns the priority of the next node to be expanded. | |
| bool | GoalFound () const |
| Returns true if the goal has been found. | |
| C | GoalCost () const |
| const std::vector< S > & | GoalPath () const |
| Returns path of states to the goal. | |
| virtual bool | IsGoal (const S &s)=0 |
| The following must be overloaded by the subclass. | |
| virtual void | Successors (const S &s, std::vector< S > &successors, std::vector< C > &costs)=0 |
| virtual C | Heuristic (const S &s) |
| virtual void | ClearVisited () |
| virtual void | Visit (const S &s, Node *n) |
| virtual Node * | VisitedStateNode (const S &s) |
| virtual bool | OnExpand (Node *n) |
Public Attributes | |
| bool | testGoalOnGeneration |
| C | zero |
| Node | root |
| The A* search tree. | |
| IndexedPriorityQueue< Node *, std::pair< C, C > > | fringe |
| std::vector< S > | successors |
| Temporary variables – slightly reduces the number of memory allocations. | |
| std::vector< C > | costs |
| int | numNodes |
| Node * | goal |
| Upon successful termination, goal contains the goal node. | |
| std::vector< S > | path |
| Upon successful termination, path contains the path from start to goal. | |
Detailed Description
template<class S, class C>
struct AI::GeneralizedAStar< S, C >
This class is a generalization of AStar that allows for non-scalar costs.
The user of this class should subclass it and overload, at the minimum, IsGoal() and Successors().
To perform visited state detection (usually recommended), the user should implement ClearVisited(), Visit(), and VisitedStateNode(). The convenience classes GeneralizedAStarWithMap and GeneralizedAStarWithHashMap provide simple implementations of the visited state detection routines.
To run the search, first call SetStart(), and then call Search(). Alternatively, to get more control, you can run SearchStep() until true is returned (in which case a solution was found), or SearchFailed() returns true (no solution exists).
The cost C class is required to implement an ordering '<', equality testing '=', unary negation '-', and accumulation '+'. The default constructor is required to return an identity element '0' such that x+'0' = x.
ints, floats, and doubles are fine for the cost class, but you can also implement more sophisticated costs, such as multi-objective costs.
Member Function Documentation
|
inlinevirtual |
Optionally, overload these functions. If not overloaded, does no visited test
Reimplemented in OptimalSubsetAStar2, OptimalSubsetAStar, GreedySubsetAStar2, GreedySubsetAStar, FMTAStar, AI::GeneralizedAStarWithHashMap< S, C >, and AI::GeneralizedAStarWithMap< S, C >.
Referenced by AI::GeneralizedAStar< S, C >::SetStart().
|
inline |
Returns cost from the start to the goal. Note: only works with testGoalOnGeneration=false
|
inlinevirtual |
Optionally, overload this callback to get feedback about how the search is proceeding. If false is returned, search under this node is pruned.
Referenced by AI::GeneralizedAStar< S, C >::SearchStep().
Member Data Documentation
| IndexedPriorityQueue<Node*,std::pair<C,C> > AI::GeneralizedAStar< S, C >::fringe |
The A* search fringe. Requires a pair for the key value, because if two items have the same f value, then the one with the greatest g is picked
Referenced by AI::GeneralizedAStar< S, C >::NumExpanded(), AI::GeneralizedAStar< S, C >::Search(), AI::GeneralizedAStar< S, C >::SearchFailed(), AI::GeneralizedAStar< S, C >::SearchStep(), AI::GeneralizedAStar< S, C >::SetStart(), and AI::GeneralizedAStar< S, C >::TopPriority().
| bool AI::GeneralizedAStar< S, C >::testGoalOnGeneration |
By default false. This can be set to true, in which case the search may return a suboptimal solution (but faster)
Referenced by AI::GeneralizedAStarWithHashMap< S, C >::ClearVisited(), AI::GeneralizedAStar< S, C >::SearchStep(), and AI::GeneralizedAStar< S, C >::SetStart().
| C AI::GeneralizedAStar< S, C >::zero |
The zero element of type C. By default this is uninitialized! Be careful if you are using plain old data types (int, float, double)
Referenced by AI::GeneralizedAStar< int, SubsetCost >::GoalCost(), AI::GeneralizedAStar< int, SubsetCost >::GoalPath(), AI::GeneralizedAStar< S, C >::SetStart(), and AI::GeneralizedAStar< S, C >::TopPriority().
The documentation for this struct was generated from the following file:
