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

人工智能导论上机实验指导书基于人工智能的状态空间搜索策略研究八数码问题求解（一）实验软件TC2.0 或 VC6.0 编程语言或其它编程语言（二）实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。（三）需要的预备知识1. 熟悉TC2.0 或 VC6.0 编程语言或者其它编程语言；2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用；4. 熟悉计算机常用人机接口设计。（四）实验数据及步骤1. 实验内容八数码问题：在33的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。2541233784186765(a) 初始状态 (b) 目标状态图1 八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。2. 实验步骤（1）分析算法基本原理和基本流程；程序采用宽度优先搜索算法，基本流程如下：起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是（2）确定对问题描述的基本数据结构，如 Open 表和 Closed 表等；OPENCLOSEDSA,B,CSB,C,D,E,FS,AC,D,E,F,GS,A,BD,E,F,G,HS,A,B,CE,F,G,H,I,JS,A,B,C,DF,G,H,I,J K,LS,A,B,C,D,EG,H,I,J K,L,M,NS,A,B,C,D,E,FH,I,J K,L,M,N,O,PS,A,B,C,D,E,F,G（3）编写算符运算、目标比较等函数；（4）编写输入、输出接口；（5）全部模块联调；（6）撰写实验报告。（五）实验报告要求所撰写的实验报告必须包含以下内容：1. 算法基本原理和流程框图；2. 基本数据结构分析和实现；3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；4. 程序运行结果，含使用的搜索算法及搜索路径等；5. 实验结果分析；6. 结论；7. 提供全部源程序及软件的可执行程序。附：实验报告格式一、实验问题二、实验目的三、实验原理四、程序框图五、实验结果及分析六、结论七、源程序及注释#include#includeint n,m;typedef struct Nodechar matrix10;/*存储矩阵*/char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/char extend;/*是否可以扩展，Y代表可以，N代表不可以*/int father;/*指向产生自身的父结点*/Node;char start10=83426517 ;/*此处没有必要初始化*/char end10=1238 4765;/*此处没有必要初始化*/Node base4000;int result100;/*存放结果的base数组下标号，逆序存放*/int match()/*判断是否为目标*/int i;for(i=0;i=0) int mm=resultm; /clrscr(); printf(nnn 状态方格tt步骤 %d,i); printf(nnnnnttt%ct%ct%cn,basemm.matrix0,basemm.matrix1,basemm.matrix2); printf(nnttt%ct%ct%cn,basemm.matrix3,basemm.matrix4,basemm.matrix5); printf(nnttt%ct%ct%cn,basemm.matrix6,basemm.matrix7,basemm.matrix8); /sleep(1); m-; i+;void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/n-;while(basen.father!=-1) resultm=n; m+; n=basen.father;resultm=0;resultm+1=0;show();/clrscr();printf(nnnnnnnnntttt搜索结束nnnnnnnnnn);getch();/exit(0);int left(int x)/*把下标为X的数组中的矩阵的空格左移*/int i,j;char ch;for(i=0;i9;i+) if(basex.matrixi= ) break;if(i=0|i=3|i=6|i=9) return 0;for(j=0;j9;j+) basen.matrixj=basex.matrixj;ch=basen.matrixi-1;basen.matrixi-1=basen.matrixi;basen.matrixi=ch;basen.operate=R;basen.extend=Y;basen.father=x;basex.extend=N;n+; if(match(i)leave();return 1;int right(int x)/*把下标为X的数组中的矩阵的空格右移*/int i,j;char ch;for(i=0;i9;i+) if(basex.matrixi= ) break;if(i=2|i=5|i=8|i=9) return 0;for(j=0;j9;j+) basen.matrixj=basex.matrixj;ch=basen.matrixi+1;basen.matrixi+1=basen.matrixi;basen.matrixi=ch;basen.operate=L;basen.extend=Y;basen.father=x;basex.extend=N;n+;if(match(i)leave();return 1;int up(int x)/*把下标为X的数组中的矩阵的空格上移*/int i,j;char ch;for(i=0;i9;i+) if(basex.matrixi= ) break;if(i=0|i=1|i=2|i=9) return 0;for(j=0;j9;j+) basen.matrixj=basex.matrixj;ch=basen.matrixi-3;basen.matrixi-3=basen.matrixi;basen.matrixi=ch;basen.operate=D;basen.extend=Y;basen.father=x;basex.extend=N;n+; if(match(i)leave();return 1;int down(int x)/*把下标为X的数组中的矩阵的空格下移*/int i,j;char ch;for(i=0;i9;i+) if(basex.matrixi= ) break;if(i=6|i=7|i=8|i=9) return 0;for(j=0;j9;j+) basen.matrixj=basex.matrixj;ch=basen.matrixi+3;basen.matrixi+3=basen.matrixi;basen.matrixi=ch;basen.operate=U;basen.extend=Y;basen.father=x;basex.extend=N;n+; if(match(i)leave();return 1;main()int i;char a20,b20;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;i9;i+) if(ai=0) starti= ; continue; if(bi=0) endi= ; continue; starti=ai; endi=bi;start9=0;end9=0;for(i=0;i9;i+) base0.matrixi=starti;base0.operate=N;base0.extend=Y;base0.father=-1;/*以上是为第一个base数组元素赋值*/for(i=0;n4000;i+) if(basei.extend=Y) if(basei.operate=L) right(i);up(i);down(i); if(basei.operate=R) left(i);up(i);down(i); if(basei.operate=U) left(i);right(i);down(i); if(basei.operate=D) left(i);right(i);up(i); if(basei.operate=N) left(i);right(i);up(i);down(i); 11