IDAStar.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*----------------------------- File IDAStar.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_IDAStar
 #define __PBeFS_IDAStar
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cstddef>
 
#include <cstdint>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/astar/Node.h"
 
#include "PBeFS/core/SearchUtils.h"
 
#include "PBeFS/astar/Solution.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS IDAStar ------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D >
class IDAStar {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using SolutionT = Solution< State , Cost >;       
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit IDAStar( const D & domain , const SearchOptions & options = {} )
  : f_domain( domain ) , f_options( options ) {}
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  Stopwatch clock;
  Run r( f_domain , f_options.node_limit );
  const State s0 = f_domain.initial_state();
  const Cost h0 = f_domain.heuristic( s0 );
  r.path.push_back( s0 );
  Cost bound = h0;
  SolutionT sol;
  for( ; ; ) {
   r.next = infinite_cost< Cost >();
   if( r.dfs( s0 , Cost( 0 ) , h0 , no_op , bound ) ) {
    sol.status = Status::solved;
    sol.cost = r.cost;
    sol.path = r.path;
    break;
    }
   if( r.stop ) {
    sol.status = Status::node_limit;
    break;
    }
   if( r.next == infinite_cost< Cost >() ) {
    sol.status = Status::unsolvable;
    break;
    }
   bound = r.next;
   }
  r.st.expanded_by = { r.st.expanded };
  r.st.stored_by = { r.st.stored };
  r.st.seconds = clock.seconds();
  sol.stats = std::move( r.st );
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 struct Run {
 
  const D & d;                                    
  std::size_t limit;                              
  std::vector< State > path;                      
  Cost next{};                                    
  Cost cost{};                                    
  bool stop = false;                              
  SearchStats st;                                 
 
  Run( const D & domain , std::size_t node_limit )
   : d( domain ) , limit( node_limit ) {}
 
  // the depth-first search below u, of cost g and heuristic h with
  // g + h within the bound, generated by the operator op; true if a goal is
  // found, the path then ending at it
  bool dfs( const State & u , Cost g , Cost h , std::uint8_t op ,
            Cost bound ) {
   if( d.is_goal( u ) ) {
    cost = g;
    return( true );
    }
   if( limit && ( st.expanded >= limit ) ) {
    stop = true;
    return( false );
    }
   ++st.expanded;
   bool found = false;
   const auto child = [ & ]( const State & v , Cost c , Cost hv ,
                             std::uint8_t opv ) {
    ++st.generated;
    if( g + c + hv > bound ) {                   // cut: a candidate bound
     next = std::min( next , g + c + hv );
     return;
     }
    path.push_back( v );
    st.stored = std::max< std::uint64_t >( st.stored , path.size() );
    if( dfs( v , g + c , hv , opv , bound ) )
     found = true;
    else
     path.pop_back();
    };
   if constexpr( OperatorDomain< D > )
    d.for_each_successor( u , h , op , [ & ]( const State & v , Cost c ,
                                              Cost hv , std::uint8_t opv ) {
     if( ! found && ! stop )
      child( v , c , hv , opv );
     } );
   else
    d.for_each_successor( u , h , [ & ]( const State & v , Cost c ,
                                         Cost hv ) {
     if( found || stop )
      return;
     if( ( path.size() >= 2 ) && ( v == path[ path.size() - 2 ] ) ) {
      ++st.generated;                            // back to the parent
      return;
      }
     child( v , c , hv , no_op );
     } );
   return( found );
   }
 
  };  // end( struct( Run ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const D & f_domain;                                 
 SearchOptions f_options;                            
 
 };  // end( class( IDAStar ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
template< Domain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > idastar(
 const D & domain , const SearchOptions & options = {} )
{
 return( IDAStar< D >( domain , options ).solve() );
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_IDAStar */
 
/*--------------------------------------------------------------------------*/
/*--------------------------- End File IDAStar.h ---------------------------*/
/*--------------------------------------------------------------------------*/