00001
00002 /***************************************************************************
00003  *  astar.h - Implementation of A*
00004  *
00005  *  Generated: Mon Sep 15 18:39:00 2002
00006  *  Copyright  2002-2007  Stefan Jacobs, Martin Liebenberg
00007  *
00008  ****************************************************************************/
00009
00010 /*  This program is free software; you can redistribute it and/or modify
00011  *  it under the terms of the GNU General Public License as published by
00012  *  the Free Software Foundation; either version 2 of the License, or
00013  *  (at your option) any later version. A runtime exception applies to
00014  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00015  *
00016  *  This program is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  *  GNU Library General Public License for more details.
00020  *
00021  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00022  */
00023
00024 #ifndef _ABSTRACT_ASTAR_H_
00025 #define _ABSTRACT_ASTAR_H_
00026 
00027 #include <utils/search/astar_state.h>
00028
00029 #include <vector>
00030 #include <map>
00031 #include <queue>
00032
00033 namespace fawkes {
00034
00035
00036 class AStar
00037 {
00038  public:
00039   AStar ();
00040   ~AStar();
00041
00042   std::vector< AStarState * > solve( AStarState * initialState );
00043
00044  private:
00045
00046   struct Cmp {
00047     bool operator() ( AStarState * a1, AStarState * a2 ) const
00048     { return (a1->totalEstimatedCost >= a2->totalEstimatedCost); }
00049   };
00050
00051   std::priority_queue< AStarState *, std::vector< AStarState * >, Cmp > openList;
00052   std::map< const long, AStarState*> closedList;
00053
00054   AStarState * search();
00055
00056   std::vector< AStarState * > getSolutionSequence( AStarState * node );
00057   std::vector< AStarState * > solution;
00058
00059 };
00060
00061
00062 } // end namespace fawkes
00063
00064 #endif