AStar.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------------ File AStar.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_AStar
 #define __PBeFS_AStar
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/astar/Node.h"
 
#include "PBeFS/astar/NodeTable.h"
 
#include "PBeFS/astar/OpenList.h"
 
#include "PBeFS/core/SearchUtils.h"
 
#include "PBeFS/astar/Solution.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS AStar -------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D ,
          class Open = std::conditional_t<
           std::is_integral_v< cost_t< D > > ,
           BucketOpenList< Node< state_t< D > , cost_t< D > > > ,
           HeapOpenList< Node< state_t< D > , cost_t< D > > > > >
class AStar {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using NodeT = Node< State , Cost >;               
 using SolutionT = Solution< State , Cost >;       
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit AStar( const D & domain , const SearchOptions & options = {} )
  : f_domain( domain ) , f_options( options ) {}
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  Stopwatch clock;
  SolutionT sol;
  SearchStats & st = sol.stats;
  NodePool< NodeT > pool;
  NodeTable< NodeT > table( f_options.expected_nodes
                            ? NodeTable< NodeT >::slots_for(
                                               f_options.expected_nodes )
                            : 1024 );
  Open open;
  std::vector< Kid > kids;                 // the successors of a node
 
  const State s0 = f_domain.initial_state();
  NodeT * root = table.find_or_insert( s0 , f_domain.hash( s0 ) , [ & ] {
   NodeT * n = pool.allocate();
   *n = NodeT{ s0 , Cost( 0 ) , Cost( f_domain.heuristic( s0 ) ) , nullptr ,
               false , false };
   return( n );
   } ).first;
  open.push( root );
 
  while( ! open.empty() ) {
   const OpenEntry< NodeT > e = open.pop();
   if( e.stale() )
    continue;
 
   NodeT * n = e.node;
   n->closed = true;
   ++st.expanded;
   if( n->expanded )
    ++st.reexpanded;
   n->expanded = true;
 
   if( f_domain.is_goal( n->state ) ) {
    sol.status = Status::solved;
    sol.cost = n->g;
    sol.path = trace_path( n );
    break;
    }
 
   // first the successors, with the slots of their lookups prefetched,
   // then the lookups, whose cache misses thus overlap
   kids.clear();
   const auto kid = [ & ]( const State & t , Cost c , Cost ht ,
                           std::uint8_t op ) {
    const std::uint64_t hash = f_domain.hash( t );
    table.prefetch( hash );
    kids.push_back( Kid{ t , c , ht , hash , op } );
    };
   for_each_child( f_domain , n->state , n->h , n->op , kid );
   st.generated += kids.size();
   for( const Kid & k : kids ) {
    const Cost g = n->g + k.c;
    auto [ m , fresh ] = table.find_or_insert( k.s , k.hash , [ & ] {
     NodeT * x = pool.allocate();
     *x = NodeT{ k.s , g , k.h , n , false , false , k.op };
     return( x );
     } );
    if( fresh )
     open.push( m );
    else
     if( g < m->g ) {     // a cheaper path: reopen
      m->g = g;
      m->parent = n;
      m->op = k.op;
      m->closed = false;
      open.push( m );
      }
     else
      ++st.duplicates;
    }
 
   if( f_options.node_limit && ( pool.size() >= f_options.node_limit ) ) {
    sol.status = Status::node_limit;
    break;
    }
   }
 
  st.stored = pool.size();
  st.expanded_by = { st.expanded };
  st.stored_by = { st.stored };
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 struct Kid {
  State s;
  Cost c;
  Cost h;
  std::uint64_t hash;
  std::uint8_t op;
  };
 
 const D & f_domain;                                 
 SearchOptions f_options;                            
 
 };  // end( class( AStar ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > astar(
 const D & domain , OpenKind open = OpenKind::automatic ,
 const SearchOptions & options = {} )
{
 using NodeT = Node< state_t< D > , cost_t< D > >;
 if constexpr( std::is_integral_v< cost_t< D > > )
  if( open != OpenKind::heap )
   return( AStar< D , BucketOpenList< NodeT > >( domain , options ).solve()
           );
 return( AStar< D , HeapOpenList< NodeT > >( domain , options ).solve() );
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_AStar */
 
/*--------------------------------------------------------------------------*/
/*---------------------------- End File AStar.h ----------------------------*/
/*--------------------------------------------------------------------------*/