8chess.h

人工智能算法 实现人工智能中的八数码问题

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <windows.h>     
using namespace std;

/***********************************************************************************************
                                           结构体定义
************************************************************************************************/

typedef struct ElemType
{
	int maze[9];
    int g;         //g函数 ，即当前节点的深度（就是距离初始节点有多远）
	int h;		   //h函数 ，即不在位的棋子数
    int father[9]; //父节点数码
	int f;		   //f=g+h
	int locate0;
}ElemType;

struct ElemType init,aim;

typedef struct lnode
{ 
	ElemType  data;           //结点数据类型	
	struct lnode * next;      //结点指针
}lnode,*linklist;

/************************************************************************************************
                                           基本函数
*************************************************************************************************/
/*************************************建空表*******************/
void initlist (linklist  &l)
{
	l=(linklist)malloc (sizeof (lnode));	
	if(!l)exit(0);	
	l->next=NULL;	
}

/************************************销毁链表*****************/
void  destroylist ( linklist  &l)
{
	lnode *p,*q;	
	p=l;    
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		free(q);
	}	
}

/*************************************判空***********************/
int emptylist(linklist l)
{
	if (l->next==NULL)	return 1;	
	else return 0;
}

/********************************结构体赋值***********************/
ElemType fuzhi(ElemType e)
{
	struct ElemType temp;
	for(int i = 0; i < 9; i++)
		temp.maze[i] = e.maze[i];
	for(i = 0; i < 9; i++)
		temp.father[i] = e.father[i];
	temp.f=e.f;
	temp.g=e.g;
	temp.h=e.h;
	return temp;
}

/***********************判断两个结构体是否相等**********************/
//所谓结构体相等仅仅指数码阵相等
int Isequal(ElemType ask,ElemType e)
{
	for(int i = 0; i < 9; i++)
		if(ask.maze[i]!=e.maze[i])
			return 0;
    return 1;
}

/*******************判断两个数组是否相等****************************/
int mazeequal(int maze1[],int maze2[])
{
	int i;
	for(i=0;i<9;i++)
	{
		if(maze1[i]!=maze2[i])
			return 0;
	}
	return 1;
}

/*****************从链表中找出与结构体e的数码阵相同的结点*************/
//表为空或未找到相应结点都返回结构体e自身
ElemType getelem(linklist l,ElemType e)
{
	lnode *q;	
	if(l->next==NULL)
		return e;  //返回自身

	q=l->next;	
	while(q!=NULL)
	{
		if(Isequal(q->data,e)==1)
			break;		
		q=q->next;
	}
	if(q==NULL)	
		return e;	
	else
		return q->data;    
}

/**************************插入元素到表头****************************/
void insertlist(linklist &l ,ElemType e)
{ 
	lnode* s;
	s=(lnode *)malloc(sizeof(lnode));
	if(!s)exit(0);
	s->data=fuzhi(e);
	s->next=l->next;
	l->next=s;
}

/******************************删除元素e*****************************/
void  deletelist(linklist &l,ElemType e)
{
	lnode *p,*q;
	p=l;	
	if (l->next==NULL)//对空表作事先判断
	{
	    printf("此表为空!");
	    exit(0);	
    }			
	while(p->next!=NULL)//找删除位置
	{
		q=p;
		p=p->next;
		if(Isequal(p->data,e)==1)
		{
			q->next=p->next;
			break;
		}
	}
	return;
}

/****************************输出结构体*******************************/
void Print(ElemType e)
{
	int i;
	for(i=0;i<9;i++)
	{
		if(e.maze[i]==0)
			cout<<"   ";
		else 
			cout<<e.maze[i]<<"  ";
		if(i%3==2)	cout<<endl;
	}
	cout<<endl<<endl;
	Sleep(200);
}

/*****************************输出链表中元素*****************************/
void printlist(linklist l)
{
   lnode *p;   
   if (l->next==NULL)
   {
	    printf("此表为空!");
	    exit(0);
   }   
   for(p=l->next;p!=NULL;p=p->next)
	   Print(p->data);
}

/**************************返回数码阵空格所在位置************************/
void Evaluate_locate0(ElemType &e)
{
	int i;
	for(i=0;i<9;i++)
		if(e.maze[i]==0)
			e.locate0 = i;
}

/********************************计算f函数*******************************/
void Evaluate_f(ElemType &e)
{
	e.h=0;
	int i;
	for(i=0;i<9;i++)
	{
		if(aim.maze[i]!=0)
			if(aim.maze[i]!=e.maze[i])
				e.h++;
	}
	e.f = e.g + e.h;
}

/*****************************在Open表中查找f函数最小的结点***************/
ElemType GetMin(linklist &Open)
{
	lnode* temp=Open->next;
	lnode* min=temp;
	while(temp->next!=NULL)
	{
		temp=temp->next ;
		if(temp->data.f <min->data.f )
			min=temp;
	}
	return min->data;
}

/********************************将结点从Open表移到Close表******************/
void Open_to_Close(linklist &Open,linklist &Close,ElemType e)
{
	deletelist(Open,e);
	insertlist(Close,e);
}


/*********************************将扩展的结点移入Open表********************/
void Open_insert(linklist &Open,linklist &Close,ElemType e)
{
	//判断Open表中是否已存在
	struct ElemType getClose;
	struct ElemType getOpen;

	getOpen=getelem(Open,e);
	getClose=getelem(Close,e);

	if(getOpen.f!=e.f)  //Open表中存在同样数码的结点，则当新的结点f函数小于原来的f函数时，替代原来的
	{
		if(e.f < getOpen.f)
		{
			deletelist(Open,e);
			insertlist(Open,e);
		}
	}

	//Open表中不存在该元素，判断Close表中是否已存在
	else if(getClose.f!=e.f)
	{
		if(e.f < getClose.f)//Close表中存在同样数码的结点，则当新的结点f函数小于原来的f函数时，将Close表中的结点移回Open表
		{
			deletelist(Close,e);
			insertlist(Open,e);
		}
	}

	else insertlist(Open,e);
}

/***********************拓展结点********************************************/
ElemType Move(linklist &Open,linklist &Close,ElemType original,int direct)
{
	struct ElemType result;
	result=fuzhi(original);
	Evaluate_locate0 (original);
	int i=original.locate0;
    switch(direct)
	{
	case 1: //left
		if(i %3 != 0)
		{
			result.maze[i] = result.maze[i-1];
			result.maze[i-1] = 0;
		}
		break;

	case 2:  //up
		if(i > 2) 
		{
			result.maze[i] = result.maze[i-3];
			result.maze[i-3] = 0;
		}
		break;

	case 3:  //right
		if(i%3 != 2) 
		{
			result.maze[i] = result.maze[i+1];
			result.maze[i+1] = 0;
		}
		break;

	case 4:  //down
		if(i < 6) 
		{
			result.maze[i] = result.maze[i+3];
			result.maze[i+3] = 0;
		}
		break;
	}

	if(Isequal(result,original)==1)  //没有作移动
		return original;
	else
	{
		result.g=original.g+1;
		Evaluate_locate0(result);
		Evaluate_f (result);
		for(int i = 0; i < 9; i++)
			result.father[i] = original.maze[i];
		Open_insert(Open,Close,result);
		return result;
	}	
}

/*************************************搜索过程***********************************/
ElemType Search(linklist &Open,linklist &Close)
{
	struct ElemType min;
	struct ElemType moveresult;
	int direct;
	while(emptylist(Open)!=1)
	{
		min=GetMin(Open);
		Open_to_Close(Open,Close,min);
		for(direct=1;direct<=4;direct++)
		{
			moveresult=Move(Open,Close,min,direct);
			if(Isequal(moveresult,aim)==1)
				return moveresult;
		}
	}
	cout<<"No solution!"<<endl;
	exit(0);
}

/***********************************判断八数码问题是否可解********************/
int Ifsolvable(int init[],int aim[])
{
	int sum1=0,sum2=0;
	int f1[9],f2[9];
	int i,j;
	for(i=0;i<9;i++)
	{
		int temp1,temp2;
		temp1=init[i];
		temp2=aim[i];
		f1[temp1]=0;
		f2[temp2]=0;
		for(j=0;j<i;j++)
		{
			if(init[j]!=0 && init[j]<temp1)
				f1[temp1]++;
			if(aim[j]!=0 && aim[j]<temp2)
				f2[temp2]++;
		}
		sum1+=f1[temp1];
		sum2+=f2[temp2];
	}
	if(sum1%2==sum2%2)return 1;
	else return 0;
}

/******************************************************************************************************
											end
*******************************************************************************************************/