昆明理工大学人工智能导论实验报告模板-20xx(新)
昆明理工大学信息工程与自动化学院学生实验报告
（ 20##—— 20## 学年 第 一 学期 ）
课程名称：人工智能导论 开课实验室：信自楼234室 20##年10月29日
目 录
一、实验问题... 2
二、实验目的... 2
三、实验原理... 2
A搜索的原理：... 2
估价函数：... 2
重要程序分析：... 3
四、程序框图... 4
五、实验结果及分析... 5
随机检验1. 5
随机检验2. 6
随机检验3. 7
随机检验4. 7
六、结论... 9
七、源程序及注释... 10
一、实验问题
八数码问题的求解，及程序设计。具体要求如下
在3*3的方格中的棋盘中任意摆放1到8个自然数和一个空格，其初始状态如下：
a初始状态
b目标状态
请选择一种盲目搜索的算法或选择一种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。
二、实验目的
1、熟悉人工智能系统中的问题求解过程；
2、熟悉状态空间的满目搜索和启发式搜索算法的运用；
3、熟悉对八码数问题的建模、求解及编程语言的运用；
三、实验原理
经过分析，8数码问题中可采用的搜速策略共有：
1.广度优先搜索
2.深度优先搜索
2.有界深度优先搜索
4.最好优先搜索
5.局部择优搜索
一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了启发式搜索中的最好优先来实现。启发式搜索算法有A算法、A*算法。本次实验采用了A算法得到结果。
A搜索的原理：
A算法搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
估价函数：
计算一个节点的估价函数，可以分成两个部分：
1、已经付出的代价（起始节点到当前节点）；
2、将要付出的代价（当前节点到目标节点）。
节点n的估价函数
定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即
= 
+ 
。
是从初始节点到达当前节点n的实际代价；
是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。
所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。
本实验中我们使用函数
，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然比
更接近于，因为不仅考虑了错位因素，还考虑了错位的距离。
重要程序分析：
1.结点状态
我采用了struct Node数据类型
typedef struct _Node{
int digit[ROW][COL];
int dist; // distance between one state and the destination一个表和目的表的距离
int dep; // the depth of node深度
// So the comment function = dist + dep.估价函数值
int index; // point to the location of parent父节点的位置
} Node; 2.发生器函数
定义的发生器函数由以下的四种操作组成：
(1)将当前状态的空格上移
Node node_up;
Assign(node_up, index);//向上扩展的节点
int dist_up = MAXDISTANCE;
(2)将当前状态的空格下移
Node node_down;
Assign(node_down, index);//向下扩展的节点
int dist_down = MAXDISTANCE;
(3)将当前状态的空格左移
Node node_left;
Assign(node_left, index);//向左扩展的节点
int dist_left = MAXDISTANCE;
(4)将当前状态的空格右移
Node node_right;
Assign(node_right, index);//向右扩展的节点
int dist_right = MAXDISTANCE;
通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。
四、程序框图
流程图文字解释：
1、把附有f（S0）的初始节点S0放入OPEN。
2、若OPEN为空（NIL），则搜索失败，退出。
3、移除OPEN表中第一个节点Ｎ放入ＣＬＯＳＥＤ表中，并加标号ｉ。
4、若目标节点Ｓｇ＝Ｎ，则搜索成功，结束。
5、若Ｎ不可扩散，则转２。
6、若扩展Ｎ，计算每个子节点函数f（x），对着组数据做以下处理：
（1）、考察是否有已经存在的OPEN表或CLOSED表中存在的节点；若存在则考察有无N的先辈节点，若有则删除它；对于其余的子节点，也删除它，但他们又被第二次生成，因而需要考虑修改已经存在的OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f（x）值，修改原则是“抄f（x）值小的路走”。
（2）对其余的子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按照f（x）值升序排序，转2。
7、以下是流程框图：
五、实验结果及分析
随机检验1
初始状态为：
的运行结果为：
经过运行，该八数码搜索不到原结果。
随机检验2
初始状态为：
的运行结果为：
经过运行，搜索结果如图，本次搜索经过了4个步骤。
随机检验3
初始状态为：
运行结果为：
经过运行搜索结果如图，经过了1步搜索成功。
随机检验4
初始状态为：
运行结果为：
运行结果如图，经过了16个步骤搜索成功。
经过随机验证了4组数据，有一组没出结果，并且有些随机数组搜索不出结果，现在我还找不到是程序错误还是数组本身性质。
六、结论
通过本次试验，对典型的启发式搜索的A算法又了更清晰的认识和运用。从所扩展的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数来说，它的定义趋向多元化，只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。
在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。
七、源程序及注释
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
const int ROW = 3;//行数
const int COL = 3;//列数
const int MAXDISTANCE = 10000;//最多可以有的表的数目
const int MAXNUM = 10000;
typedef struct _Node{
int digit[ROW][COL];
int dist; // distance between one state and the destination一个表和目的表的距离
int dep; // the depth of node深度
// So the comment function = dist + dep.估价函数值
int index; // point to the location of parent父节点的位置
} Node;
Node src, dest;// 父节表 目的表
vector<Node> node_v; // store the nodes存储节点
bool isEmptyOfOPEN() //open表是否为空
{
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist != MAXNUM)
return false;
}
return true;
}
bool isEqual(int index, int digit[][COL]) //判断这个最优的节点是否和目的节点一样
{
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] != digit[i][j])
return false;
}
return true;
}
ostream& operator<<(ostream& os, Node& node)
{
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++)
os << node.digit[i][j] << ' ';
os << endl;
}
return os;
}
void PrintSteps(int index, vector<Node>& rstep_v)//输出每一个遍历的节点 深度遍历
{
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
while (index != 0)
{
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
}
for (int i = rstep_v.size() - 1; i >= 0; i--)//输出每一步的探索过程
cout << "Step " << rstep_v.size() - i
<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b)
{
int t;
t = a;
a = b;
b = t;
}
void Assign(Node& node, int index)
{
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
}
int GetMinNode() //找到最小的节点的位置 即最优节点
{
int dist = MAXNUM;
int loc; // the location of minimize node
for (int i = 0; i < node_v.size(); i++)
{
if (node_v[i].dist == MAXNUM)
continue;
else if ((node_v[i].dist + node_v[i].dep) < dist) {
loc = i;
dist = node_v[i].dist + node_v[i].dep;
}
}
return loc;
}
bool isExpandable(Node& node)
{
for (int i = 0; i < node_v.size(); i++) {
if (isEqual(i, node.digit))
return false;
}
return true;
}
int Distance(Node& node, int digit[][COL])
{
int distance = 0;
bool flag = false;
for(int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
for (int k = 0; k < ROW; k++) {
for (int l = 0; l < COL; l++) {
if (node.digit[i][j] == digit[k][l]) {
distance += abs(i - k) + abs(j - l);
flag = true;
break;
}
else
flag = false;
}
if (flag)
break;
}
return distance;
}
int MinDistance(int a, int b)
{
return (a < b ? a : b);
}
void ProcessNode(int index)
{
int x, y;
bool flag;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] == 0)
{
x =i; y = j;
flag = true;
break;
}
else flag = false;
}
if(flag)
break;
}
Node node_up;
Assign(node_up, index);//向上扩展的节点
int dist_up = MAXDISTANCE;
if (x > 0)
{
Swap(node_up.digit[x][y], node_up.digit[x - 1][y]);
if (isExpandable(node_up))
{
dist_up = Distance(node_up, dest.digit);
node_up.index = index;
node_up.dist = dist_up;
node_up.dep = node_v[index].dep + 1;
node_v.push_back(node_up);
}
}
Node node_down;
Assign(node_down, index);//向下扩展的节点
int dist_down = MAXDISTANCE;
if (x < 2)
{
Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);
if (isExpandable(node_down))
{
dist_down = Distance(node_down, dest.digit);
node_down.index = index;
node_down.dist = dist_down;
node_down.dep = node_v[index].dep + 1;
node_v.push_back(node_down);
}
}
Node node_left;
Assign(node_left, index);//向左扩展的节点
int dist_left = MAXDISTANCE;
if (y > 0)
{
Swap(node_left.digit[x][y], node_left.digit[x][y - 1]);
if (isExpandable(node_left))
{
dist_left = Distance(node_left, dest.digit);
node_left.index = index;
node_left.dist = dist_left;
node_left.dep = node_v[index].dep + 1;
node_v.push_back(node_left);
}
}
Node node_right;
Assign(node_right, index);//向右扩展的节点
int dist_right = MAXDISTANCE;
if (y < 2)
{
Swap(node_right.digit[x][y], node_right.digit[x][y + 1]);
if (isExpandable(node_right))
{
dist_right = Distance(node_right, dest.digit);
node_right.index = index;
node_right.dist = dist_right;
node_right.dep = node_v[index].dep + 1;
node_v.push_back(node_right);
}
}
node_v[index].dist = MAXNUM;
}
int main() // 主函数
{
int number;
cout << "Input source:" << endl;
for (int i = 0; i < ROW; i++)//输入初始的表
for (int j = 0; j < COL; j++) {
cin >> number;
src.digit[i][j] = number;
}
src.index = 0;
src.dep = 1;
cout << "Input destination:" << endl;//输入目的表
for (int m = 0; m < ROW; m++)
for (int n = 0; n < COL; n++) {
cin >> number;
dest.digit[m][n] = number;
}
node_v.push_back(src);//在容器的尾部加一个数据
cout << "Search..." << endl;
clock_t start = clock();
while (1)
{
if (isEmptyOfOPEN())
{
cout << "Cann't solve this statement!" << endl;
return -1;
}
else
{
int loc; // the location of the minimize node最优节点的位置
loc = GetMinNode();
if(isEqual(loc, dest.digit))
{
vector<Node> rstep_v;
cout << "Source:" << endl;
cout << src << endl;
PrintSteps(loc, rstep_v);
cout << "Successful!" << endl;
cout << "Using " << (clock() - start) / CLOCKS_PER_SEC
<< " seconds." << endl;
break;
}
else
ProcessNode(loc);
}
}
return 0;
}
-
人工智能实验报告
人工智能九宫格重移搜索成员赵春杰20xx210665羊森20xx210653黄鑫20xx210周成兵20xx210664王素娟20…
-
人工智能试验报告汇总
人工智能课程实验指导书实验内容实验一产生式系统实验实验二移动机器人的路径规划与行为决策实验实验三梵塔问题实验实验四A算法实验实验五…
-
人工智能实验报告
华北电力大学实验报告实验名称课程名称人工智能及应用专业班级学生姓名号成绩指导教师李继荣实验日期20xx5学华北电力大学实验报告华北…
-
人工智能实验报告
人工智能第二次实验报告一实验题目遗传算法的设计与实现二实验目的通过人工智能课程的学习熟悉遗传算法的简单应用三实验内容用遗传算法求解…
-
人工智能实验报告
人工智能技术实验报告实验名称人工智能实验1姓名班级指导教师完成时间20xx04301读程序指出运行结果domainsssymbol…
-
C语言解八数码问题之人工智能实验报告
人工智能导论上机实验指导书基于人工智能的状态空间搜索策略研究八数码问题求解一实验软件TC20或VC60编程语言或其它编程语言二实验…
-
人工智能实验报告
人工智能九宫格重移搜索成员赵春杰20xx210665羊森20xx210653黄鑫20xx210周成兵20xx210664王素娟20…
-
人工智能试验报告汇总
人工智能课程实验指导书实验内容实验一产生式系统实验实验二移动机器人的路径规划与行为决策实验实验三梵塔问题实验实验四A算法实验实验五…
-
人工智能实验报告
华北电力大学实验报告实验名称课程名称人工智能及应用专业班级学生姓名号成绩指导教师李继荣实验日期20xx5学华北电力大学实验报告华北…
-
人工智能实验报告
人工智能第二次实验报告一实验题目遗传算法的设计与实现二实验目的通过人工智能课程的学习熟悉遗传算法的简单应用三实验内容用遗传算法求解…