wode_bashuma.cpp

八数码难题 A*算法 利用堆栈实现启发式搜索

#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#include <queue>
#include <stack>
using namespace std;

const int N=3;
const int Maxstep=120;

struct qipan
{
	int map[N+1][N+1];
	int cuopaishu;
	int father_fangxiang;
	struct qipan* Parent;
};

void print_qipan(struct qipan *dayin)
{
	    
	cout<<"*************************************************"<<endl;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
  
			cout<<dayin->map[i][j]<<"   ";
        }
  
		cout<<endl;
    }
 
	cout<<"*************************************************"<<endl;
}

struct qipan *moveqipan(struct qipan *father,int fangxiang)
{
	int kongx,kongy;
	int gaibianx,gaibiany;
	kongx=kongy=-1;
	struct qipan *child=new struct qipan();
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
  
			child->map[i][j]=father->map[i][j];
			if(father->map[i][j]==0)
			{
				kongx=j;
				kongy=i;
			}
        }
    }
	if(kongx==-1||kongy==-1)
	{
		return NULL;
	}
	switch(fangxiang)
	{	
	case 1:gaibianx=kongx;gaibiany=kongy-1;break;//上
	case 2:gaibianx=kongx;gaibiany=kongy+1;break;//下
	case 3:gaibianx=kongx-1;gaibiany=kongy;break;//左
	case 4:gaibianx=kongx+1;gaibiany=kongy;break;//右
	}

	if(gaibianx>N||gaibianx<1||gaibiany>N||gaibiany<1)
	{}
	else
	{
		child->map[kongy][kongx]=child->map[gaibiany][gaibianx];
		child->map[gaibiany][gaibianx]=0;
	}
	return child;
}

int pipei(struct qipan * temp,struct qipan * mubiao)
{
	int count;
	count=0;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{
			if(temp->map[i][j]!=mubiao->map[i][j])
				count++;
		}

		temp->cuopaishu=count;
		return count;



}

struct qipan * yiuxianshoushuo(struct qipan *chushi,struct qipan *mubiao)
{
	struct qipan *p1,*p2,*p;
	int step=0;
	p=NULL;	    
	queue<struct qipan *> open; 
	queue<struct qipan *> close;
	queue<struct qipan *> change;

	open.push(chushi);
   


	do
	{
		int yy=0;
		do
		{
  			int size = open.size();		   
			int xx = 0;		   
			struct qipan *min; 		  
			struct qipan *temp; 		   
			min = open.front();
			open.pop();
			while(xx<size-1)
			{
				temp=open.front();
				open.pop();
				if(min->cuopaishu>temp->cuopaishu)
				{
					delete min;
					min=temp;

				}
				else if(min->cuopaishu==temp->cuopaishu)
				{

					open.push(temp);
				}
				else
				{
					delete temp;
					temp=NULL;
		
				}
				xx++;
			}
			open.push(min);
			yy++;
		}while(yy<4);//////////////////////////////

		while(!open.empty())
		{
  
			close.push(open.front());
  
			open.pop();
 
		}


		while(!close.empty())
		{
						
			p1 = (struct qipan *)close.front();  
			close.pop();  
			if (p1->cuopaishu== 0) //得到结果
			{
   
				p = p1;   
				return p;
  
			}
   
  
			for(int i = 1; i <= 4; i++)  
			{
    
				if(i == p1->father_fangxiang)
					continue;
    
   
				p2=moveqipan(p1,i);////	p2 = 
    
				if(p2 != p1)//数码是否可以移动   
				{  
					p2->cuopaishu=pipei(p2,mubiao);//获得value值    
					p2->Parent = p1;
         
					switch(i)//设置屏蔽方向,防止往回推
     
					{
     
					case 1:
     
						p2->father_fangxiang = 2;
     
						break;
    
					case 2:
      
						p2->father_fangxiang = 1;
      
						break;
     
					case 3:
     
						p2->father_fangxiang = 4;
    
						break;
    
					case 4:
     
						p2->father_fangxiang = 3;
     
						break;
    
					}
    
					open.push(p2);//存储节点到待处理队列
    
				}
   
			}

		}

		        step++;
        if(step > Maxstep)
            return NULL;	
	}while(p == NULL || open.size() <= 0);

	return p;

}

void main()
{


	struct qipan *kaishi,*mubiao,*jieguo;

	int temps[4][4];
	int i,j,t;	
	cout<<"请输入初始表\n";
	kaishi=new struct qipan();

	mubiao=new struct qipan();

	for(i=1;i<=3;i++)
	{
		for(j=1;j<=3;j++)
		{

			cin>>kaishi->map[i][j];//temps[i][j];	

		}
	}
			

	cout<<"请输入结果图\n";
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			cin>>t;
			mubiao->map[i][j]=t;
		}
	}

 

    kaishi->Parent= NULL;
    kaishi->father_fangxiang=0;
    mubiao->cuopaishu=0;
    cout<<"目标图:"<<endl;
    print_qipan(mubiao);
    cout<<"初始图:"<<endl;
    print_qipan(kaishi);

	kaishi->cuopaishu=pipei(kaishi,mubiao);
    
    jieguo=yiuxianshoushuo(kaishi,mubiao);
   
    if(jieguo != NULL)
    {
        //把路径倒序
        struct qipan *p=jieguo;
        stack<struct qipan *> daoxu;
        while(p->Parent != NULL)
        {
            daoxu.push(p);
            p = p->Parent;
        }
        cout<<"搜索结果:"<<endl;
        while(!daoxu.empty())
        {
            print_qipan(daoxu.top());
            daoxu.pop();
        }
        cout<<"\n完成!";
    }
 
	else
        cout<<"搜索不到结果.深度为 " <<Maxstep<<endl;
 return ;
}