资源简介
z1. 综合应用“深度优先搜索”、“宽度优先搜索”、“启发式搜索”这三种人工智能搜索技术的基本知识以及程序设计的相关知识。
z2. 通过设计一个八数码问题求解程序，学习、了解状态空间搜索的思想，进一步加深对人工智能课程相关启发式搜索的理解。
z实验内容 1. 针对八数码问题，在Windows环境下用C/C++语言(Java语言)实现几种搜索算法(最好是图形界面)：
y深度优先搜索 P23
y宽度优先搜索 P24
y启发式搜索算法（h1(n) =W(n) “不在位”的将牌数）P28
y启发式搜索算法（h2(n) = P(n)将牌“不在位”的距离和）P40
y启发式搜索算法（h3(n) = h(n)＝P(n)+3S(n)） P46
2. 随机产生或手动输入初始状态，对于同一个初始状态，分别用上面的5种方法进行求解，并对比结果
代码片段和文件信息
#include“8puzzle.h“
//主函数
int main（）{
eightdigit e;
e.init（）;
return 0;
}
//查找空格位置
int eightdigit::findpos（int a）{
int pos = 9;
while （a % 10 != 0）{
pos--;
a /= 10;
}
return pos;
}
//下移操作
int eightdigit::mDown（int a int pos）{
if （pos >= 7） return 0;//表明空格在第三一行，不能下移，返回0
int b = a / p[pos + 3];
b = b % 10; //空格下面的数码位置为pos+3，找出对应位置的数码值b
a -= b * p[pos + 3]; //移动空格0到位置pos+3
a += b * p[pos]; //移动数码值b到位置pos
if （exist[a] == 0）
return a; //如果是新状态，返回该状态a，否则返回0
else return 0;
}
//上移操作
int eightdigit::mUp（int a int pos）{
if （pos <= 3） return 0;//表明空格在第一行，不能上移，返回0
int b = a / p[pos - 3];
b = b % 10; //空格上面的数码位置为pos-3，找出对应位置的数码值b
a -= b * p[pos - 3]; //移动空格0到位置pos-3
a += b * p[pos]; //移动数码值b到位置pos
if （exist[a] == 0）
return a; //如果是新状态，返回该状态a，否则返回0
else return 0;
}
//左移
int eightdigit::mLeft（int a int pos）{
if （pos % 3 == 1） return 0;//表明空格在第一列，不能左移，返回0
int b = a / p[pos - 1];
b = b % 10; //空格左面的数码位置为pos-1，找出对应位置的数码值b
a -= b * p[pos - 1]; //移动空格0到位置pos-1
a += b * p[pos]; //移动数码值b到位置pos
if （exist[a] == 0）
return a; //如果是新状态，返回该状态a，否则返回0
else return 0;
}
//右移
int eightdigit::mRight（int a int pos）{
if （pos % 3 == 0） return 0;//表明空格在第三列，不能右移，返回0
int b = a / p[pos + 1];
b = b % 10; //空格右面的数码位置为pos+1，找出对应位置的数码值b
a -= b * p[pos + 1]; //移动空格0到位置pos+1
a += b * p[pos]; //移动数码值b到位置pos
if （exist[a] == 0）
return a; //如果是新状态，返回该状态a，否则返回0
else return 0;
}
//深度优先搜索，递归调用
bool eightdigit::dfs（int a）{
if （a == aim） return true;//找到目标状态，返回ture
int b;
expand[0] += 1; //扩展结点数
int pos = findpos（a）; //查找状态a空格所在的位置pos
b = mDown（a pos）; //当前空格下移，得到新状态b
if （b）{
exist[b] = a; //映射，状态a生成状态b
create[0] += 1; //生成结点数
if （dfs（b）） return true;//递归调用
}
b = mUp（a pos）;
if （b）{
exist[b] = a;
create[0] += 1;
if （dfs（b）） return true;
}
b = mLeft（a pos）;
if （b）{
exist[b] = a;
create[0] += 1;
if （dfs（b）） return true;
}
b = mRight（a pos）;
if （b）{
exist[b] = a;
create[0] += 1;
if （dfs（b）） return true;
}
return false;
}
//宽度优先搜索，队列处理
bool eightdigit::bfs（int a）{
int b;
while （!qopen.empty（））
qopen.pop（）;
qopen.push（a）;
while （!qopen.empty（））{
a = qopen.front（）; //取状态a进行扩展
qopen.pop（）;
if （a == aim）{
return true; //找到目标状态，返回ture
}
expand[1]++; //扩展结点数
int pos = findpos（a）; //查找状态a空格所在的位置pos
b = mDown（a pos）; //当前空格下移，得到新状态b
if （b）{
exist[b] = a; //映射，状态a生成状态b
create[1] += 1; //生成状态数
qopen.push（b）; //新状态b入栈
}
b = mUp（a pos）;
if （b）{
exist[b] = a;
create[1] += 1;
qopen.push（b）;
}
b = mLeft（a pos）;
if （b）{
exist[b] = a;
create[1] += 1;
qopen.push（b）;
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
文件 3537834 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\8 puzzle solution path.txt
文件 8120 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\8 puzzle.cpp
文件 3993 2017-05-30 17:45 【170518】8 puzzle\8 puzzle\8 puzzle.vcxproj
文件 1066 2017-05-30 17:45 【170518】8 puzzle\8 puzzle\8 puzzle.vcxproj.filters
文件 143 2017-05-06 22:33 【170518】8 puzzle\8 puzzle\8 puzzle.vcxproj.user
文件 1815 2017-05-30 17:50 【170518】8 puzzle\8 puzzle\8puzzle.h
文件 406 2017-05-18 09:02 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.exe.em
文件 472 2017-05-18 10:41 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.exe.em
文件 381 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.exe.intermediate.manifest
文件 69 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.lastbuildstate
文件 2604 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.log
文件 594806 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.obj
文件 713 2017-05-27 10:51 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.vcxprojResolveAssemblyReference.cache
文件 0 2017-05-18 10:41 【170518】8 puzzle\8 puzzle\Debug\8 puzzle.write.1.tlog
文件 206 2017-05-18 09:02 【170518】8 puzzle\8 puzzle\Debug\8 puzzle_manifest.rc
文件 1434 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\cl.command.1.tlog
文件 25358 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\CL.read.1.tlog
文件 858 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\CL.write.1.tlog
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 2 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 3266 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
文件 6128 2017-05-31 11:06 【170518】8 puzzle\8 puzzle\Debug\li
............此处省略25个文件信息
- 上一篇：网上购物系统+毕业设计（完整版）
- 下一篇：奖学金管理系统源码
川公网安备 51152502000135号
评论
共有 条评论