八我的数码游戏与一般图搜索算法.cpp

八数码游戏的不同实现方法! 1.八数码游戏与A*算法的结合! 本程序主要是给出一个A*算法的示例!效率并不高 2.广度算法 这个效率还可以的!

#pragma warning(disable:4786)
#include<iostream>
#include<deque>
#include<algorithm>
#include<functional>
#include<cmath>
#include<map>
using namespace std;

const N=3;

map<int,int> sonFather;//根据sun的m_name找父亲的m_name;
map<int,int>::iterator ite;

class A
{
public:

	A(char a[N][N])
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
			m_a[i][j]=a[i][j];
			}
		}
        m_name=0;
		m_price=0;
		m_depth=0;
	}

	bool operator ==(const A& a)
	{
		for(int i=0;i<N;i++)
		{
		for(int j=0;j<N;j++)
			{
				if(a.m_a[i][j]!=m_a[i][j])
				{
					return false;
				}
			}
		}
		
		return true;
	}

	//到aim所有格子最少需要移动步数的总和。//启发函数
int price(const A& aim) const
  {
	int price=0;

	for(int i=0;i<N;i++)
	{
	   	for(int j=0;j<N;j++)
		{
			for(int m=0;m<N;m++)
			{
				for(int n=0;n<N;n++)
				{
					if(((*this).m_a[i][j]==aim.m_a[m][n]) && ((*this).m_a[i][j]!=' '))
					{
						price+=abs(m-i)+abs(n-j);
					}
				}
			}
		}
	}

	return price;
  }

bool ancestor( const A& b) const
{
	ite=sonFather.begin();
	int father=sonFather[b.m_name];

	while(ite!=sonFather.end() )
	{
	   int fath=father;
	   
       if(father==(*this).m_name)
		{
			return true;
		}

	   father=sonFather[fath];

		ite++;
	}

	return false;
}

 
	void print()
	{
		for(int i=0;i<N;i++)
		{   
			for(int j=0;j<N;j++)
			{
				cout<<m_a[i][j]<<"	";
			}

			cout<<endl<<endl<<endl;
		}
	}

public:
 	char m_a[N][N];
	int m_price;
	int m_depth;
	int m_name;

};	

class fo
{
public:
bool operator()(const A& a, const A& b) const 
{
	return a.m_price<b.m_price;
}
};

void main()
{
	//char a[N][N]={'1', '2', '3', ' '};
	//char b[N][N]={'3', '1', ' ', '2'};
	char a[N][N]={'1','2','3','8',' ','4','7','6','5'};
	char b[N][N]={'1','3','8','2','6',' ','4','7','5'};
	A soure(a);
	soure.m_depth=0;
	soure.m_name=0;
	A aim(b);
    deque<A> open;
	deque<A> close;
    deque<A>::iterator iter;
	open.push_back(soure);
    sonFather.insert(make_pair(0,0));
	int name=1; 

	while(1)
	{
        if(open.empty()==true)
		{
			cout<<"There is no trace from soure to aim!"<<endl;
				break;
		}
       
        A father(open[0].m_a);//即将扩展的节点
		father.m_name=open[0].m_name;
		father.m_depth=open[0].m_depth;
		father.m_price=open[0].m_price;
		close.push_back(father);
		open.erase(open.begin());
		
		//找到aim后，close表的最后一个元素是aim
		if(father==aim)
		{
			break;
		}	
		
        //找出空格子所在的位置。便于扩展子节点。
        int m,n;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				if(father.m_a[i][j]==' ')
				{
					m=i;
					n=j;
					break;
				}
			}
		}
        
		if(m<N-1)//往上移
		{   
			A sun(father.m_a);
			sun.m_depth=father.m_depth+1;
		    swap(sun.m_a[m+1][n],sun.m_a[m][n]);
	        
			//如果sun已经存在于open表中，即*iter==sun，且经新父节点的路径代价更小
			//修改*iter的m_depth和m_price
			 if((iter=find(open.begin(),open.end(),sun))!=open.end() && !(sun.ancestor(father)))
			{  
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				 sonFather[sun.m_name]=father.m_name;
			 }
			}
            
			//如果sun已经存在与close表中，即*iter=sun,且经新父节点的路径代价更小
			//修改*iter的m_depth和m_price,并将*iter从close表中转移到open表。
			if((iter=find(close.begin(),close.end(),sun))!=close.end() && !(sun.ancestor(father)))
			{
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
                 open.push_back(*iter);
			     close.erase(iter);
			 }
			}

            //如果sun为全新的节点，将sun插入open表.    
			if((iter=find(open.begin(),open.end(),sun))==open.end() && (iter=find(close.begin(),close.end(),sun))==close.end() )
			{
				sun.m_price=(*iter).price(aim)+sun.m_depth;
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		}

        if(m>0)//往下移
		{   
			A sun(father.m_a);
			sun.m_depth=father.m_depth+1;
		    swap(sun.m_a[m-1][n],sun.m_a[m][n]);
	
		    if((iter=find(open.begin(),open.end(),sun))!=open.end() && !(sun.ancestor(father)))
			{  
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth; 
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
			 }

			}
          
			if((iter=find(close.begin(),close.end(),sun))!=close.end() && !(sun.ancestor(father)))
			{
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
                 open.push_back(*iter);
				 close.erase(iter);
			 
			 }
			}
           
			if((iter=find(open.begin(),open.end(),sun))==open.end() && (iter=find(close.begin(),close.end(),sun))==close.end() )
			{
				sun.m_price=sun.price(aim)+sun.m_depth;
			    sun.m_name=name; 
			    sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		}

         if(n<N-1)//往左移
		{   
			A sun(father.m_a);
			sun.m_depth=father.m_depth+1;
		    swap(sun.m_a[m][n+1],sun.m_a[m][n]);
	        
		    if((iter=find(open.begin(),open.end(),sun))!=open.end() && !(sun.ancestor(father)))
			{  
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
			 }
			}
            
			if((iter=find(close.begin(),close.end(),sun))!=close.end() && !(sun.ancestor(father)))
			{
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
             open.push_back(*iter);
			 close.erase(iter);
			 }

			}

			if((iter=find(open.begin(),open.end(),sun))==open.end() && (iter=find(close.begin(),close.end(),sun))==close.end() )
			{
				sun.m_price=sun.price(aim)+sun.m_depth;
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		 }

          if(n>0)//往右移
		  {   
			A sun(father.m_a);
			sun.m_depth=father.m_depth+1;
		    swap(sun.m_a[m][n-1],sun.m_a[m][n]);
	       
		    if((iter=find(open.begin(),open.end(),sun))!=open.end() && !(sun.ancestor(father)))
			{  
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
                 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
			 }

			}
            
			if((iter=find(close.begin(),close.end(),sun))!=close.end() && !(sun.ancestor(father)))
			{
             if(sun.m_depth<(*iter).m_depth)
			 {
				 (*iter).m_depth=sun.m_depth;
				 (*iter).m_price=(*iter).price(aim)+(*iter).m_depth;
				  sonFather[sun.m_name]=father.m_name;
                 open.push_back(*iter);
			     close.erase(iter);
			 }
			}

			if((iter=find(open.begin(),open.end(),sun))==open.end() && (iter=find(close.begin(),close.end(),sun))==close.end() )
			{
				sun.m_price=sun.price(aim)+sun.m_depth;
			    sun.m_name=name; 
				sonFather.insert(make_pair(sun.m_name,father.m_name));
				name++;
				open.push_back(sun);
			}
		

		}
  
			stable_sort(open.begin(),open.end(),fo());

		}//while(1)

	    	//output
			cout<<name<<endl<<endl;//节点的个数
			if(open.empty()==false)
			{
				A sun((*(close.end()-1)).m_a);
				sun.m_name=(*(close.end()-1)).m_name;
				int x=sun.m_name;
				sun.print();

				while(x!=0)
				{
					//iter=find_if(close.begin(),close.end(),bind2nd(superior<A>(),sun));
			    	//	iter=find_if(close.begin(),close.end(),bind2nd(su<A>(),));
					iter=close.begin();
					while(iter!=close.end())
					{
						//如果将x换成son，因为同名，将调用上面的son，而我实际想调用的是下面的。
						//因此造成
						if((*iter).m_name==sonFather[x])
						{
							break;
						}
						else
						{
							iter++;
						}
					}

					A sun((*iter).m_a);
				    sun.m_name=(*iter).m_name;
					x=sun.m_name;
					cout<<endl<<endl<<endl<<endl;
			    	sun.print();

				}
			}
		}