mts.cc

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

  std::map<unsigned,std::pair<bool,state_t> > nodes;
  std::map<state_t,unsigned> anodes, onodes;
  std::set<std::pair<unsigned,unsigned> > edges;

  unsigned k = 0;
  nodes.insert( std::make_pair( k, std::make_pair( true, s0 ) ) );
  onodes.insert( std::make_pair( s0, k++ ) );

  for( int bx = 0; bx < n; ++bx )
    for( int by = 0; by < n; ++by )
      for( int ax = 0; ax < n; ++ax )
        for( int ay = 0; ay < n; ++ay )
          {
            state_t s( ax, ay, bx, by );
            if( onodes.find( s ) == onodes.end() )
              {
                nodes.insert( std::make_pair( k, std::make_pair( true, s ) ) );
                onodes.insert( std::make_pair( s, k++ ) );
              }
            assert( onodes.find( s ) != onodes.end() );

            if( !s.terminal() )
              {
                for( int a = 0; a < 4; ++a )
                  if( VALID(n,s.ax(),s.ay(),a) )
                    {
                      state_t s_a = s.a_move( a );
                      if( anodes.find( s_a ) == anodes.end() )
                        {
                          nodes.insert( std::make_pair( k, std::make_pair( false, s_a ) ) );
                          anodes.insert( std::make_pair( s_a, k++ ) );
                        }
                      assert( anodes.find( s_a ) != anodes.end() );
                      edges.insert( std::make_pair( onodes[s], anodes[s_a] ) );

                      for( int b = 0; b < 4; ++b )
                        if( VALID(n,s_a.bx(),s_a.by(),b) )
                          {
                            state_t s_ab = s_a.b_move( b );
                            if( onodes.find( s_ab ) == onodes.end() )
                              {
                                nodes.insert( std::make_pair( k, std::make_pair( true, s_ab ) ) );
                                onodes.insert( std::make_pair( s_ab, k++ ) );
                              }
                            assert( onodes.find( s_ab ) != onodes.end() );
                            edges.insert( std::make_pair( anodes[s_a], onodes[s_ab] ) );
                          }
                    }
              }
          }
  assert( (k == onodes.size() + anodes.size()) && (k == nodes.size()) );

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

  // output nodes
  for( size_t k = 0; k < nodes.size(); ++k )
    {
      assert( nodes.find( k ) != nodes.end() );
      std::map<unsigned,std::pair<bool,state_t> >::const_iterator p = nodes.find( k );
      bool or_node = (*p).second.first;
      state_t s = (*p).second.second;
      double hvalue = ( !h ? 0 : h->value( s ) );

      if( format == 1 )
        {
          os << "h(" << k << ") " << (!or_node?0:hvalue) << std::endl
             << "AND(0)/OR(1) " << (or_node?1:0) << std::endl
             << "SOLVED(0)/NON_TERMINAL(1) " << (or_node && s.terminal()?0:1) << std::endl;
        }
      else
        {
          os << (or_node?"or":"and") << " "
             << k << " "
             << (or_node && s.terminal()?0:1) << " "
             << (!or_node?0:hvalue) << std::endl;
        }
    }

  // output edges
  if( format == 1 ) os << "arcarcarcarcarcarcarcarcarcarcarcarc" << std::endl;
  for( std::set<std::pair<unsigned,unsigned> >::const_iterator it = edges.begin(); it != edges.end(); )
    {
      assert( nodes.find( (*it).first ) != nodes.end() );
      assert( nodes.find( (*it).second ) != nodes.end() );
      std::map<unsigned,std::pair<bool,state_t> >::const_iterator p = nodes.find( (*it).first );
      if( format == 1 )
        {
          os << "vtx1 " << (*it).first << std::endl
             << "vtx2 " << (*it).second << std::endl
             << "weight " << ((*p).second.first?1:0) << std::endl
             << "another? " << (++it == edges.end() ? 0 : 1) << std::endl;
        }
      else
        {
          os << "edge "
             << (*it).first << " "
             << (*it).second << " "
             << ((*p).second.first?1:0) << 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 )
{
  void printMazePostscript( int, const unsigned char*, std::ostream& );
  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 postscript = 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':
          algorithm = atoi( argv[1] );
          ++argv;
          --argc;
          break;
        case 'a':
          qvalue = &hash_t::QValueAdd;
          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 'p':
          postscript = true;
          break;
        case 's':
          rseed = atoi( argv[1] );
          ++argv;
          --argc;
          break;
        case 'S':
          stats = true;
          break;
        case 'v':
          verbose = true;
          break;
        }
      ++argv;
      --argc;
    }

  int n = atoi( argv[0] );
  seed[0] = seed[1] = seed[2] = rseed;
  seed48( seed );
  if( output ) std::cout << "seed=" << rseed << std::endl;

  // generate maze
  std::set<std::pair<int,int> > *visited = new std::set<std::pair<int,int> >;
  std::set<std::pair<int,int> > *nowalls = new std::set<std::pair<int,int> >;
  dfs( n, 0, 0, *visited, *nowalls );
  delete visited;
  moveMap( n, maze, *nowalls );
  delete nowalls;

  const state_t s0( 0, 0, n-1, n-1 );

  gettimeofday( &startTime, NULL );
  heuristic_t heuristic( htype, n );
  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 );

  // output maze
  if( output )
    {
      std::cout << "maze: " << std::endl << std::endl;
      printMaze( n, 2, maze );
      std::cout << std::endl;
    }
  else if( postscript )
    {
      printMazePostscript( n, maze, std::cerr );
      return( 0 );
    }
  else if( dump )
    {
      dumpCFC( n, s0, &heuristic, std::cerr, format );
      return( 0 );
    }

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

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

void
printMazePostscript( int n, const unsigned char *maze, std::ostream &os )
{
  void psHeader( int, int, std::ostream& );
  void psTrailer( std::ostream& );
  void psDrawFilledRectangle( int, int, int, int, int, int, int, std::ostream& );
  void psDrawThickLine( int, int, int, int, int, int, int, std::ostream& );

  psHeader( n, n, os );
  psDrawFilledRectangle( 0, 0, BOXW, BOXW, 255, 255, 255, os );
  psDrawFilledRectangle( (n-1)*BOXW, (n-1)*BOXW, BOXW, BOXW, 255, 255, 255, os );
  for( int j = 0; j < n; ++j )
    {
      for( int i = 0; i < n; ++i )
        {
          psDrawFilledRectangle( i*BOXW, j*BOXW, BOXW, BOXW, 255, 255, 255, os );
          if( !VALID(n,i,n-1-j,DOWN) ) psDrawThickLine( i*BOXW, j*BOXW, BOXW, 0, 0, 0, 0, os );
          if( !VALID(n,i,n-1-j,UP) ) psDrawThickLine( i*BOXW, (j+1)*BOXW, BOXW, 0, 0, 0, 0, os );
          if( !VALID(n,i,n-1-j,LEFT) ) psDrawThickLine( i*BOXW, j*BOXW, 0, BOXW, 0, 0, 0, os );
          if( !VALID(n,i,n-1-j,RIGHT) ) psDrawThickLine( (i+1)*BOXW, j*BOXW, 0, BOXW, 0, 0, 0, os );
        }
    }
#if 0
  psHeader( 2*n+1, 2*n+1, os );
  for( int j = 0; j < n; ++j )
    {
      psDrawFilledRectangle( 0, 2*j*BOXW, BOXW, BOXW, 255, 0, 0, os );
      for( int i = 0; i < n; ++i )
        {
          if( !VALID(n,i,n-1-j,DOWN) )
            psDrawFilledRectangle( (2*i+1)*BOXW, 2*j*BOXW, BOXW, BOXW, 255, 0, 0, os );
          else
            psDrawFilledRectangle( (2*i+1)*BOXW, 2*j*BOXW, BOXW, BOXW, 255, 255, 255, os );
          psDrawFilledRectangle( (2*i+2)*BOXW, 2*j*BOXW, BOXW, BOXW, 255, 0, 0, os );
        }
      psDrawFilledRectangle( 0, (2*j+1)*BOXW, BOXW, BOXW, 255, 0, 0, os );
      for( int i = 0; i < n; ++i )
        {
          psDrawFilledRectangle( (2*i+1)*BOXW, (2*j+1)*BOXW, BOXW, BOXW, 255, 255, 255, os );
          if( !VALID(n,i,n-1-j,RIGHT) )
            psDrawFilledRectangle( (2*i+2)*BOXW, (2*j+1)*BOXW, BOXW, BOXW, 255, 0, 0, os );
          else
            psDrawFilledRectangle( (2*i+2)*BOXW, (2*j+1)*BOXW, BOXW, BOXW, 255, 255, 255, os );
        }
    }
  psDrawFilledRectangle( 0, (2*n)*BOXW, BOXW, BOXW, 255, 0, 0, os );
  for( int i = 0; i < n; ++i )
    {
      psDrawFilledRectangle( (2*i+1)*BOXW, (2*n)*BOXW, BOXW, BOXW, 255, 0, 0, os );
      psDrawFilledRectangle( (2*i+2)*BOXW, (2*n)*BOXW, BOXW, BOXW, 255, 0, 0, os );
    }
#endif
  psTrailer( os );
}

void
psHeader( int rows, int cols, std::ostream &os )
{
  os << "%!PS-Adobe-2.0 EPSF-1.2" << std::endl
     << "%%Creator: unknown" << std::endl
     << "%%DocumentFonts:" << std::endl
     << "%%Pages: 1" << std::endl
     << "%%BoundingBox: 0 0 " << (cols+2)*BOXW << " " << (rows+2)*BOXW << std::endl
     << "%%EndComments" << std::endl
     << "%%EndProlog" << std::endl
     << "%%Page: 1 1" << std::endl
     << "0 setlinewidth " << BOXW << " " << BOXW << " translate" << std::endl;
}

void
psTrailer( std::ostream &os )
{
  os << "%%EOF" << std::endl;
}

void
psDrawFilledRectangle( int x, int y, int dx, int dy, int r, int g, int b, std::ostream &os )
{
  os << r << " " << g << " " << b << " setrgbcolor" << std::endl
     << "newpath " << x << " " << y << " moveto "
     << dx << " 0 rlineto 0 " << dy << " rlineto "
     << -dx << " 0 rlineto closepath fill" << std::endl
     << "0 0 0 setrgbcolor" << std::endl
     << "newpath " << x << " " << y << " moveto "
     << dx << " 0 rlineto 0 " << dy << " rlineto " << -dx
     << " 0 rlineto closepath stroke" << std::endl;
}

void
psDrawThickLine( int x, int y, int dx, int dy, int r, int g, int b, std::ostream &os )
{
  os << "2 setlinewidth "
     << r << " " << g << " " << b << " setrgbcolor" << std::endl
     << "newpath " << x << " " << y << " moveto "
     << dx << " " << dy << " rlineto closepath stroke "
     << "0 setlinewidth" << std::endl;
}