C语言解八数码问题之人工智能实验报告
《人工智能》上机实验
基于人工智能的状态空间搜索策略研究
——八数码问题求解
(一)实验软件
TC2.0 或 VC6.0 编程语言或其它编程语言
(二)实验目的
1. 熟悉人工智能系统中的问题求解过程;
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;
3. 熟悉对八数码问题的建模、求解及编程语言的应用。 (三)需要的预备知识
1. 熟悉TC2.0 或 VC6.0 编程语言或者其它编程语言;
2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法;
3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用;
4. 熟悉计算机常用人机接口
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
。
(四)实验数据及步骤
1. 实验内容
八数码问题:在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
2 5 4 1 2 3
3 7 8 4
1 8 6 7 6 5
(a) 初始状态 (b) 目标状态
图1 八数码问题示意图
请任选一种盲目搜索算法(深度优先搜索或宽度优先搜索)或 任选一种启发式搜索方法(A 算法或 A* 算法)编程求解八数码问题(初始状态任选)，并对实验结果进行分析，得出合理的结论。
2. 实验步骤
(1)分析算法基本原理和基本
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
;
程序采用宽度优先搜索算法，基本流程如下:
2
起始
把s放入open表
是 是否open表为失败 空表,
否
把open表中的第一个节点n
移入close表
扩展节点n，把其后裔放入
open表的前头
是 否 是否有后继节点 成功
为目标节点,
3
(2)确定对问题描述的基本数据结构，如 Open 表和 Closed 表等;
OPEN CLOSED S
A,B,C S
B,C,D,E,F S,A
C,D,E,F,G S,A,B D,E,F,G,H S,A,B,C E,F,G,H,I,J S,A,B,C,D F,G,H,I,J K,L S,A,B,C,D,E G,H,I,J K,L,M,N S,A,B,C,D,E,F H,I,J K,L,M,N,O,P S,A,B,C,D,E,F,G
(3)编写算符运算、目标比较等函数;
(4)编写输入、输出接口;
(5)全部模块联调;
(6)撰写实验报告。
(五)实验报告要求
所撰写的实验报告必须包含以下内容:
1. 算法基本原理和流程框图;
2. 基本数据结构分析和实现;
3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功
能、输入输出参数意义和与其它模块联系等;
4. 程序运行结果，含使用的搜索算法及搜索路径等; 5. 实验结果分析;
6. 结论;
7. 提供全部源程序及软件的可执行程序。
4
附:实验报告格式
一、实验问题
二、实验目的
三、实验原理
四、程序框图
五、实验结果及分析
六、结论
七、源程序及注释
#include
#include
int n,m;
typedef struct Node {
char matrix[10];/*存储矩阵*/
char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D
代表不能下移*/
char extend;/*是否可以扩展，Y代表可以，N代表不可以*/
int father;/*指向产生自身的父结点*/ }Node;
char start[10]={"83426517 "};/*此处没有必要初始化*/ char end[10]={"1238 4765"};/*此处没有必要初始化*/ Node base[4000];
int result[100];/*存放结果的base数组下标号，逆序存放*/
int match()/*判断是否为目标*/
{
int i;
for(i=0;i<9;i++)
{
if(base[n-1].matrix[i]!=end[i])
{
return 0;
}
}
return 1;
}
void show()/*显示矩阵的内容*/
{
int i=1;
while(m>=0)
{
5
int mm=result[m];
//clrscr();
printf("\n\n\n 状态方格\t\t步骤 %d",i);
printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]
);
printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);
printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);
//sleep(1);
m--;
i++;
}
}
void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/
{
n--;
while(base[n].father!=-1) {
result[m]=n;
m++;
n=base[n].father;
}
result[m]=0;
result[m+1]='\0';
show();
//clrscr();
printf("\n\n\n\n\n\n\n\n\n\t\t\t\t搜索结束\n\n\n\n\n\n\n\n\n\n");
getch();
//exit(0);
}
int left(int x)/*把下标为X的数组中的矩阵的空格左移*/ {
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==0||i==3||i==6||i==9) {
return 0;
6
}
for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}
ch=base[n].matrix[i-1]; base[n].matrix[i-1]=base[n].matrix[i];
base[n].matrix[i]=ch; base[n].operate='R';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
int right(int x)/*把下标为X的数组中的矩阵的空格右移*/ {
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==2||i==5||i==8||i==9) {
return 0;
}
for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}
ch=base[n].matrix[i+1]; base[n].matrix[i+1]=base[n].matrix[i];
base[n].matrix[i]=ch; base[n].operate='L';
base[n].extend='Y';
7
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
int up(int x)/*把下标为X的数组中的矩阵的空格上移*/ {
int i,j;
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==0||i==1||i==2||i==9) {
return 0;
}
for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}
ch=base[n].matrix[i-3]; base[n].matrix[i-3]=base[n].matrix[i];
base[n].matrix[i]=ch; base[n].operate='D'; base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i)) leave();
return 1;
}
int down(int x)/*把下标为X的数组中的矩阵的空格下移*/ {
int i,j;
8
char ch;
for(i=0;i<9;i++)
{
if(base[x].matrix[i]==' ')
break;
}
if(i==6||i==7||i==8||i==9) {
return 0;
}
for(j=0;j<9;j++)
{
base[n].matrix[j]=base[x].matrix[j];
}
ch=base[n].matrix[i+3]; base[n].matrix[i+3]=base[n].matrix[i];
base[n].matrix[i]=ch;
base[n].operate='U';
base[n].extend='Y';
base[n].father=x;
base[x].extend='N';
n++;
if(match(i))
leave();
return 1;
}
main()
{
int i;
char a[20],b[20];
n=1;
//textcolor(LIGHTGREEN); //clrscr();
/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/ printf("Please input the start 9 chars:");
scanf("%s",a);
printf("Please input the end 9 chars:");
scanf("%s",b);
9
for(i=0;i<9;i++)
{
if(a[i]=='0')
{
start[i]=' ';
continue;
}
if(b[i]=='0')
{
end[i]=' ';
continue;
}
start[i]=a[i];
end[i]=b[i];
}
start[9]='\0';
end[9]='\0';
for(i=0;i<9;i++)
{
base[0].matrix[i]=start[i]; }
base[0].operate='N';
base[0].extend='Y';
base[0].father=-1;
/*以上是为第一个base数组元素赋值*/
for(i=0;n<4000;i++)
{
if(base[i].extend=='Y')
{
if(base[i].operate=='L')
{
right(i);up(i);down(i);
}
if(base[i].operate=='R')
{
left(i);up(i);down(i);
}
if(base[i].operate=='U')
{
left(i);right(i);down(i);
}
10
if(base[i].operate=='D')
{
left(i);right(i);up(i);
}
if(base[i].operate=='N')
{
left(i);right(i);up(i);down(i);
}
}
}
}
11
浙公网安备 33021202002483