人工智能(A星算法)电子教案.doc

人工智能(A星算法)

学习—————好资料
A*算法实验报告
实验目的
1．熟悉和掌握启发式搜索的定义、估价函数和算法过程
2. 学会利用A*算法求解N数码难题
3. 理解求解流程和搜索顺序
实验原理
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。
实验条件
1. Window NT/xp/7及以上的操作系统
2. 内存在512M以上
3. CPU在奔腾II以上
实验内容
1. 分别以8数码和15数码为例实际求解A*算法
2. 画出A*算法求解框图
3. 分析估价函数对搜索算法的影响
4. 分析A*算法的特点
实验分析
1. A*算法基本步骤
1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。
2）生成一个列表CLOSED，它的初始值为空。
3）如果OPEN表为空，则失败退出。
4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。
5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。
6）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n的后继。
7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。
8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。
9）返回第3步。
在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。
实验步骤
算法流程图
开始

读入棋局初始状态

是否可解

否o

是o

初始状态加入open表

在open表中找到评价值最小的节点，作为当前结点

是目标节点

是o

否o

扩展新状态，把不重复的新状态加入open表中

当前结点从open表移除

结束
输出结果

程序代码
#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; //一个表和目的表的距离
int dep; // t深度
int index; //节点的位置
} Node;

Node src, dest;// 父节表 目的表

vector<Node> node_v; //存储节点

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;
}
程序运行效果图
2
8
3
1
6
4
7

5
(初始状态)
1
2
3
8
0
4
7
6
5
(结束状态)

个人实验小结
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。通过本实验， 我熟悉启发式搜索的定义、估价函数和算法过程，并利用A*算法求解了8数码难题，理解了求解流程和搜索顺序。实验过程中巩固了所学的知识，通过实验也提高了自己的编程和思维能力，收获很多。
精品资料