昆明理工大学信息工程与自动化学院学生实验报告
（ 20##—— 20## 学年 第 一 学期 ）
课程名称：人工智能导论 开课实验室：信自楼432室 20##年10月26日
目录
一、实验问题... 3
二、实验目的... 3
三、实验原理... 3
四、程序框图... 4
五、实验结果及分析... 5
1、随机检验... 5
2、该问题广度优先搜索算法的搜索树；... 6
3、该问题的Open 表和 Closed 表：... 7
六、结论... 7
七、源程序及注释... 8
一、实验问题
八数码问题的求解，及程序设计。具体要求如下
在3*3的方格中的棋盘中任意摆放1到8个自然数和一个空格，其初始状态如下：
请选择一种盲目搜索的算法或选择一种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。
二、实验目的
1、熟悉人工智能系统中的问题求解过程；
2、熟悉状态空间的满目搜索和启发式搜索算法的运用；
3、熟悉对八码数问题的建模、求解及编程语言的运用；
三、实验原理
经过分析，8数码问题中可采用的搜速策略共有：
1.广度优先搜索
2.深度优先搜索
2.有界深度优先搜索
4.最好优先搜索
5.局部择优搜索
一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了广度优先算法
广度优先算法搜索原理：
广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考察完之后，才考查下一级的节点。
（1）把起始节点放到OPEN表中；
（2）如果OPEN是个空表，则没有解，失败退出；否则继续；
（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；
（4）扩展节点n。如果没有后继节点，则转向（2）；
（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；
（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）
四、程序框图
五、实验结果及分析
1、随机检验
初始状态为：
的运行结果为：
运行结果如图所示；
目标状态为：
2、该问题广度优先搜索算法的搜索树；
3、该问题的Open 表和 Closed 表：
六、结论
通过实验问题的求解过程就是搜索的过程，让我明白了采用适合的搜索算法是关键的，因为一个合适的算法对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。虽然我使用的广度优先算法实现八数码问题，但是我不得不说广度优先算法其实是一种比较费劲的方式；然而深度优先将是一个相对好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。 这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验让我受益匪浅。
七、源程序及注释
//八数码问题——广度优先
#include ＜iostream.h＞
struct Snode
{
int parent; //指向该结点父节点的编号
int map[9];
public:
void TransformIn(const int *d);
void TransformOut(int *d);
};
void Snode::TransformIn(const int *d)
{
for(int i=0;i＜9;++i)
map[i]=d[i];
}
#define MAX_OPEN_LEN 50000
#define MAX_CLOSE_LEN 50000
Snode OPEN[MAX_OPEN_LEN];
int op=0;
Snode CLOSE[MAX_CLOSE_LEN];
int cp=0;
int result[50000][9]; //result数组用于保存路径，纵向9个数为对应的map数组
int have(Snode &node1,Snode &node2) //判断是否为新节点
{
int flag=1;
for(int i=0;i＜9;i++)
{
if(node1.map[i]!=node2.map[i]) flag=0;
}
return flag;
}
inline void swapn(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}
//判断节点是否为目标节点
int judge(Snode &node)
{
int flag=1;
int g[9]={1,2,3,8,0,4,7,6,5};
for(int i=0;i＜9;i++)
{
if(node.map[i]!=g[i])
flag=0;
}
return flag;
}
int Astar(const int *d)
{
int begin=0; //begin含义是每次从OPEN表中去除要扩展的那个节点
int node_number=1; //扩展节点数，初始时已有OPEN[0]节点,故为1，即node_number=cp+op
static int dp[4]={-3,-1,1,3}; //-3表示向上移动，3表示向下移动，-1表示向左移动，1表示向右移动
op=1;
cp=0;
OPEN[begin].TransformIn(d);
OPEN[begin].parent=-1; //根节点的parent值设置为-1
while(op＞0)//OPEN表不为空
{
int i=0,zero,pos,j=0,k=0;
if(judge(OPEN[begin])==1) //找到的这个节点已经是目标节点
{
CLOSE[cp]=OPEN[begin];
while(begin!=-1) //while循环用于把路径存入数组result中，顺序是从目标节点到根节点
{
for(int i=0;i＜9;i++)
{
result[j][i]=OPEN[begin].map[i];
}
j=j+1;
begin=OPEN[begin].parent;
}
for(i=j-1;i＞=0;i--) //两层for循环用于把result数组中保存的路径输出，从最后一个向前输出
{
for(k=0;k＜9;k++)
{
cout＜
if(k%3==2) cout＜
}
cout＜
}
cout＜＜"生成的节点总数为："＜
cout＜＜"扩展的节点总数为："＜
return 1;
}
for(zero=0;zero＜9;++zero)
{
if(OPEN[begin].map[zero]==0)
break; //跳出当前for循环，向下执行
}
for(i=0;i＜4;++i)
{
if(zero==0&&(i==0||i==1)) continue; //判断zero位置怎样可以移动，与上边的判断相同
if(zero==1&&i==0) continue;
if(zero==2&&(i==0||i==2)) continue;
if(zero==3&&i==1) continue;
if(zero==5&&i==2) continue;
if(zero==6&&(i==1||i==3)) continue;
if(zero==7&&i==3) continue;
if(zero==8&&(i==2||i==3)) continue;
pos=zero+dp[i];
swapn(OPEN[begin].map[zero],OPEN[begin].map[pos]); //交换位置
Snode child;
child.TransformIn(OPEN[begin].map);
for(j=0;j
{
if(have(CLOSE[j],child)==1)
break;
}
if(j==cp) //得到新节点
{
OPEN[op]=child; //先使用op,再op加1
OPEN[op].parent=begin;
op=op+1;
node_number=node_number+1;
if(node_number==10000) //有些情况可能不存在解，这里当op等于10000时退出，并返回0
{
cout＜＜"node_number="＜
cout＜＜"op="＜
return 0;
}
}
swapn(OPEN[begin].map[zero],OPEN[begin].map[pos]); //前边把OPEN[min]的值进行了交换，现在再换回去，保持OPEN[min]的map数组
}
CLOSE[cp++]=OPEN[begin];
begin=begin+1;
}
return 0;
}
void OutputSolution()
{
cout＜＜"Succeed!\n";
}
int main(void)
{
//int map[9]={ 2, 8, 3, 1, 4, 0, 7, 6, 5 };
//{1,3,4,2,8,6,5,7,0};
//{6,4,7,8,5,0,3,2,1};
//{1,2,3,4,5,6,7,8,0};
//{2,8,3,1,0,4,7,6,5};
//{1,3,4,0,6,2,8,7,5};
int map[9];
cout＜＜"请输入初始数组："＜
for(int i=0;i＜3;i++)
for(int j=0;j＜3;j++)
cin＞＞map[3*i+j];
if(Astar(map))
cout＜＜"Succeed!"＜
else
cout＜＜"no solution!\n";
cout＜＜"按n键退出"＜
char c;
cin＞＞c;
if(cin&&c!='n')
{
return 0;
}
return 0;
}