人工智能八数码游戏

{
if(The_graph->form[i][j]!=End_graph->form[i][j])
{
valute++;
}
}
}
The_graph->evalue=valute;
return valute;
}
/////////移动数码组
Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph)
实验一：八数码游戏问题
一、八数码游戏问题简介
九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。
问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。
283
12 3
164
84
75
例如：
2
8
3
1
2
3
1
6
4
8
4
7
0
5
7
6
5
(a) 初始状态 (b) 目标状态
图1 八数码问题示意图
1.启发函数设定
由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索围，提高搜索速度。
struct node *parent;//父节点
}Graph;
Graph *Qu[MAX];//队列
Graph *St[MAX];//堆栈
五、实验过程及代码
#include <stdio.h> } //设计了搜索深度围，防止队列存越界
#include <stdlib.h>
#include <time.h>
{
return The_graph;
}
if(CreatNew_graph==1)
{
New_graph=(Graph *)malloc(sizeof(Graph));//生成节点
for(x=0;x<N;x++)
{
for(y=0;y<N;y++)
{
New_graph->form[x][y]=The_graph->form[x][y];//复制数码组
{
HasGetBlank=1;
break;
}
}
if(HasGetBlank==1)
break;
}
//printf("空格位置:%d,%d\n",i,j);
t_i=i;
t_j=j;
//移动空格
switch(Direct)
{
case 1://上
t_i--;
if(t_i<0)
AbleMove=0;
break;
else
{
printf("---------------------\n");
for(i=0;i<N;i++)
{
printf("|\t");
for(j=0;j<N;j++)
{
printf("%d\t",The_graph->form[i][j]);//遍历打印
}
printf("\t|\n");
}
printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示
76 5
（a）初始状态（b）目标状态
图 八数码游戏
二、实验目的
1.熟悉人工智能系统中的问题求解过程；
2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；
3.熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验的思路
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；
f、跳到步骤2；
四、数据结构的设计
数码结构体
typedef struct node//八数码结构体
{
int form[N][N];//数码组
int evalue;//评估值，差距
int udirec;//所屏蔽方向,防止往回推到上一状态,1上2下3左4右
struct node *parent;//父节点
}Graph;
Graph *Qu[MAX]; //队列
Graph *St[MAX]; //堆栈
/////////打印数码组
void Print(Graph *The_graph)
{
int i,j;
if(The_graph==NULL)
printf("图为空\n");
printf("---------------------\n");
}
}
/////////评价函数
int Evaluate(Graph *The_graph,Graph *End_graph)
{
int valute=0;//差距数
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
2.搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））
a、把初始数码组压入队列；
b、从队列中取出一个数码组节点；
c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：
d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。
#define N 3 //数码组大小
#define Max_Step 50 //最大搜索深度
#define MAX 50
typedef struct node//八数码结构体
{
int form[N][N];//数码组
int evalue;//评估值
int udirect;//所屏蔽方向，防止往回推到上已状态，1上2下3左4右
{
Graph *New_graph;
int HasGetBlank=0;//是否获取空格位置
int AbleMove=1;//Байду номын сангаас否可移动
int i,j,t_i,t_j,x,y;
for(i=0;i<N;i++)//获取空格坐标i,j
{
for(j=0;j<N;j++)
{
if(The_graph->form[i][j]==0)
case 2://下
t_i++;
if(t_i>=N)
AbleMove=0;
break;
case 3://左
t_j--;
if(t_j<0)
AbleMove=0;
break;
case 4://右
t_j++;
if(t_j>=N)
AbleMove=0;
break;
}
if(AbleMove==0)//不能移动则返回原节点