guangdu.cpp

人工智能中的广度优先搜索算法

#include<stdio.h>
#include<conio.h>
#include<windows.h>

typedef struct shuma
{
int number[3][3];/*存放八数码的数组*/
char operate;/*存储不可以进行的操作*/
char extend;/*存储是否可以扩展*/
int  father;/*指向产生自身的父结点*/
}shuma;

int s0[3][3]={{2,8,3},{1,0,4},{7,6,5}};/*设定初始状态*/ 
int sg[3][3]={{1,2,3},{8,0,4},{7,6,5}};/*设定目标状态*/
shuma open[1000];  /*存放open表中的节点*/
int result[100];/*存放最优路径的数组下标号，逆序存放*/
int m,n;
/*******************判断是否达到目标状态******************/
int match()
{int i,j;
 for(i=0;i<3;i++)
{ for(j=0;j<3;j++)
{
  if(open[n-1].number[i][j]!=sg[i][j])   //如果达到目标状态则返回1，否则返回0
  {   return 0;  }
}}

return 1;}

/************输出最优路径的各个状态****************/
void showway()
{
int i=0;
while(m>=0)
{
  int mm=result[m];         //根据父节点，依次输出最有路径上的各个节点
  printf("\n S%d",i);
  printf("\n\t\t%d\t%d\t%d\n",open[mm].number[0][0],open[mm].number[0][1],open[mm].number[0][2]);
  printf("\n\t\t%d\t%d\t%d\n",open[mm].number[1][0],open[mm].number[1][1],open[mm].number[1][2]);
  printf("\n\t\t%d\t%d\t%d\n",open[mm].number[2][0],open[mm].number[2][1],open[mm].number[2][2]);
  //Sleep(1000);
  m--;
  i++;
}
}
/*********************达到目标状态后，找到最优路径**********/
void solve()
{
n--;
m=0;
result[0]=n;
while(open[n].father!=-1) //用result数组存放最优路径上的各个节点
{
  result[m]=n;
  m++;
  n=open[n].father;
}
result[m]=0;
showway();    //调用输出函数
printf("\n\n\n\n\n\n\n\n\n\t\t\t\tfinish\n\n\n\n\n\n\n\n\n\n");
exit(0);
}
/******************************空格左移*******************/
int left(int x)
{
int i,j,hang,lie;
int middle;
for(i=0;i<3;i++)
{for (j=0;j<3;j++)
{if(open[x].number[i][j]==0)
{  hang=i;
   lie=j;	  //判断空格所在的行位置和列位置 
   break;}
}}
if(lie==0)
{
  return 0;
}
for (i=0;i<3;i++)
{for(j=0;j<3;j++)
{
open[n].number[i][j]=open[x].number[i][j];
}}

middle=open[n].number[hang][lie-1];
open[n].number[hang][lie-1]=open[n].number[hang][lie]; //空格左移
open[n].number[hang][lie]=middle;
open[n].operate='R';   //扩展节点不包括父节点
open[n].extend='Y';
open[n].father=x;     //存放父节点指针

open[x].extend='N';  //已经扩展的节点不再扩展
n++;
if(match())
solve();       //判断是否达到目标状态
return 1;
}
/****************空格右移*********************/
int right(int x)
{
int i,j,hang,lie;
int middle;
for (i=0;i<3;i++)
{for(j=0;j<3;j++)
{
  if(open[x].number[i][j]==0)    //判断空格所在的行位置和列位置 
  {hang=i;
   lie=j;
   break;}
}}
if(lie==2)
{
  return 0;
}
for (i=0;i<3;i++)
{for(j=0;j<3;j++)
{
  open[n].number[i][j]=open[x].number[i][j];
}}

middle=open[n].number[hang][lie+1];
open[n].number[hang][lie+1]=open[n].number[hang][lie];  //空格右移
open[n].number[hang][lie]=middle;
open[n].operate='L';
open[n].extend='Y';
open[n].father=x;
open[x].extend='N';
n++;
if(match())   //判断是否达到目标状态
solve();
return 1;
}
/************空格上移子程序**********/
int up(int x)
{
int i,j,hang,lie;
int middle;
for(i=0;i<3;i++)
{
{ for (j=0;j<3;j++)
{ if(open[x].number[i][j]==0)    //判断空格所在的行位置和列位置 
   {hang=i;  
    lie=j;
	break;}
}}}
if(hang==0)
{
  return 0;
}
for (i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
  open[n].number[i][j]=open[x].number[i][j];   
}}


middle=open[n].number[hang-1][lie];
open[n].number[hang-1][lie]=open[n].number[hang][lie];  //空格上移
open[n].number[hang][lie]=middle; 
open[n].operate='D';
open[n].extend='Y';
open[n].father=x;
open[x].extend='N';

n++;
if(match())    //判断是否达到目标状态
solve();
return 1;
}
/***********空格下移子程序*************/
int down(int x)
{
int i,j,hang,lie;
int middle;
for(i=0;i<3;i++)
{for (j=0;j<3;j++)
{
  if(open[x].number[i]==0)    //判断空格所在的行位置和列位置 
  {hang=i; 
   lie=j;
   break;}
}}
if(hang==2)
{
  return 0;
}

for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
  open[n].number[i][j]=open[x].number[i][j];
}}

middle=open[n].number[hang+1][lie];
open[n].number[hang+1][lie]=open[n].number[hang][lie];  //空格下移
open[n].number[hang][lie]=middle;
open[n].operate='U';
open[n].extend='Y';
open[n].father=x;

open[x].extend='N';
n++;
if(match())   //判断是否达到目标状态
solve();
return 1;
}
void main()
{
int i,j;
n=1;
for(i=0;i<3;i++)
{for(j=0;j<3;j++) 
{open[0].number[i][j]=s0[i][j];}    //初始状态存放到open表中
}
open[0].operate='N';    //初始状态空格上下左右移动皆可
open[0].extend='Y';
open[0].father=-1;

for(i=0;i<1000;i++)
{
  if(open[i].extend=='Y')    //判断节点是否可以扩展
  {
   if(open[i].operate=='L')  //空格不可左移的话则执行其他操作
   {
    right(i);up(i);down(i);
   }
   if(open[i].operate=='R') //空格不可右移的话则执行其他操作
   {
    left(i);up(i);down(i);
   }
   if(open[i].operate=='U') //空格不可上移的话则执行其他操作
   {
    left(i);right(i);down(i);
   }
   if(open[i].operate=='D')  //空格不可下移的话则执行其他操作
   {
    left(i);right(i);up(i);
   }
   if(open[i].operate=='N') //所有操作皆可执行
   {
    left(i);right(i);up(i);down(i);
   }
  }
}
}