第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
实验报告三.doc
实验三 A*算法
实验三 A*算法
一、实验目的
1. 熟悉和掌握启发式搜索的定义、估价函数和算法过程，理解求解流程和搜索顺序。
2．使学生掌握 A*算法的编程方法，
3．并能利用 A*算法求解 N 数码难题。
二、实验原理
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，
总是选择 f 值最小的节点作为扩展节点。因此，f 是根据需要找到一条最小代价路径的观点
来估算节点的，所以，可考虑每个节点 n 的估价函数值为两个分量：从起始节点到节点 n
的代价以及从节点 n 到达目标节点的代价。
三、实验内容
1、以 8 数码或 15 数码为例，用 A*算法编写一个求解数码问题的程序。
2、画出 A*算法求解框图。
四、程序功能要求
根据情况可以选择实现基本功能或者附加功能
１、基本功能
可以演示问题的求解过程。
２、附加功能
可选择实现下述一种或几种功能：
（１）开始演示。进入 N 数码难题演示程序，可选 8 数码或者 15 数码，点击“选择数
码”按钮确定。
（２）点击“缺省棋局”，会产生一个固定的初始节点。点击“随机生成”，会产生任
意排列的初始节点。
（３）算法执行。点击“连续执行”则程序自动搜索求解，并演示每一步结果；点击“单
步运行”则每次执行一步求解流程。“运行速度”可自由调节。
（４）观察运行过程和搜索顺序，理解启发式搜索的原理。在下拉框中选择演示“15
数码难题”，点击“选择数码”确定选择；运行 15 数码难题演示实例。
（５）算法流程的任一时刻的相关状态,以算法流程高亮、open 表、close 表、节点静
态图、当前扩展节点移动图等 5 种形式在按钮上方同步显示,便于深入学习理解 A*算法。
五、实验截图
六、实验源码
#include
#include
#include
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_v;
// store the nodes
bool isEmptyOfOPEN() {
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& 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 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;
}
程序框图：
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
