diagnosis.cc

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

    }
  end:;
  if( verbose ) std::cerr << "updates=" << hash_->updates() << ", iters=" << i << std::endl;
}

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
    {
      unsigned old_value = hash.value( s_ );
      std::pair<unsigned,size_t> p = hash.bestAction( s_, qvalue );
      hash.update( s_, p.first );
      mark( p.second );

      bool solved = true;
      if( p.second < UINT_MAX )
        {
          assert( s_.available_test( p.second ) );
          for( size_t obs = 0; solved && (obs < 2); ++obs )
            {
              state_t s_obs = s_.next_state( p.second, obs, *test_matrix );
              solved = hash.solved( s_obs );
            }

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

inline graph_t::entry_t*
graph_t::add_tip( entry_t *parent, size_t test, size_t obs, 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 bool
graph_t::expand( entry_t &n, std::multiset<entry_t*,entry_t> &S )
{
  bool found = false;
  for( size_t test = 0; test < state_t::max_tests(); ++test )
    if( n.s().available_test( test ) )
      {
        found = true;
        for( size_t obs = 0; obs < 2; ++obs )
          {
            state_t s_obs = n.s().next_state( test, obs, *test_matrix );
            add_tip( &n, test, obs, s_obs );
          }
      }
  return( found );
}

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;
      if( !expand( n, S ) )
        {
          hash.update( n.s(), UMAX );
          hash.mark( 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;
              size_t test = (*pi)->marked();
              assert( test != UINT_MAX );
              assert( (*pi)->s().available_test( test ) );
              for( size_t obs = 0; obs < 2; ++obs )
                {
                  state_t s_obs = (*pi)->s().next_state( test, obs, *test_matrix );
                  if( s_obs == e->s() ) found = true;
                  std::map<state_t,entry_t*>::const_iterator it = nodes_.find( s_obs );
                  if( (it != nodes_.end()) && (*it).second->visited() ) ++index;
                }

              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() ) );

          if( e->fringe() )
            tips_.insert( e );
          else if( e->marked() != UINT_MAX )
            {
              bool solved = true;
              size_t test = e->marked();
              assert( e->s().available_test( test ) );
              for( size_t obs = 0; obs < 2; ++obs )
                {
                  state_t s_obs = e->s().next_state( test, obs, *test_matrix );
                  if( !hash.solved( s_obs ) )
                    {
                      solved = false;
                      std::map<state_t,entry_t*>::iterator ni = nodes_.find( s_obs );
                      assert( ni != nodes_.end() );
                      if( !(*ni).second->visited() ) stack.push_front( (*ni).second );
                    }
                }
              if( solved ) { e->set_fringe( true ); tips_.insert( e ); }
            }
          else
            {
              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, unsigned bound, qvalue_func_t qvalue )
{
  if( verbose ) { indent( std::cout, depth ); std::cout << s << std::endl; }
  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() );
      return( true );
    }

  ++expansions;
  bool flag = false;
  assert( hash.value( s ) <= bound );
  for( size_t test = 0; test < state_t::max_tests(); ++test )
    if( s.available_test( test ) )
      {
        unsigned qv = (hash.*qvalue)( s, test );
        if( qv > bound ) continue;
        flag = true;
        for( size_t obs = 0; obs < 2; ++obs )
          { 
            state_t s_obs = s.next_state( test, obs, *test_matrix );
            unsigned nbound = bound - 1;
            if( qvalue == &hash_t::QValueAdd )
              {
                state_t s_tmp = s.next_state( test, 1-obs, *test_matrix );
                nbound -= hash.value( s_tmp );
              }
            flag = ldfsBound( 1+depth, hash, s_obs, nbound, qvalue );
            if( flag )
              {
                unsigned qv = (hash.*qvalue)( s, test );
                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
    {
      unsigned bqv = hash.bestQValue( s, qvalue );
      assert( 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
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;
  unsigned bound = hash.value( s );
  for( size_t test = 0; test < state_t::max_tests(); ++test )
    if( s.available_test( test ) )
      {
        unsigned qv = (hash.*qvalue)( s, test );
        if( qv > bound ) continue;
        flag = true;
        for( size_t obs = 0; obs < 2; ++obs )
          { 
            state_t s_obs = s.next_state( test, obs, *test_matrix );
            flag = ldfs( 1+depth, hash, s_obs, qvalue );
            if( flag )
              {
                unsigned qv = (hash.*qvalue)( s, test );
                flag = (qv <= bound);
              }
            if( !flag ) break;
          }
        if( flag ) break;
      }

  if( flag )
    {
      hash.mark( s );
      if( verbose )
        {
          indent( std::cout, depth );
          std::cout << "mark=" << hash.value(s) << std::endl;
        }
    }
  else
    {
      unsigned 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 );
}

void
generateStateSpace( const state_t s0, std::set<state_t> &space )
{
  std::list<state_t> queue;
  queue.push_back( s0 );
  space.insert( s0 );
  while( !queue.empty() )
    {
      state_t s = queue.front();
      queue.pop_front();
      for( size_t test = 0; test < state_t::max_tests(); ++test )
        if( s.available_test( test ) )
          for( size_t obs = 0; obs < 2; ++obs )
            {
              state_t s_obs = s.next_state( test, obs, *test_matrix );
              if( space.find( s_obs ) == space.end() )
                {
                  space.insert( s_obs );
                  queue.push_back( s_obs );
                }
            }
    }
}

size_t
valueIteration( hash_t &hash, const state_t s0, qvalue_func_t qvalue )
{
  std::set<state_t> space;
  generateStateSpace( s0, space );
  unsigned residual = 1;
  size_t iterations = 0;
  while( residual > 0 )
    {
      residual = 0;
      for( std::set<state_t>::const_iterator si = space.begin(); si != space.end(); ++si )
        if( !(*si).terminal() )
          {
            unsigned value = hash.value( *si );
            unsigned bqv = hash.bestQValue( *si, qvalue );
            residual = MAX(residual,bqv-value);
            hash.update( *si, bqv );
          }
        else
          hash.update( *si, (*si).terminal_value() );
      ++iterations;
      if( verbose ) std::cout << "residual=" << residual << std::endl;
    }
  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, UINT_MAX, UINT_MAX, s );
  graph.set_root( root );

  size_t iterations = 0;
  while( !hash.solved( s ) )