#include<stdio.h>
#include <iostream>
#include <vector>
#define R 3
#define error 0
#define overflow 0
using namespace std;
const int max_pace = 10000;
const int max_num = 10000;
typedef struct NODE
{
int arr[R][R]; //保存当前八数码状态的数组
int dist; //当前状态到目标状态的距离
int depth; //当前节点的深度
int index; //指向父节点
}Node;
typedef struct
{
int pattern[R][R];
}Digit;
typedef struct ANODE
{
int f,g,h; //f为估计函数,g=depth,为当前状态节点的深度,h=dist,为当前状态节点距目标状态的距离,f=g+h.
Digit data;
struct ANODE *children[4];
struct ANODE *parent;
struct ANODE *next;
}Anode;
typedef struct Stack
{
Anode *data;
struct Stack *next;
}stack;
Anode *Open,*Close;
stack *Sstack;
void InitStack(stack **h) //初始化存储父节点的栈
{
(*h)=(stack *)malloc(sizeof(stack));
(*h)->next=NULL;
}
void Push(stack *s,Anode *father) //将父节点入栈
{
stack *q;
q=(stack *)malloc(sizeof(stack));
q->data=father;
q->next=s->next;
s->next=q;
}
Anode *Pop(stack *h) //将父节点出栈
{
Anode *e;
stack *top;
e=h->next->data;
top=h->next;
h->next=top->next;
free(top);
return e;
}
void Init_Open(Anode **open) //初始化OPEN表
{
*open=(Anode *)malloc(sizeof(Anode));
if(*open == NULL)
{
printf("内存分配失败!\n");
exit(overflow);
}
(*open)->next = NULL;
}
void Insert_Open(Anode *top,Anode *open) //向OPEN中输入元素
{
top->next=open->next;
open->next=top;
}
void Init_Close(Anode **close) //初始化CLOSE表
{
*close=(Anode *)malloc(sizeof(Anode));
if(*close == NULL)
{
printf("内存分配失败!\n");
exit(overflow);
}
(*close)->next=NULL;
}
void Insert_Close(Anode *top,Anode *close) //向CLOSE表中输入元素
{
top->next = close->next;
close->next = top;
}
int Compare(int a[R][R],int **b)
{
int i,j;
for(i=0;i<R;i++)
{
for(j=0;j<R;j++)
{
if(a[i][j]!=b[i][j])
return 0;
}
}
return 1;
}
void Sort_Open(Anode *head) //对OPEN表中的估价值进行排序
{
Anode *p,*q,*temp,*l;
q=head->next;
p=q->next;
q->next=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
temp=head;
l=head->next;
while(temp->next!=NULL && (q->f >= l->f))
{
temp=l;
l=l->next;
}
q->next=temp->next;
temp->next=q;
}
}
Anode * Pop_Open(Anode *top) //将OPEN表元素输出
{
Anode *q;
if(!top->next)
{
printf("出错！此栈为空栈！\n");
return error;
}
q = top->next;
top->next = q->next;
return q;
}
Anode * Check_Open(Anode *open,int **s) //检查子节点是否在OPEN表中
{
Anode *p;
p=open->next;
while(p!=NULL)
{
if(Compare(p->data.pattern,s) == 1)
{
return p;
}
p=p->next;
}
return NULL;
}
Anode * Check_Close(Anode *close,int **s) //检查子节点是否在CLOSE表中
{
Anode *p;
p=close->next;
while(p!=NULL)
{
if(Compare(p->data.pattern,s) == 1)
{
return p;
}
p=p->next;
}
return NULL;
}
Node src,dest; //src为八数码初始状态节点,dest为八数码目标状态节点
vector<Node> open,close; //创建open,close两个存储结点
bool IsEmpty_open() //判断OPEN表是否为空
{
int i;
for(i=0;i<open.size();i++)
{
if(open[i].dist!= max_num)
return false;
}
return false;
}
bool IsEqual(int index, int arr[][R]) //判断两个八数码状态是否一样
{
int i,j;
for(i=0;i<R;i++)
for(j=0;j<R;j++)
{
if(open[index].arr[i][j]!=arr[i][j])
return false;
}
return true;
}
ostream& operator<<(ostream& os, Node& node)
{
int i,j;
for(i=0;i<R;i++)
{
for(j=0;j<R;j++)
os<< node.arr[i][j] << ' ';
os<<endl;
}
return os;
}
void Print_steps(int index,vector<Node>& close) //输出打印路径步骤
{
int i;
close.push_back(open[index]);
index=open[index].index;
while(index != 0)
{
close.push_back(open[index]);
index = open[index].index;
}
for(i=close.size()-1;i>= 0;i--)
cout <<"第"<< close.size()-i<<"步:"<<endl<< close[i]<<endl;
}
int Search_min() //得出可扩展节点中的最小估价值节点
{
int i,min,f=max_num;
for(i=0;i<open.size();i++)
{
if(open[i].dist==max_num)
continue;
else if((open[i].dist+open[i].depth)<f)
{
f=open[i].dist+open[i].depth;
min=i;
}
}
return min;
}
bool IsExpandable(Node& node) //判断节点是否可扩展
{
int i;
for(i=0;i<open.size();i++)
{
if(IsEqual(i,node.arr))
return false;
}
return true;
}
int Distance(Node& node, int arr[][R]) //计算八数码当前状态与目标状态距离
{
int dist=0,temp=0,i,j,m,n;
for(i=0;i<R;i++)
for(j=0;j<R;j++)
for(m=0;m<R;m++)
{
for(n=0;n<R;n++)
{
if (node.arr[i][j]==arr[m][n])
{
dist=dist+abs(i-m)+abs(j-n);
temp=1;
break;
}
else
temp=0;
}
if(temp)
break;
}
return dist;
}
bool Have_ans(int arr1[][3],int arr2[][3])
{
int i,j,m=0,n=0;
int a[8],b[8],count1=0,count2=0;
for(i=0;i<R;i++)
for(j=0;j<R;j++)
{
if(arr1[i][j]!=0)
a[m++]=arr1[i][j];
if(arr2[i][j]!=0)
b[n++]=arr2[i][j];
}
for(i=0;i<7;i++)
for(j=i+1;j<8;j++)
{
if(a[j]<a[i])
count1++;
if(b[j]<b[i])
count2++;
}
if((count1 % 2==count2 % 2))
return true;
else
return false;
}
void Search_path(int index) //进行搜索
{
int i=0,j=0,x,y,temp,du,dd,dr,dl; //temp为临时变量,d*为向上下左右移动后的距离dist
Node nu,nd,nr,nl; //n*为向上下左右移动后的八数码状态节点
du=dd=dr=dl=max_pace;
for(i=0;i<R;i++)
{
for(j=0;j<R;j++)
{
if(open[index].arr[i][j]==0)
{
x=i; y=j; temp=1;
break;
}
else temp=0;;
}
if(temp)
break;
}
//--------------------节点上移----------------------
for(i=0;i<R;i++)
for(j=0;j<R;j++)
nu.arr[i][j]=open[index].arr[i][j];
if(x>0)
{
temp=nu.arr[x][y];
nu.arr[x][y]=nu.arr[x-1][y];
nu.arr[x-1][y]=temp;
if(IsExpandable(nu))
{
du=Distance(nu,dest.arr);
nu.index=index;
nu.dist= du;
nu.depth=open[index].depth + 1;
open.push_back(nu);
}
}
//--------------------节点下移----------------------
for(i=0;i<R;i++)
for(j=0;j<R;j++)
nd.arr[i][j] = open[index].arr[i][j];
if(x<2)
{
temp=nd.arr[x][y];
nd.arr[x][y]=nd.arr[x+1][y];
nd.arr[x+1][y]=temp;
if(IsExpandable(nd))
{
dd=Distance(nd,dest.arr);
nd.index=index;
nd.dist=dd;
nd.depth=open[index].depth + 1;
open.push_back(nd);
}
}
//--------------------节点左移----------------------
for(i=0;i<R;i++)
for(j=0;j<R;j++)
nl.arr[i][j]=open[index].arr[i][j];
if(y>0)
{
temp=nl.arr[x][y];
nl.arr[x][y]=nl.arr[x][y-1];
nl.arr[x][y-1]=temp;
if(IsExpandable(nl))
{
dl=Distance(nl,dest.arr);
nl.index = index;
nl.dist=dl;
nl.depth=open[index].depth + 1;
open.push_back(nl);
}
}
//--------------------节点右移----------------------
for(i=0;i<R;i++)
for(j=0;j<R;j++)
nr.arr[i][j]=open[index].arr[i][j];
if(y<2)
{
temp=nr.arr[x][y];
nr.arr[x][y]=nr.arr[x][y+1];
nr.arr[x][y+1]=temp;
if(IsExpandable( nr))
{
dr=Distance(nr,dest.arr);
nr.index=index;
nr.dist=dr ;
nr.depth=open[index].depth + 1;
open.push_back
- 1
- 2
前往页