2024年1月8日发(作者：司徒丽君)
。
人工智能实验报告
实验名称：八数码问题
姓名：xx
学号：2012210xx
xx计算机学院
2014年1月14日
精选资料，欢迎下载
。
一．实验目的
掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。
二．实验内容
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如
2 8 3
1 6 4
7 0 5
2 8 3
1 6 4
7 0 5
三、A*算法思想：
1、思想：
A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好
2、原理：
估价函数公式表示为： f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
精选资料，欢迎下载
。
四、算法流程：
Heuristic_Search(启发式搜索)
While（未拓展
表不为空？）
是
从未拓展表中删除第一个状态n
是，输出路径
N为目标状态？
否，生成n的所有子状态
Case:此子状态Case:此子状态Case:此子状态
在未拓展表中 在拓展表
不在拓展表和
未拓展表中
计算该子状态的估价函记录比已有的路径更短记录比已有的路径更短
数值；
的路径
的路径
精选资料，欢迎下载
。
返回
五、关键技术：
1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。
关键代码：
bool CreateChild(NOExtend ns[],NOExtend ne){
int i,j,k=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(_[i][j]==0){ //寻找九宫格空缺所在的坐标
if(i-1>=0){ //将空格向上移动
CopySudoku(ns[k].cur_sudoku,_sudoku);//先把未改变的九宫格复制给九宫格数组的某一元素
ns[k].cur_[i][j]=_[i-1][j];//然后仅改变此二维九宫格的两项值即可
ns[k].cur_[i-1][j]=0;
ns[k].dx=1;
k++;
}
if(j+1<=2){ //将空格向右移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i][j+1];
ns[k].cur_[i][j+1]=0;
ns[k].dx=1;
k++;
}
if(i+1<=2){ //将空格向下移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i+1][j];
ns[k].cur_[i+1][j]=0;
ns[k].dx=1;
k++;
}
if(j-1>=0){ //将空格向左移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i][j-1];
ns[k].cur_[i][j-1]=0;
ns[k].dx=1;
k++;
}
return 1;
}
精选资料，欢迎下载
。
}
}
return 0;
2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。
关键代码：
bool Heuristic_Search(Sudoku start,Sudoku end){
int a=0,b=0,c=0;
int count=0;
NOExtend_Sudoku ns; //未扩展结点表
Extended_Sudoku es; //已扩展结点表
Path path; //求解路径
NOExtend father; //定义父节点
_node[a].cur_sudoku=start; //初始化未拓展结点表
_node[a].dx=0;
_node[a].hx=GetHx(_node[a].cur_sudoku,end);
_node[a].fx=_node[a].dx+_node[a].hx;
a++;
while(a!=0) //当未拓展结点表不为空时
{
father=_node[0]; //父节点为为拓展表的第一个结点
[c++]=father; //记录求解路径
DeleteFirst(ns,a); //从未拓展表中删除第一个结点
a--;
if(EqualSudoku(_sudoku,end)){ //如果找到了目标九宫格则输出求解路径
ShowPath(path,c);
return 1;
}
NOExtend child[4]; //因为九宫格只能拓展上下左右四个方向所以拓展出的结点最多有四个
CreateChild(child,father); //生成父节点的扩展结点
if(!CreateChild(child,father))
continue; //如果没有扩展结点就跳出进行下一次循环
for(int i=0;i<4;i++){
if(child[i].dx==1){ //对于父节点可以生成的每个子结点
if(!ExistNOExtend(ns,child[i].cur_sudoku)&&!ExistExtended(es,child[i].cur_sudoku))
{//如果未拓展表和已拓展表中都没有此状态，则添加此状态到未拓展表中
Value(child[i],father,end);//获取此结点的估价值
精选资料，欢迎下载
。
_node[a]=child[i];
_node_father[a]=father;
a++;
continue;
}
if(ExistNOExtend(ns,child[i].cur_sudoku)){
//如果未拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较
//若估价值大就放弃此结点，更小，就加入此结点
Value(child[i],father,end);
if(child[i].fx<){
_node[a]=child[i];
_node_father[a]=father;
a++;
continue;
}
}
if(ExistExtended(es,child[i].cur_sudoku)){
//如果已拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较
//若估价值大就放弃此结点，更小，就加入此结点
Value(child[i],father,end);
if(child[i].fx<[0].value){//当子状态的价值小与已经扫描过的状态时
_node[a]=child[i];
_node_father[a]=father;
a++;//a为未拓展表中的元素个数
continue;
}
}
}
}
[b].cur_sudoku=_sudoku; //将已经生成完拓展结点的父节点放入已拓展表中
[b].value=;
b++; //b为已拓展表中的元素个数
SortNoExtend(ns,a); //根据估价函数值，从小到大重新排列未拓展表，每次只搜索估价值最小的结点的路径
if(count++>MAXPATH){
break;
}
}
return 0;
}
精选资料，欢迎下载
。
六、实验心得
1、学习了新的算法——A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我编程能力的一种提升，也让我懂了更多做题的方法。
2、在这次实验中，存在着许许多多细节上的小问题，是因为自己的编程基础不牢靠而产生的，通过这次实验又让我懂了许多细节上的问题，以后就不会发生类似的问题了。
精选资料，欢迎下载
。
Welcome !!!
欢迎您的下载，
资料仅供参考！
精选资料，欢迎下载
2024年1月8日发(作者：司徒丽君)
。
人工智能实验报告
实验名称：八数码问题
姓名：xx
学号：2012210xx
xx计算机学院
2014年1月14日
精选资料，欢迎下载
。
一．实验目的
掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。
二．实验内容
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如
2 8 3
1 6 4
7 0 5
2 8 3
1 6 4
7 0 5
三、A*算法思想：
1、思想：
A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好
2、原理：
估价函数公式表示为： f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
精选资料，欢迎下载
。
四、算法流程：
Heuristic_Search(启发式搜索)
While（未拓展
表不为空？）
是
从未拓展表中删除第一个状态n
是，输出路径
N为目标状态？
否，生成n的所有子状态
Case:此子状态Case:此子状态Case:此子状态
在未拓展表中 在拓展表
不在拓展表和
未拓展表中
计算该子状态的估价函记录比已有的路径更短记录比已有的路径更短
数值；
的路径
的路径
精选资料，欢迎下载
。
返回
五、关键技术：
1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。
关键代码：
bool CreateChild(NOExtend ns[],NOExtend ne){
int i,j,k=0;
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(_[i][j]==0){ //寻找九宫格空缺所在的坐标
if(i-1>=0){ //将空格向上移动
CopySudoku(ns[k].cur_sudoku,_sudoku);//先把未改变的九宫格复制给九宫格数组的某一元素
ns[k].cur_[i][j]=_[i-1][j];//然后仅改变此二维九宫格的两项值即可
ns[k].cur_[i-1][j]=0;
ns[k].dx=1;
k++;
}
if(j+1<=2){ //将空格向右移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i][j+1];
ns[k].cur_[i][j+1]=0;
ns[k].dx=1;
k++;
}
if(i+1<=2){ //将空格向下移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i+1][j];
ns[k].cur_[i+1][j]=0;
ns[k].dx=1;
k++;
}
if(j-1>=0){ //将空格向左移动
CopySudoku(ns[k].cur_sudoku,_sudoku);
ns[k].cur_[i][j]=ns[k].cur_[i][j-1];
ns[k].cur_[i][j-1]=0;
ns[k].dx=1;
k++;
}
return 1;
}
精选资料，欢迎下载
。
}
}
return 0;
2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。
关键代码：
bool Heuristic_Search(Sudoku start,Sudoku end){
int a=0,b=0,c=0;
int count=0;
NOExtend_Sudoku ns; //未扩展结点表
Extended_Sudoku es; //已扩展结点表
Path path; //求解路径
NOExtend father; //定义父节点
_node[a].cur_sudoku=start; //初始化未拓展结点表
_node[a].dx=0;
_node[a].hx=GetHx(_node[a].cur_sudoku,end);
_node[a].fx=_node[a].dx+_node[a].hx;
a++;
while(a!=0) //当未拓展结点表不为空时
{
father=_node[0]; //父节点为为拓展表的第一个结点
[c++]=father; //记录求解路径
DeleteFirst(ns,a); //从未拓展表中删除第一个结点
a--;
if(EqualSudoku(_sudoku,end)){ //如果找到了目标九宫格则输出求解路径
ShowPath(path,c);
return 1;
}
NOExtend child[4]; //因为九宫格只能拓展上下左右四个方向所以拓展出的结点最多有四个
CreateChild(child,father); //生成父节点的扩展结点
if(!CreateChild(child,father))
continue; //如果没有扩展结点就跳出进行下一次循环
for(int i=0;i<4;i++){
if(child[i].dx==1){ //对于父节点可以生成的每个子结点
if(!ExistNOExtend(ns,child[i].cur_sudoku)&&!ExistExtended(es,child[i].cur_sudoku))
{//如果未拓展表和已拓展表中都没有此状态，则添加此状态到未拓展表中
Value(child[i],father,end);//获取此结点的估价值
精选资料，欢迎下载
。
_node[a]=child[i];
_node_father[a]=father;
a++;
continue;
}
if(ExistNOExtend(ns,child[i].cur_sudoku)){
//如果未拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较
//若估价值大就放弃此结点，更小，就加入此结点
Value(child[i],father,end);
if(child[i].fx<){
_node[a]=child[i];
_node_father[a]=father;
a++;
continue;
}
}
if(ExistExtended(es,child[i].cur_sudoku)){
//如果已拓展表中有此状态，此求得当前状态的估价值并且与表中存在的此状态的估价值比较
//若估价值大就放弃此结点，更小，就加入此结点
Value(child[i],father,end);
if(child[i].fx<[0].value){//当子状态的价值小与已经扫描过的状态时
_node[a]=child[i];
_node_father[a]=father;
a++;//a为未拓展表中的元素个数
continue;
}
}
}
}
[b].cur_sudoku=_sudoku; //将已经生成完拓展结点的父节点放入已拓展表中
[b].value=;
b++; //b为已拓展表中的元素个数
SortNoExtend(ns,a); //根据估价函数值，从小到大重新排列未拓展表，每次只搜索估价值最小的结点的路径
if(count++>MAXPATH){
break;
}
}
return 0;
}
精选资料，欢迎下载
。
六、实验心得
1、学习了新的算法——A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我编程能力的一种提升，也让我懂了更多做题的方法。
2、在这次实验中，存在着许许多多细节上的小问题，是因为自己的编程基础不牢靠而产生的，通过这次实验又让我懂了许多细节上的问题，以后就不会发生类似的问题了。
精选资料，欢迎下载
。
Welcome !!!
欢迎您的下载，
资料仅供参考！
精选资料，欢迎下载