diagnosis.cc

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

    {
      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() );
  aux.clear();

  bool rv = true;
  aux.insert( e.second );
  queue.push_front( e );
  while( !queue.empty() )
    {
      e = queue.front();
      queue.pop_front();
      if( ((e.second != 0) && e.second->mark_) || e.first.terminal() )
	{
	  if( e.second == 0 )
	    {
	      hash.update( e.first, e.first.terminal_value() );
	      hash.mark( e.first );
	    }
	  else if( !e.second->mark_ )
	    e.second->mark_ = true;
	  continue;
	}
      assert( !e.first.terminal() );

      stack.push_front( e );
      std::pair<unsigned,size_t> p = hash.bestAction( e.first, qvalue );
      if( (e.second == 0) || (e.second->lower_ != p.first) ) { rv = false; continue; }
      assert( e.first.available_test( p.second ) );
      for( size_t obs = 0; obs < 2; ++obs )
        {
          state_t s_obs = e.first.next_state( p.second, obs, *test_matrix );
          hash_t::data_pair tmp = hash.get( s_obs );
          if( aux.find( tmp.second ) == aux.end() )
            {
              aux.insert( tmp.second );
              queue.push_front( tmp );
            }
        }
    }

  while( !stack.empty() )
    {
      e = stack.front();
      stack.pop_front();
      assert( (e.second != 0) || !rv );
      if( rv )
	e.second->mark_ = true;
      else
	{
	  assert( !e.first.terminal() );
	  unsigned bqv = hash.bestQValue( e.first, qvalue );
	  assert( (e.second == 0) || (bqv >= e.second->lower_) );
	  if( e.second != 0 )
	    e.second->lower_ = bqv;
	  else
	    hash.update( e.first, bqv );
	}
    }

  return( rv );
}

void
labeled_lrta_trial( hash_t &hash, const state_t s0, qvalue_func_t qvalue )
{
  std::list<state_t> queue;
  std::vector<size_t> b_moves;

  state_t s = s0;
  queue.push_front( s );
  //std::cout << "begin trial" << std::endl;
  while( !s.terminal() && !hash.solved( s ) )
    {
      //std::cout << "  state = " << s << std::endl;
      ++expansions;
      std::pair<unsigned,size_t> p = hash.bestAction( s, qvalue );
      assert( p.first != UINT_MAX );
      if( p.first == UMAX ) break;
      hash.update( s, p.first );
      size_t obs = lrand48() % 2;
      assert( s.available_test( p.second ) );
      //std::cout << "  test = " << p.second << std::endl;
      //std::cout << "  obs = " << obs << std::endl;
      s = s.next_state( p.second, obs, *test_matrix );
      //std::cout << "  s_obs = " << s << std::endl;
      queue.push_front( s );
    }
  //std::cout << "end trial" << std::endl;

  // mark terminal nodes as solved
  if( s.terminal() || (hash.value( s ) == UMAX) )
    {
      if( s.terminal() ) hash.update( s, s.terminal_value() );
      hash.mark( s );
    }

  // labeling
  while( !queue.empty() )
    {
      state_t s = queue.front();
      queue.pop_front();
      if( !checksolved( hash.get(s), hash, qvalue ) ) break;
    }
}

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

size_t
policySize( const state_t s0, hash_t &hash, qvalue_func_t qvalue )
{
  std::set<state_t> policy, aux;
  std::list<state_t> stack;
  aux.insert( s0 );
  stack.push_back( s0 );
  while( !stack.empty() )
    {
      state_t s = stack.front();
      stack.pop_front();
      policy.insert( s );
      if( s.terminal() ) continue;

      std::pair<unsigned,size_t> p = hash.bestAction( s, qvalue );
      for( int obs = 0; obs < 2; ++obs )
        {
          state_t s_obs = s.next_state( p.second, obs, *test_matrix );
          if( aux.find( s_obs ) == aux.end() )
            {
              stack.push_back( s_obs );
              aux.insert( s_obs );
            }
        }
    }
  return( policy.size() );
}

void
dumpCFC( const state_t s0, const heuristic_t *h, std::ostream &os, int format )
{
  std::map<state_t,unsigned> onodes;
  std::map<unsigned,state_t> ionodes;
  std::map<std::pair<unsigned,unsigned>,unsigned> anodes;
  std::set<std::pair<unsigned,std::pair<unsigned,int> > > edges;

  std::set<state_t> space;
  generateStateSpace( s0, space );

  unsigned k = 0;
  ionodes.insert( std::make_pair( k, s0 ) );
  onodes.insert( std::make_pair( s0, k++ ) );
  for( std::set<state_t>::iterator si = space.begin(); si != space.end(); ++si )
    {
      if( onodes.find( (*si) ) == onodes.end() )
        {
          ionodes.insert( std::make_pair( k, (*si) ) );
          onodes.insert( std::make_pair( (*si), k++ ) );
        }
      if( (*si).terminal() ) continue;
      unsigned s_idx = onodes[(*si)];

      for( size_t test = 0; test < state_t::max_tests(); ++test )
        if( (*si).available_test( test ) )
          {
             std::pair<unsigned,unsigned> s_a( s_idx, test );
             if( anodes.find( s_a ) == anodes.end() ) anodes.insert( std::make_pair( s_a, k++ ) );
             assert( anodes.find( s_a ) != anodes.end() );
             unsigned s_a_idx = anodes[s_a];
             edges.insert( std::make_pair( s_idx, std::make_pair( s_a_idx, 1 ) ) );
             for( size_t obs = 0; obs < 2; ++obs )
               {
                 state_t s_obs = (*si).next_state( test, obs, *test_matrix );
                 if( onodes.find( s_obs ) == onodes.end() )
                   {
                     ionodes.insert( std::make_pair( k, s_obs ) );
                     onodes.insert( std::make_pair( s_obs, k++ ) );
                   }
                 assert( onodes.find( s_obs ) != onodes.end() );
                 edges.insert( std::make_pair(s_a_idx,std::make_pair(onodes[s_obs],0)) );
               }
          }
    }
  assert( space.size() == onodes.size() );
  assert( k == onodes.size() + anodes.size() );

  if( format == 1 )
    os << "Number_of_nodes " << onodes.size() + anodes.size() << std::endl;
  else
    {
      os << "comment states " << state_t::max_states()
         << " tests " << state_t::max_tests()
         << " random seed " << rseed << std::endl;
      os << "aograph " << onodes.size() << " "
         << anodes.size() << " "
         << edges.size() << std::endl;
    }

  // output nodes
  for( size_t k = 0; k < onodes.size() + anodes.size(); ++k )
    {
      std::map<unsigned,state_t>::const_iterator it = ionodes.find( k );
      if( it != ionodes.end() )
        {
          double hvalue = ( !h ? 0 : h->value( (*it).second ) );
          int terminal = ( (*it).second.terminal() ? 0 : 1 );
          if( format == 1 )
            {
              os << "h(" << k << ") " << hvalue << std::endl
                 << "AND(0)/OR(1) 1" << std::endl
                 << "SOLVED(0)/NON_TERMINAL(1) " << terminal << std::endl;
            }
          else
            {
              os << "or " << k << " " << terminal << " " << hvalue << std::endl;
            }
        }
      else
        {
          if( format == 1 )
            {
              os << "h(" << k << ") 0" << std::endl
                 << "AND(0)/OR(1) 0" << std::endl
                 << "SOLVED(0)/NON_TERMINAL(1) 1" << std::endl;
            }
          else
            {
              os << "and " << k << " 1 0" << std::endl;
            }
        }
    }

  // output edges
  if( format == 1 ) os << "arcarcarcarcarcarcarcarcarcarcarcarc" << std::endl;
  for( std::set<std::pair<unsigned,std::pair<unsigned,int> > >::const_iterator it = edges.begin(); it != edges.end(); )
    if( format == 1 )
      {
        os << "vtx1 " << (*it).first << std::endl
           << "vtx2 " << (*it).second.first << std::endl
           << "weight " << (*it).second.second << std::endl
           << "another? " << (++it == edges.end() ? 0 : 1) << std::endl;
      }
    else
      {
        os << "edge " << (*it).first << " "
           << (*it).second.first << " "
           << (*it).second.second << std::endl;
        ++it;
      }
}

void
diffTime( unsigned long& secs, unsigned long& usecs, struct timeval& t1, struct timeval& t2 )
{
  if( t1.tv_sec == t2.tv_sec )
    {
      secs = 0;
      usecs = t2.tv_usec - t1.tv_usec;
    }
  else
    {
      secs = (t2.tv_sec - t1.tv_sec) - 1;
      usecs = (MILLION - t1.tv_usec) + t2.tv_usec;
      if( usecs > MILLION )
	{
	  ++secs;
	  usecs = usecs % MILLION;
	}
    }
}

int
main( int argc, char **argv )
{
  unsigned short seed[3];
  unsigned long secs, usecs;
  struct timeval startTime, elapsedTime;

  qvalue_func_t qvalue = &hash_t::QValueMax;
  int algorithm = 0;
  bool dump = false;
  int format = 1;
  bool output = false;
  bool stats = false;

  int htype = 0;
  size_t hiter = 0;

  // read arguments
  ++argv;
  --argc;
  if( argc == 0 ) exit( -1 );
  while( **argv == '-' )
    {
      switch( argv[0][1] )
        {
        case 'a':
          qvalue = &hash_t::QValueAdd;
          break;
        case 'A':
          algorithm = atoi( argv[1] );
          ++argv;
          --argc;
          break;
        case 'd':
          dump = true;
          break;
        case 'f':
          format = 2;
          break;
        case 'h':
          htype = atoi( argv[1] );
          hiter = atoi( argv[2] );
          argv += 2;
          argc -= 2;
          break;
        case 'o':
          output = true;
          break;
        case 's':
          rseed = atoi( argv[1] );
          ++argv;
          --argc;
          break;
        case 'S':
          stats = true;
          break;
        case 'v':
          verbose = true;
          break;
        default:
          std::cerr << "undefined option: " << argv[0] << std::endl;
          exit( -1 );
          break;
        }
      ++argv;
      --argc;
    }

  size_t m = atoi( argv[0] );
  size_t n = atoi( argv[1] );
  seed[0] = seed[1] = seed[2] = rseed;
  seed48( seed );
  if( output ) std::cout << "seed=" << rseed << std::endl;
  state_t::set_max( m, n );

  //std::cout << "generating solvable problem: *"; std::cout.flush();
  test_matrix = test_matrix_t::generate_random( m, n );
  while( !test_matrix->solvable() )
    {
      delete test_matrix;
      test_matrix = test_matrix_t::generate_random( m, n );
      if( output ) { std::cout << "*"; std::cout.flush(); }
    }
  if( output ) std::cout << std::endl << *test_matrix;

  state_t s0;
  for( size_t i = 0; i < m; ++i ) s0.insert_state( i );

  gettimeofday( &startTime, NULL );
  heuristic_t heuristic( htype, *test_matrix );
  heuristic.compute_heuristic( s0, hiter, qvalue );
  gettimeofday( &elapsedTime, NULL );
  diffTime( secs, usecs, startTime, elapsedTime );
  float htime = TIME(secs,usecs);
  if( output ) heuristic.dump( std::cout );

  if( dump )
    {
      dumpCFC( s0, &heuristic, std::cerr, format );
      return( 0 );
    }

  size_t (*atable[5])( hash_t&, const state_t, qvalue_func_t );
  atable[0] = valueIteration;
  atable[1] = ldfsDriver;
  atable[2] = ldfsBoundDriver;
  atable[3] = aostar;
  atable[4] = &labeled_lrta;

  unsigned last_solution = UINT_MAX;
  for( int i = 0; i < 5; ++i )
    if( ((algorithm>>i) % 2 == 1) && (atable[i] != 0) )
      {
        hash_t *hash = new hash_t( &heuristic );
        gettimeofday( &startTime, NULL );
        size_t iterations = (*atable[i])( *hash, s0, qvalue );
        gettimeofday( &elapsedTime, NULL );
        diffTime( secs, usecs, startTime, elapsedTime );
        std::cout << hash->value(s0) << " "
                  << iterations << " "
                  << hash->updates() << " "
                  << expansions << " "
                  << htime << " "
                  << TIME(secs,usecs) << std::endl;
        if( (last_solution < UINT_MAX) && (last_solution != hash->value(s0)) )
          std::cout << "***** DISCREPANCY FOUND" << std::endl;
        last_solution = hash->value( s0 );
        if( stats ) std::cerr << "policy_size=" << policySize( s0, *hash, qvalue ) << std::endl;
        delete hash;
      }
  return( 0 );
}