一、实验内容和要求
八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如:
28
4 7 6 5 7 0 5
目标状态初始状态 (b) (a)
图1 八数码问题示意图
请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。
二、实验目的
1. 熟悉人工智能系统中的问题求解过程;
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;
3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验算法
A*算法是一种常用的启发式搜索算法。
在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为:
f'(n) = g'(n) + h'(n)
这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数:
f(n) = g(n) + h(n)
其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。用f(n)作为f'(n)的近似,也就是用g(n)代替g'(n),h(n)代替h'(n)。(大多数情况下都是满足的,可以不g(n)>=g'(n))1(这样必须满足两个条件:
用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
*算法的步骤
A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都是估价函数最小的结点。
A*算法的步骤如下:
1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。
2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。
3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。
4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后更新队列尾指针。
5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。
四、程序框图
五、实验结果及分析
输入初始状态:2 8 3 目标状态: 1 2 3
8 0 4 1 6 4
7 6 5 7 0 5
运行结果屏幕打印
OPEN表与CLOSE表:
OPEN CLOSE
0 1 2 3 4
0 1 2 3 4 5 6
0 1 5 2 3 4 6 7
0 1 5 7 2 3 4 6 8 90 1 5 7 6 2 3 4 8 9 10
0 1 5 7 6 9 2 3 4 8 11 12 13
0 1 5 7 6 9 11 2 3 4 8 12 13 14 15
0 1 5 7 6 9 11 2 3 4 8 12 13 14 15 16 170 1 5 7 6 9 11 2 3 4 8 12 13 14 15 16 17 18 190 1 5 7 6 9 11 2 3 18 4 8 12 13 14 15 16 17 19 200 1 5 7 6 9 11 2 3 18 4 8 12 13 14 15 16 17 19 21 22
0 1 5 7 6 9 11 2 3 18 4 8 12 13 14 15 16 17 19 21 22 23
0 1 5 7 6 9 11 2 3 18 4 8 23 12 13 14 15 16 17 19 21 22 24 250 1 5 7 6 9 11 2 3 18 4 8 23 24 12 13 14 15 16 17 19 21 22 24 26
26发现为目标节点
0…7
2 8 3 搜索树: 1 0 4
7 6 5
3..11…7 2..14..12 0
2 8 1 8 2 8 2 8
1 4 0 1 7 6 1 6 7 6 7 6 7 0 6…5…2 8 2 8 2 3 2 8 0 2 2 8 0 8 2 8 1 4 7 1 1 6 2 1 1 8 1 4 1 8 1 6 7 6 7 6 7 5 7 6 7 6 0 6 7 0 7 6
7…2 3 1 2 8 0 0 8 1 8 2 1 7 6 7 6 7 6
8..9..注释
1 2 1 2 每个方格中最上面两个数7 8 8 0 7 6 0 6 分别为编号与启发值,下九个数字为八数码。较粗箭头为解路11.23.1 2 1 2 8 4 8 6 1 0 1 2 7 0 7 6 8 2 7 8 7 6 6 0
24.1 2 3 1 0 1 1 2 7 8 8 2 8 2 6 5 7 0 7 6 7 6 6 8 目标节点
六、结论
对于八数码问题,BFS算法最慢,A*算法较快。八数码问题的一个状态实际上是0~9的一个排列,对于任意给定的初始状态和目标,不一定有解,也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类,从奇排列不能转化成偶排列。如果一个数字0~8的随机排列0,用F(X)表示数字X前面比它小的数的个数,全部数字的F(X)之和为Y=∑(F(X)),如果Y为奇数则称原数可以在运为偶数则称原数字的排列是偶排列。因此,Y字的排列是奇排列,如果
行程序前检查初始状态和目标状态的排序的奇偶行是否相同,相同则问题可解,应当能搜索到路径。否则无解。
七、源程序及注释
#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;
int abs(int a)
{
if (a>0) return a;
else return -a;
}
typedef struct _Node{
int digit[ROW][COL];
int dist; ist != MAXNUM)
return false;
}
return true;
}
bool isEqual(int index, int digit[][COL]) { igit[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 << [i][j] << ' ';
os << endl;
}
return os;
}
void PrintSteps(int index, vector<Node>& rstep_v) { ndex;
while (index != 0) {
(node_v[index]);
index = node_v[index].index;
}
for (int i = () - 1; i >= 0; i--)
cout << Step << () - i
<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b) { igit[i][j];
}
int GetMinNode() { ist == 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) { igit[i][j] == 0) { x =i; y = j; flag = true; break; } else flag = false; } if(flag) break; }
Node node_up; ep + 1; (node_up); }
}
Node node_down; ep + 1;
(node_down);
}
}
Node node_left;ep + 1;
(node_left);
}
}
Node node_right; ep + 1;
(node_right);
}
}
node_v[index].dist = MAXNUM;
}
int main() {
int number;
潣瑵输入初始状态: << endl;
for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) { cin >> number; [i][j] = number; } = 0; = 1;
<< endl;潣瑵输入目标状态 for (int m = 0; m < ROW; m++) for (int n = 0; n < COL; n++) { cin >> number; [m][n] = number; }
(src);
while (1) { if (isEmptyOfOPEN()) { ! << endl;找不到解潣瑵
return -1;
}
else {
int loc; // the location of the minimize node
loc = GetMinNode();
if(isEqual(loc, ) {
vector<Node> rstep_v;
挠畯尠初始状态: << endl;
cout << src << endl;
PrintSteps(loc, rstep_v);
挠畯尠成功! << endl;
break;
}
else
ProcessNode(loc);
}
}
return 0;
}