rules.cc

基于学习的深度优先搜索算法

}

inline bool
graph_t::entry_t::revise( hash_t &hash, qvalue_func_t qvalue )
{
  if( s_.terminal() )
    {
      hash.update( s_, s_.terminal_value() );
      hash.mark( s_ );
      fringe_ = false;
      return( true );
    }
  else
    {
      double old_value = hash.value( s_ );
      std::pair<double,const rule_t*> p = hash.bestAction( s_, qvalue );
      hash.update( s_, p.first );
      mark( p.second );

      bool solved = true;
      const rule_body_t &body = p.second->body(); 
      for( rule_body_t::const_iterator bi = body.begin(); solved && (bi != body.end()); ++bi )
        {
          state_t s_next( *bi );
          solved = hash.solved( s_next );
        }

      if( solved )
        {
          hash.mark( s_ );
          fringe_ = false;
        }
      return( solved || (p.first > old_value) );
    }
}

inline graph_t::entry_t*
graph_t::add_tip( entry_t *parent, const rule_t *rule,  unsigned target, const state_t &child )
{
  std::map<state_t,entry_t*>::iterator ni = nodes_.find( child );
  if( ni != nodes_.end() )
    {
      (*ni).second->add_parent( parent );
      return( (*ni).second );
    }
  else
    {
      entry_t *e = new entry_t( child );
      if( parent ) e->add_parent( parent );
      nodes_.insert( std::make_pair( child, e ) );
      tips_.insert( e );
      return( e );
    }
}

inline void
graph_t::expand( entry_t &n, std::multiset<entry_t*,entry_t> &S )
{
  const rule_list_t &rules = rule_system->rules( n.s().atom() );
  for( rule_list_t::const_iterator ri = rules.begin(); ri != rules.end(); ++ri )
    {
      for( rule_body_t::const_iterator bi = (*ri)->body().begin(); bi != (*ri)->body().end(); ++bi )
        {
          state_t s_next( *bi );
          add_tip( &n, *ri, *bi, s_next );
        }
    }
}

void
graph_t::expand_and_update( entry_t &n, hash_t &hash, qvalue_func_t qvalue )
{
  std::multiset<entry_t*,entry_t> S;

  // expand node n: Steps 6 and 7 from Nilsson's
  assert( n.fringe() && !hash.solved( n.s() ) );
  assert( nodes_.find( n.s() ) != nodes_.end() );
  n.set_fringe( false );
  if( n.s().terminal() )
    {
      hash.update( n.s(), n.s().terminal_value() );
      hash.mark( n.s() );
    }
  else
    {
      ++expansions;
      expand( n, S );
    }
  S.insert( &n );
  n.visit();

  // iterate over S: Step 10 from Nilsson's
  //std::cout << "begin" << std::endl;
  while( !S.empty() )
    {
      entry_t *e = *S.begin();
      S.erase( e );
      e->unvisit();
      //std::cout << "  e=" << e->s() << ", index=" << e->index() << std::endl;
      assert( e->index() == 0 );

      // backprop: Step 11 from Nilsson's
      bool change = e->revise( hash, qvalue );
      if( change )
        {
          // update parents: Step 12 from Nilsson's
          for( std::set<entry_t*>::const_iterator pi = e->parents().begin(); pi != e->parents().end(); ++pi )
            {
              //std::cout << "    parent=" << (*pi)->s() << std::endl;
              bool found = false;
              size_t index = 0;
              const rule_t *r = (*pi)->marked();
              assert( r != 0 );
              const rule_body_t &body = r->body();
              //std::cout << "      body: ";
              for( rule_body_t::const_iterator bi = body.begin(); bi != body.end(); ++bi )
                {
                  //std::cout << *bi << " ";
                  state_t p( *bi );
                  if( p == e->s() ) found = true;
                  std::map<state_t,entry_t*>::const_iterator it = nodes_.find( p );
                  if( (it != nodes_.end()) && (*it).second->visited() ) ++index;
                }
              //std::cout << std::endl;

              if( found && (*pi)->visited() )
                {
                  S.erase( *pi );
                  (*pi)->dec_index();
                  S.insert( *pi );
                  //std::cout << "    inserting " << (*pi)->s() << ", index=" << (*pi)->index() << std::endl;
                }
              else if( found )
                {
                  (*pi)->set_index( index );
                  S.insert( *pi );
                  //std::cout << "    inserting " << (*pi)->s() << ", index=" << (*pi)->index() << std::endl;
                }
            }
        }
    }
  assert( S.empty() );
  //std::cout << "done" << std::endl << std::endl;

  // compute best partial solution graph: Step 4 from Nilsson's
  tips_.clear();
  if( !hash.solved( root_->s() ) )
    {
      std::list<entry_t*> stack;
      stack.push_front( root_ );
      while( !stack.empty() )
        {
          entry_t *e = stack.front();
          stack.pop_front();
	  e->visit();
          assert( !hash.solved( e->s() ) );
          assert( e->fringe() || (e->marked() != 0) );

          if( e->fringe() )
            tips_.insert( e );
          else
            {
              bool solved = true;
              const rule_t *r = e->marked();
              const rule_body_t &body = r->body();
              for( rule_body_t::const_iterator bi = body.begin(); bi != body.end(); ++bi )
                {
                  state_t s_next( *bi );
                  if( !hash.solved( s_next ) )
                    {
                      solved = false;
                      std::map<state_t,entry_t*>::iterator ni = nodes_.find( s_next );
                      assert( ni != nodes_.end() );
                      if( !(*ni).second->visited() ) stack.push_front( (*ni).second );
                    }
                }
              if( solved ) { e->set_fringe( true ); tips_.insert( e ); }
            }
          if( tips_.size() > 0 ) break;
        }
    }
  assert( hash.solved( root_->s() ) || (tips_.size() > 0) );

  // clean visited flags
  for( std::map<state_t,entry_t*>::iterator ni = nodes_.begin(); ni != nodes_.end(); ++ni )
    (*ni).second->unvisit();
}

bool
ldfsBound( int depth, hash_t &hash, const state_t s, double bound, qvalue_func_t qvalue )
{
  if( verbose ) { indent( std::cout, depth ); std::cout << s << ", lower=" << hash.value(s) << ", upper=" << hash.upper(s) << ", bound=" << bound << std::endl; }
  //if( hash.upper( s ) <= bound ) return( true );
  //if( s.terminal() || (hash.value(s) == hash.upper(s)) )
  if( s.terminal() || (hash.upper(s) <= bound) )
    {
      if( (verbose ) && !hash.solved(s) )
        {
          indent( std::cout, depth );
          std::cout << "terminal=" << s.terminal_value() << std::endl;
        }
      if( s.terminal() )
        {
          hash.update( s, s.terminal_value() );
          hash.update_upper( s, s.terminal_value() );
        }
      return( true );
    }

  ++expansions;
  bool flag = false;
  assert( hash.value( s ) <= bound );
  const rule_list_t &rules = rule_system->rules( s.atom() );
  rule_list_t::const_iterator ri;
  for( ri = rules.begin(); ri != rules.end(); ++ri )
    {
      double qv = (hash.*qvalue)( s, **ri );
      if( qv > bound ) continue;
      flag = true;
      const rule_body_t &body = (*ri)->body();
      for( rule_body_t::const_iterator bi = body.begin(); bi != body.end(); ++bi )
        { 
          double nbound = bound - 1;
          if( qvalue == &hash_t::QValueAdd )
            {
              for( rule_body_t::const_iterator xi = body.begin(); xi != body.end(); ++xi )
                if( xi != bi ) nbound -= hash.value( state_t( *xi ) );
            }
          flag = ldfsBound( 1+depth, hash, state_t( *bi ), nbound, qvalue );
          if( flag )
            {
              double qv = (hash.*qvalue)( s, **ri );
	      flag = (qv <= bound);
            }
          if( !flag ) break;
        }
      if( flag ) break;
    }

  if( flag )
    {
      hash.update_upper( s, bound );
      if( verbose )
        {
          indent( std::cout, depth );
          std::cout << "upper=" << bound << std::endl;
        }
    }
  else
    {
      double bqv = hash.bestQValue( s, qvalue );
      assert( bqv > hash.value( s ) );
      hash.update( s, bqv );
      if( verbose )
        {
          indent( std::cout, depth );
          std::cout << s << ", lower=" << bqv << std::endl;
        }
    }
  return( flag );
}

size_t
ldfsBoundDriver( hash_t &hash, const state_t s, qvalue_func_t qvalue )
{
  expansions = 0;
  size_t iterations = 0;
  while( hash.value( s ) < hash.upper( s ) )
    {
      ++iterations;
      ldfsBound( 0, hash, s, hash.value( s ), qvalue );
      if( verbose ) std::cout << "V(s0)=" << hash.value(s) << std::endl;
    }
  return( iterations );
}

bool
ldfs( size_t depth, hash_t &hash, const state_t s, qvalue_func_t qvalue )
{
  if( verbose ) { indent( std::cout, depth ); std::cout << s << std::endl; }
  if( s.terminal() || hash.solved(s) )
    {
      if( (verbose ) && !hash.solved(s) )
        {
          indent( std::cout, depth );
          std::cout << "terminal=" << s.terminal_value() << std::endl;
        }
      if( s.terminal() ) hash.update( s, s.terminal_value() );
      hash.mark( s );
      return( true );
    }

  ++expansions;
  bool flag = false;
  double bound = hash.value( s );
  const rule_list_t &rules = rule_system->rules( s.atom() );
  for( rule_list_t::const_iterator ri = rules.begin(); ri != rules.end(); ++ri )
    {
      double qv = (hash.*qvalue)( s, **ri );
      if( qv > bound ) continue;
      flag = true;
      const rule_body_t &body = (*ri)->body();
      for( rule_body_t::const_iterator bi = body.begin(); bi != body.end(); ++bi )
        { 
          flag = ldfs( 1+depth, hash, state_t( *bi ), qvalue );
          if( flag )
            {
              double qv = (hash.*qvalue)( s, **ri );
              flag = (qv <= bound);
            }
          if( !flag ) break;
        }
      if( flag ) break;
    }

  if( flag )
    {
      hash.mark( s );
      if( verbose )
        {
          indent( std::cout, depth );
          std::cout << "mark " << s << " with " << hash.value(s) << std::endl;
        }
    }
  else
    {
      double bqv = hash.bestQValue( s, qvalue );
      assert( (qvalue != &hash_t::QValueAdd) || (bqv > hash.value(s)) );
      hash.update( s, bqv );
      if( verbose )
        {
          indent( std::cout, depth );
          std::cout << s << ", update=" << bqv << std::endl;
        }
    }
  return( flag );
}

size_t
ldfsDriver( hash_t &hash, const state_t s, qvalue_func_t qvalue )
{
  expansions = 0;
  size_t iterations = 0;
  while( !hash.solved( s ) )
    {
      ++iterations;
      ldfs( 0, hash, s, qvalue );
      if( verbose ) std::cout << "V(s0)=" << hash.value(s) << std::endl;
    }
  return( iterations );
}

size_t
valueIteration( hash_t &hash, const state_t s0, qvalue_func_t qvalue )
{
  double residual = 1;
  size_t iterations = 0;
  while( residual > 0 )
    {
      residual = 0;
      for( atom_t p = 0; p < rule_system->num_atoms(); ++p )
        {
          state_t s( p );
          if( !s.terminal() )
            {
              double value = hash.value( s );
              double bqv = hash.bestQValue( s, qvalue );
              residual = MAX(residual,bqv-value);
              hash.update( s, bqv );
            }
          else
            hash.update( s, s.terminal_value() );
        }
      ++iterations;
    }
  return( iterations );
}

size_t
aostar( hash_t &hash, const state_t s, qvalue_func_t qvalue )
{
  graph_t graph;
  expansions = 0;

  if( s.terminal() )
    {
      hash.update( s, s.terminal_value() );
      hash.mark( s );
    }
  graph_t::entry_t *root = graph.add_tip( 0, 0, UINT_MAX, s );
  graph.set_root( root );

  size_t iterations = 0;
  while( !hash.solved( s ) )
    {
      if( verbose ) std::cout << "V(s0)=" << hash.value( s ) << std::endl;
      assert( graph.tips().size() != 0 );
      graph_t::entry_t &n = graph.choose_tip();
      graph.expand_and_update( n, hash, qvalue );
      ++iterations;
    }
  return( iterations );
}

bool
checksolved( hash_t::data_pair e, hash_t &hash, qvalue_func_t qvalue )
{
  static std::set<hashing::entry_t*> aux;
  static std::list<hash_t::data_pair> queue;
  static std::list<hash_t::data_pair> stack;

  assert( queue.empty() && stack.empty() );