启发式搜素.cpp

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估

#include<stdio.h>
int n,n1;//n是结构open的指针,n1是结构close的指针都代表结构当前位置
int w=0;
char start[10];//存放初始数码
char end[9]={'1','2','3','8','0','4','7','6','5'};//目标数码
typedef struct op
{ char shuma[9];
  char operation;
 int length;
 int father;
 int farth;
}op;
op open[2000];
 typedef struct cl
{char shuma[9];
  char operation;
 int length;
 int father;
 int farth;
}cl;
cl close[1000];

int dif(int n5)//计算与目标数码差距的函数
{int n7;
n7=0;
for(int n6=0;n6<9;n6++)
{if(open[n5].shuma[n6]!=end[n6]&&open[n5].shuma[n5]!='0')
 n7++;
}
return n7;
}

void match(int n7)//比较函数
{int n6=0;
int n8,n9;
int result[60];
while(n6<9)
{if(open[n7].shuma[n6]!=end[n6])
 return;
 n6++;
}
  n8=open[n7].father;
n9=0;
result[n9]=n8;
n9++;
while(close[n8].father!=-1)
{
	result[n9]=close[n8].father;
	n9++;
 n8=close[n8].father;
 }
n9--;
while(n9>=0)
{n8=result[n9];
printf("\n\t%c\t%c\t%c\n",close[n8].shuma[0],close[n8].shuma[1],close[n8].shuma[2]);
printf("\n\t%c\t%c\t%c\n",close[n8].shuma[3],close[n8].shuma[4],close[n8].shuma[5]);
printf("\n\t%c\t%c\t%c\n",close[n8].shuma[6],close[n8].shuma[7],close[n8].shuma[8]);
printf("\n\n\n");
n9--;}
printf("\n\t%c\t%c\t%c\n",open[n7].shuma[0],open[n7].shuma[1],open[n7].shuma[2]);
printf("\n\t%c\t%c\t%c\n",open[n7].shuma[3],open[n7].shuma[4],open[n7].shuma[5]);
printf("\n\t%c\t%c\t%c\n",open[n7].shuma[6],open[n7].shuma[7],open[n7].shuma[8]);
printf("\n\n\n");
w++;
}


void match2(int n5)//函数  判断新生成节点是不是存在于open或close中，并进行相应操作。
{int n6;
for(n6=0;n6<n;n6++)
{if(open[n6].shuma[0]==open[n5].shuma[0]&&open[n6].shuma[1]==open[n5].shuma[1]&&open[n6].shuma[2]==open[n5].shuma[2]&&open[n6].shuma[3]==open[n5].shuma[3]&&open[n6].shuma[4]==open[n5].shuma[4]
   &&open[n6].shuma[5]==open[n5].shuma[5]&&open[n6].shuma[6]==open[n5].shuma[6]&&open[n6].shuma[7]==open[n5].shuma[7]&&open[n6].shuma[8]==open[n5].shuma[8])
{if(open[n6].farth==1000)
  open[n6].farth=open[n5].farth;
 else 
	{ if(open[n6].farth<open[n5].farth)
	{}
    else 
		open[n6].farth=open[n5].farth;
	}
 n--;}
}
}



void left(int n5)//以0为标志 左移操作函数
{int n3,n4;
n3=0;
while(close[n5].shuma[n3]!='0')
{n3++;}
if(n3==0||n3==3||n3==6)
{return;}
for(n4=0;n4<9;n4++)
{open[n].shuma[n4]=close[n5].shuma[n4];}
open[n].shuma[n3]=open[n].shuma[n3-1];
open[n].shuma[n3-1]='0';
open[n].father=n5;
open[n].operation='L';
open[n].length=1+close[n5].length;
open[n].farth=open[n].length+dif(n);
match(n);
match2(n);
n++;
}

void right(int n5)
{int n3,n4;
n3=0;
while(close[n5].shuma[n3]!='0')
{n3++;}
if(n3==2||n3==5||n3==8)
{return;}
for(n4=0;n4<9;n4++)
{open[n].shuma[n4]=close[n5].shuma[n4];}
open[n].shuma[n3]=open[n].shuma[n3+1];
open[n].shuma[n3+1]='0';
open[n].father=n5;
open[n].operation='R';
open[n].length=1+close[n5].length;
open[n].farth=open[n].length+dif(n);
match(n);
match2(n);
n++;
}

void up(int n5)
{int n3,n4;//n3 代表0的位置
n3=0;
while(close[n5].shuma[n3]!='0')
{n3++;}
if(n3==0||n3==1||n3==2)
{return;}
for(n4=0;n4<9;n4++)
{open[n].shuma[n4]=close[n5].shuma[n4];}
open[n].shuma[n3]=open[n].shuma[n3-3];
open[n].shuma[n3-3]='0';
open[n].father=n5;
open[n].operation='U';
open[n].length=1+close[n5].length;
open[n].farth=open[n].length+dif(n);
match(n);
match2(n);
n++;
}

void down(int n5)
{int n3,n4;//n3 代表0的位置
n3=0;
while(close[n5].shuma[n3]!='0')
{n3++;}
if(n3==6||n3==7||n3==8)
{return;}
for(n4=0;n4<9;n4++)
{open[n].shuma[n4]=close[n5].shuma[n4];}
open[n].shuma[n3]=open[n].shuma[n3+3];
open[n].shuma[n3+3]='0';
open[n].father=n5;
open[n].operation='D';
open[n].length=1+close[n5].length;
open[n].farth=open[n].length+dif(n);
match(n);
match2(n);
n++;
}

void main()
{int n8,n9;
int min;
n=0;
n9=0;
n1=1;
printf("输入字符串，以0代表空格格式如：283164705+回车:\n");
scanf("%s",start);
if(start[0]==end[0]&&start[1]==end[1]&&start[2]==end[2]&&start[3]==end[3]&&start[4]==end[4]&&start[5]==end[5]&&start[6]==end[6]&&start[7]==end[7]&&start[8]==end[8])
{printf("输入的数码就是所求数码\n");
 return;}
for(n8=0;n8<9;n8++)
{if(start[n8]!=end[n8]&&start[n8]!='0')
  n9++;
}
for(int n3=0;n3<9;n3++)//设置初始值，存在close中
{close[1].shuma[n3]=start[n3];}
close[1].operation='N';
close[1].father=-1;
close[1].length=0;
close[1].farth=n9;

while((n<2000)&&(n1<1000))
{
if(close[n1].operation=='L')
{  left(n1);
if(w)
return;
 up(n1);
if(w)
return;
 down(n1);
if(w)
return;
}
if(close[n1].operation=='R')
{ right(n1);
if(w)
return;
up(n1);
if(w)
return;
down(n1);
if(w)
return;}

if(close[n1].operation=='U')
 {up(n1);
if(w)
return;
right(n1);
if(w)
return;
left(n1);
if(w)
return;}
 
if(close[n1].operation=='D')
 {left(n1);
if(w)
return;
right(n1);
if(w)
return;
down(n1);
if(w)
return;
}
if(close[n1].operation=='N')
 {right(n1);
if(w)
return;
up(n1);
if(w)
return;
down(n1);
if(w)
return;
left(n1);
if(w)
return;
}

min=open[0].farth;//寻找farth最小的节点
n9=0;
for(n8=0;n8<n;n8++)
{
if(open[n8].farth<min)
{min=open[n8].farth;
 n9=n8;}
}
if(min==1000)
return;
n1++;
for(int n3=0;n3<9;n3++)//open表移入close表中，并将寻找到的节点在open表中删除（这里将 farth附一个很大的值使其不起作用）
{close[n1].shuma[n3]=open[n9].shuma[n3];}
close[n1].operation=open[n9].operation;
close[n1].father=open[n9].father;
close[n1].length=open[n9].length;
close[n1].farth=open[n9].farth;
open[n9].farth=1000;
}
printf("\n在规定长度内，不能实现8数码问题\n");
}