实现了深度，广度，启发式搜索，启发函数为F=G*X+H*Y型
注意问题 ：1.对已搜索的节点，不能简单的认为以后不需要搜索了，因为我们实际上是限定了搜索的深度的，在不容层上的即使局面一样，也不能简单的认为不需再往下搜索了。如果没有限定深度，这样假设是正确的。对于局面一样，且深度不小于已搜索的局面，可以直接剪裁掉，不需要搜索。
eight.h文件
#include <stdio.h>
#include <stdlib.h>
/*
by shaoxp@zju.edu.cn at 05-10-17
作为人工智能作业
*/
struct neightNode//深度，和广度搜索用的节点
{
int *state;//一种棋局
int depth;//该棋局所在的深度
int weight;//启发式搜索时用的，启发值
};
struct neightNodeLinkNode
{
struct neightNode *pneightNode;
struct neightNodeLinkNode *next;
};
eight.c文件
/*
by shaoxp@zju.edu.cn at 05-10-17
作为人工智能作业
*/
#include "eightNormal.h"
/*数码问题,0表示空位*/
static struct neightNodeLinkNode *searchLink;
static struct neightNodeLinkNode *phead,*ptail;
static struct neightNode *begin,*end,*curr;
static int neight;//neight数码问题
static int searchstep;
static int maxDepth;
static FILE * pf;//文件输出
static int searchPolicy;/*0 深度 1 广度 2 启发式*/
static int illumType,illumX,illumY;/*当启发式搜索时，该变量有用*/
static void initEight(int n,const int *startStat,const int *endStat,int maxD,FILE *pout)//n=3时，为8数码问题
{
neight=n;
maxDepth=maxD;
pf=pout;
if(pf==NULL)
pf=fopen("out.txt","w");
begin=(struct neightNode *)malloc(sizeof(struct neightNode));
end=(struct neightNode *)malloc(sizeof(struct neightNode));//为了后面回收方便
begin->state=(int *)malloc(n*n*sizeof(int));
end->state=(int *)malloc(n*n*sizeof(int));
for(int i=0;i<n*n;i++)
{
begin->state[i]=startStat[i];
begin->depth=1;
end->state[i]=endStat[i];
}
curr=begin;
searchstep=1;
searchLink=(struct neightNodeLinkNode*)malloc(sizeof(struct neightNodeLinkNode));
searchLink->pneightNode=curr;
searchLink->next=NULL;
phead=ptail=searchLink;
}
static int cmpStat(neightNode node1,neightNode node2)
{
for(int i=0;i<neight*neight;i++)
if(node1.state [i]!=node2.state[i])
return 1;
return 0;
}
static void cpyStat(neightNode *s,neightNode cd)
{
for(int i=0;i<neight*neight;i++)
s->state[i]=cd.state[i];
s->depth=cd.depth;
}
static void illum(int type,int x,int y,struct neightNode *pwillIllum);
static int dirMoveHole(int i,int j,int dir)
{
if(curr==NULL)
return -1;
neightNode node;
node.state=(int *)malloc(neight*neight*sizeof(int));/*可以优化一下*/
cpyStat(&node,*curr);
switch(dir)
{
case 4:
(node.state[i*neight+j])^=(node.state[(i-1)*neight+j])^=(node.state[i*neight+j])^=(node.state[(i-1)*neight+j]);//空移动
break;
case 3:
(node.state[i*neight+j])^=(node.state[i*neight+j-1])^=(node.state[i*neight+j])^=(node.state[i*neight+j-1]);
break;
case 2:
(node.state[i*neight+j])^=(node.state[(i+1)*neight+j])^=(node.state[i*neight+j])^=(node.state[(i+1)*neight+j]);
break;
case 1:
(node.state[i*neight+j])^=(node.state[i*neight+j+1])^=(node.state[i*neight+j])^=(node.state[i*neight+j+1]);
break;
}
struct neightNodeLinkNode *p=searchLink;
int haveCheck=0;
while(p!=phead)//察看是不是已经检查过,对已检查过深度要求不小于未检查过的，才不予考虑
{
if(!cmpStat(node,*(p->pneightNode))&&(node.depth>=p->pneightNode->depth))
{
haveCheck=1;
break;
}
p=p->next;
}
if(haveCheck!=1)//没,需要加入到待检查的队列中
{
struct neightNode *pstatNode = (struct neightNode*)malloc(sizeof(struct neightNode));
pstatNode->state=(int *)malloc(neight*neight*sizeof(int));
cpyStat(pstatNode,node);
(pstatNode->depth)++;
struct neightNodeLinkNode *plinkNode =(struct neightNodeLinkNode*)malloc(sizeof(struct neightNodeLinkNode));
plinkNode->pneightNode=pstatNode;
if(searchPolicy==0)//深度
{
plinkNode->next=phead->next;
phead->next=plinkNode;
}
else if(searchPolicy==1)//广度,需要从后面添加
{
plinkNode->next=NULL;
ptail->next =plinkNode;
ptail=plinkNode;
}
else
{
illum(illumType,illumX,illumY,pstatNode);
struct neightNodeLinkNode *q=p;
struct neightNodeLinkNode *p=phead->next;
while(p!=NULL&&p->pneightNode->weight<plinkNode->pneightNode->weight)
{
q=p;
p=p->next;
}
plinkNode->next=q->next;
q->next=plinkNode;
}
}
free(node.state);
return 0;
}
static int moveHole(int i,int j)
{
if(curr==NULL)
return -1;
if(searchPolicy==0)//深度
{
if(i!=0)
dirMoveHole(i,j,4);//north
if(j!=0)
dirMoveHole(i,j,3);//west
if(i!=neight-1)
dirMoveHole(i,j,2);//south
if(j!=neight-1)
dirMoveHole(i,j,1);//east
}
else //广度和启发搜索
{
if(j!=neight-1)
dirMoveHole(i,j,1);//east
if(i!=neight-1)
dirMoveHole(i,j,2);//south
if(j!=0)
dirMoveHole(i,j,3);//west
if(i!=0)
dirMoveHole(i,j,4);//north
}
return 0;
}
static int ifind(int fi,int *stat)
{
for(int i=0;i<neight*neight;i++)
if(stat[i]==fi)
return i;
printf("error\n");
exit(0);
}
static int generateNextMove()/*从状态CURR生成可能的后续状态，空格按东南西北(1234)的顺序移动，如果碰到已经测试的状态，则忽略*/
{
if(curr==NULL)
return -1;
if(curr->depth==maxDepth)//如已经到达最大深度,不往下搜索
return 0;
int n=ifind(0,curr->state);
int i,j;
i=n/neight;
j=n%neight;
moveHole(i,j);//从i,j处按东南西北的方向移动空
return 0;
}
static int moveNextStep()
{
if(curr==NULL)
return -1;
generateNextMove();//从curr状态生成可能的后续状态,放到链searchLink中
phead=phead->next;
if(phead!=NULL)
{
curr=phead->pneightNode;
searchstep++;
}
else
curr=NULL;
return 0;
}
static int success()
{
return !cmpStat(*curr,*end);
}
static int eeof()
{
return curr==NULL;
}
static void print()
{
printf("STEP %d ON DEPTH %d:\n",searchstep,curr->depth);
fprintf(pf,"STEP %d ON DEPTH %d:\n",searchstep,curr->depth);
for(int i=0;i<neight;i++)
{
for(int j=0;j<neight;j++)
{
printf("%d ",curr->state[i*neight+j]);
fprintf(pf,"%d ",curr->state[i*neight+j]);
}
printf("\n");
fprintf(pf,"\n");
}
}
static void saveMem()
{
struct neightNodeLinkNode *p=searchLink;
struct neightNodeLinkNode *q;
while(p!=NULL)
{
q=p->next;
free(p->pneightNode->state);
free(p->pneightNode);
free(p);
p=q;
}
}
void df(int n, const int *startStat, const int *endStat,int maxD,FILE *pout)//深度搜索从startStat到endStat的n*n-1数码问题，maxD为最大深度
{
initEight(n,startStat,endStat,maxD,pout);
searchPolicy=0;
while(!eeof()&&!success())
{
print();
moveNextStep();
}
if(!eeof())
{
print();
printf("SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
}
else
{
printf("FAILURE AT DEPTH %d\n",maxDepth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"FAILURE AT DEPTH %d\n",maxDepth);
}
saveMem();
}
void bf(int n,const int *startStat,const int *endStat,int maxD,FILE *pout)//广度搜索从startStat到endStat的n*n-1数码问题，maxD为最大深度
{
initEight(n,startStat,endStat,maxD,pout);
searchPolicy=1;
while(!eeof()&&!success())
{
print();
moveNextStep();
}
if(!eeof())
{
print();
printf("SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
}
else
{
printf("FAILURE AT DEPTH %d\n",maxDepth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"FAILURE AT DEPTH %d\n",maxDepth);
}
saveMem();
}
static int countDiff(int *p1,int *p2)
{
int count=0;
for(int i=0;i<neight*neight;i++)
if(p1[i]!=p2[i])
count++;
return count;
}
static int countShortestSum(int *p1,int *endStat)
{
int sum=0;
for(int i=0;i<neight*neight;i++)
{
int n=ifind(p1[i],endStat);
sum+=(abs(n/neight-i/neight)+abs((n%neight)-(i%neight)));
}
return sum;
}
static void illum(int type,int x,int y,struct neightNode *pwillIllum)//启发函数，启发函数的形式为f=g*x+h*y，其中x，y表示g,h分别所占的权重
/*type:
1: g表示深度，h表示pwillIllum状态中放错位置的节点总数
2: g表示深度，h表示pwillIllum状态中各数字现在所处的位置和正确的位置最短距离的总和
*/
{
if(pwillIllum!=NULL)
{
switch(type)
{
case 1:
int diff;
diff=countDiff(pwillIllum->state ,end->state);
pwillIllum->weight=pwillIllum->depth*x+diff*y;//计算启发函数
break;
case 2:
int shortestSum;
shortestSum=countShortestSum(pwillIllum->state,end->state);
pwillIllum->weight=pwillIllum->depth*x+shortestSum*y;
break;
}
}
}
void ill(int n,const int *startStat,const int *endStat,int maxD,int illtype,int illx,int illy,FILE *pout)//启发式搜索,
{
initEight(n,startStat,endStat,maxD,pout);
searchPolicy=2;
illumType=illtype;
illumX=illx;
illumY=illy;
while(!eeof()&&!success())
{
print();
moveNextStep();
}
if(!eeof())
{
print();
printf("SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"SUCCESS AT %dth on depth %d\n",searchstep,curr->depth);
}
else
{
printf("FAILURE AT DEPTH %d\n",maxDepth);
printf("结果同样输出到out.txt文件了\n");
fprintf(pf,"FAILURE AT DEPTH %d\n",maxDepth);
}
saveMem();
}
