这是一道poj1184的题目，由于求解的是最优解，所以首先想到的就是使用广度优先搜索。对于这道题目我同时使用set容器，来作为状态判重。

/* *	POJ 1184 聪明的打字员  *	版本1 ： 普通的广度搜索 ,使用set进行状态判重 */#include
    
     #include
     
      #include
      
       #include
       
        //#include
        
         #define CODE_LENGTH 6 using namespace std;typedef struct str{		int step;	string code;	int pos;					//光标的位置 	str(){}	//光标的初始位置为0 	str(int s , string c):step(s),code(c),pos(0){}	//重载operator< 	friend bool operator<(const str& a, const str& b) {				if(a.code < b.code )			return true;		if(a.code > b.code )			return false;					if( a.pos < b.pos )			return true;		if( a.pos > b.pos)			return false ;				return false ;	}}Str;typedef pair
         
          
           ::iterator,bool> Pair; queue
           
             Queue; //bfs的队列的数据结构set
            
              HashSet; //状态判重的set //ofstream out("result.txt");static int pushNUM=0;//index :标记使用的操作//state：表示当前节点 Str changeCode(const Str& state,const int& index){ Str tmp = state ; char c; //1 : swap0 2: swap1 3:up 4:down 5:left 6:right switch( index ){ case 1: if( 0 == tmp.pos ) {} else { c= tmp.code[0]; tmp.code[0]= tmp.code[tmp.pos]; tmp.code[tmp.pos] = c; } break; case 2: if( 5 == tmp.pos ) {} else{ c = tmp.code[5]; tmp.code[5]= tmp.code[tmp.pos]; tmp.code[ tmp.pos] = c ; } break; //注意这里是字符不是数字 case 3: if( '9' == tmp.code[ tmp.pos ] ){} else{ tmp.code[tmp.pos] += 1 ; } break; case 4: if( '0' == tmp.code[ tmp.pos ] ){} else{ tmp.code[tmp.pos] -= 1 ; } break; case 5: if( 0 == tmp.pos ) {} else{ tmp.pos -=1 ; } break; case 6: if( 5 == tmp.pos ){} else{ tmp.pos += 1; } break; default: cout<<"ERROR!"<
             
              >org>>dest; Str strOrg(0,org),strDest(0,dest); clock_t time=clock(); bfsSearch( strOrg, strDest ); cout<<"Time consumed: "<
              
               <<" MS"<
              
             
            
           
          
         
        
       
      
     
    

在这里值得注意的地方如下：

 

1、由于重复状态的条件必须满足有相同的code和光标位置，所以在str结构体中重载operator<操作时，需要同时考虑code和pos两个域，保证这两个状态的都相同时，是不会被插入到set中的。因为对于set来说，他判断是否insert时发生冲突是通过两次使用operator<对两个状态进行检测，发现得出相同的结果。如果比较对象域是string这样的标准类型的话，那么在operator<函数中不能出现等于号，即写成这样是错误的：return a.code <= b.code，因为这样的话，就不会发生冲突了。

 

2、由于没有进行其他方面的优化，所以这个程序的效率是比较差的。

 

下面是我改用hash处理状态判重的一个程序：

 

/* *	POJ 1184 聪明的打字员  *	版本2 ： 使用hash进行状态判重 */#include
    
     #include
     
      #include
      
       #include
       
        //#include
        
         #define HashTableSize 262147using namespace std;typedef struct str{		int step;	string code;	int pos;					//光标的位置 	str(){}	//光标的初始位置为0 	str(int s , string c):step(s),code(c),pos(0){}}Str,*PStr;//typedef pair
         
          
           ::iterator,bool> Pair; queue
           
             Queue; //A*的堆数据结构 set
            
              HashSet; //状态判重的set PStr hashTable[HashTableSize]={NULL}; //状态判重的hash表 //static int conflict=0,hashNum=0;//ofstream out("result.txt");int getHashValue(const Str& state){ string str(state.code); str = str.append(1,state.pos+'0'); int hashValue=0 ,len= str.length()+1; for(int i=0; i
             
              >org>>dest; Str strOrg(0,org),strDest(0,dest); clock_t time=clock(); bfsSearch( strOrg, strDest ); cout<<"Time consumed: "<
              
               <<" MS"<
              
             
            
           
          
         
        
       
      
     
    

这里我把光标的位置直接放到code的最后一位，这样直接作为字符串来处理，方便很多。但是测试下来，性能没有太大的提高，因为需要搜索的状态实在太多，到后面hash冲突现象很严重。

 

后来我用A*算法来优化BFS搜索，代码如下：

/* *	POJ 1184 聪明的打字员  *	版本3 ： A* ,使用set进行状态判重 */#include
    
     #include
     
      #include
      
       #include
       
        //#include
        
         #define CODE_LENGTH 6 #define TABLE_SIZE 1<<16using namespace std;typedef struct str{		int step;	string code;	int pos;					//光标的位置 	int fCost;	int hCost;	int myindex;	int parent ;		str(){}	//光标的初始位置为0 	str(int s , string c):step(s),code(c),pos(0){}	//重载operator< 	friend bool operator<(const str& a, const str& b) {				//注意一定要写成< ，这样才能排除code相同的Str 		return a.code < b.code ;	}}Str;//堆的比较函数 struct compareFunction{		bool operator()(const Str& a,const Str& b){				return a.fCost>=b.fCost ;	}	};typedef pair
         
          
           ::iterator,bool> Pair; priority_queue
           
            
             ,compareFunction> Heap; set
             
               ClosedSet; //A*的关闭列表set
              
                OpenSet;//ofstream out("result.txt");static int storageTableIndex=0;//目标串 string cc="654321";static int pushNum=0;//index :标记使用的操作//state：表示当前节点 Str changeCode(const Str& state,const int& index){ Str tmp = state ; char c; //1 : swap0 2: swap1 3:up 4:down 5:left 6:right switch( index ){ case 1: if( 0 == tmp.pos ) {} else { c= tmp.code[0]; tmp.code[0]= tmp.code[tmp.pos]; tmp.code[tmp.pos] = c; } break; case 2: if( 5 == tmp.pos ) {} else{ c = tmp.code[5]; tmp.code[5]= tmp.code[tmp.pos]; tmp.code[ tmp.pos] = c ; } break; //注意这里是字符不是数字 case 3: if( '9' == tmp.code[ tmp.pos ] ){} else{ tmp.code[tmp.pos] += 1 ; } break; case 4: if( '0' == tmp.code[ tmp.pos ] ){} else{ tmp.code[tmp.pos] -= 1 ; } break; case 5: if( 0 == tmp.pos ) {} else{ tmp.pos -=1 ; } break; case 6: if( 5 == tmp.pos ){} else{ tmp.pos += 1; } break; default: cout<<"ERROR!"<
               
                >org>>dest; Str strOrg(0,org),strDest(0,dest); strOrg.fCost=0; strOrg.hCost=0; strOrg.parent = -1; strOrg.myindex=storageTableIndex++;// storageTable[strOrg.myindex]=strOrg; clock_t time=clock(); aStarSearch( strOrg, strDest ); cout<<"Time consumed: "<
                
                 <<" MS"<
                
               
              
             
            
           
          
         
        
       
      
     
    

 

这里有一些值得注意的地方：

 

1、这里关闭列表使用的是set容器，另外和传统的A*算法不同，我这里没有将产生的已有状态，但还没有进入关闭列表的状态，加入到堆数据结构中，因为可以分析出来，在这道题目中，这些状态是不可能产生更好的搜索路径的。这样大大提高了搜索效率。

但是在有些例子下，还是搜索时间太长了，需要进一步剪枝优化。

 

在这些程序中使用到的一些技巧吧：

1、使用pair这个utility。声明定义pair，如：typedef pair<set<string>::iterator , bool > Pair ;

pair的两个域可以分别用first和second来引用。

2、set容器中的insert有一个版本为 pair insert( constTYPE &val ); 注意返回的是pair。

3、string中的一个append版本为：basic_string &append( size_type num, char ch );  在字符串的末尾添加num个字符ch 。

文章转载出处：