C语言解八数码问题之人工智能实验报告

八数码问题

人工智能导论》上机实验指导书

《

八数码问题

基于人工智能的状态空间搜索策略研究

——八数码问题求解

（一）实验软件

TC2.0 或 VC6.0 编程语言或其它编程语言

（二）实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。

（三）需要的预备知识

1. 熟悉TC2.0 或 VC6.0 编程语言或者其它编程语言；

2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；

3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤

1. 实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

图1 八数码问题示意图

请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

2. 实验步骤

（1）分析算法基本原理和基本流程；

程序采用宽度优先搜索算法，基本流程如下：

八数码问题

起始

把 s 放入 open 表

是否 open 表为 空表？

是 失败

否

把 open 表中的第一个节点 n 移入 close 表

扩展节点 n,把其后裔放入 open 表的前头

否

是 是否有后继节点 为目标节点？ 成功

八数码问题

（2）确定对问题描述的基本数据结构，如 Open 表和 Closed 表等；

（3）编写算符运算、目标比较等函数；

（4）编写输入、输出接口；

（5）全部模块联调；

（6）撰写实验报告。

（五）实验报告要求

所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图；

2. 基本数据结构分析和实现；

3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；

4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析；

6. 结论；

7. 提供全部源程序及软件的可执行程序。

八数码问题

附：实验报告格式

一、实验问题 二、实验目的 三、实验原理 四、程序框图

五、实验结果及分析 六、结论

七、源程序及注释

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

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) {

八数码问题

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;

八数码问题

}

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';

八数码问题

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;

八数码问题

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);

八数码问题

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); }

八数码问题

if(base[i].operate=='D') {

left(i);right(i);up(i); }

if(base[i].operate=='N') {

left(i);right(i);up(i);down(i); } } } }