1 / 11
文档名称:

人工智能(A星算法).doc

格式:doc   大小:151KB   页数:11页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

人工智能(A星算法).doc

上传人:mh900965 2018/1/3 文件大小:151 KB

下载得到文件列表

人工智能(A星算法).doc

文档介绍

文档介绍:A*算法实验报告
实验目的
、估价函数和算法过程
2. 学会利用A*算法求解N数码难题
3. 理解求解流程和搜索顺序
实验原理
A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的代价以及从节点n到达目标节点的代价。
实验条件
Window NT/xp/7及以上的操作系统
内存在512M以上
CPU在奔腾II以上
实验内容
分别以8数码和15数码为例实际求解A*算法
画出A*算法求解框图
分析估价函数对搜索算法的影响
分析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 < (); 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 << [i][j] << ' ';
os << endl;

最近更新

2025年度农村版房屋租赁合同(含农村电商服务.. 8页

2025年度农村户口分家协议书及农村土地权益保.. 8页

2025年度农村土地承包经营权流转版合同 9页

2025年度农户小额贷款借款合同 8页

河南省郑州市中原区2024-2025学年九年级下学期.. 25页

2025年技术陶瓷制品项目建议书 56页

2025年彩色多普勒超声显象仪项目发展计划 57页

铁路机车配件绿色制造技术-全面剖析 26页

新零售模式下的果品、蔬菜销售策略-全面剖析 27页

野生植物保护现状与挑战-全面剖析 27页

高二数学多因素方法 34页

清理垃圾信息简报(6篇) 9页

高中英语必修三unit1(端午节)作文 9页

电话销售的个人工作计划(32篇) 16页

肾内科护士工作计划优秀5篇 14页

一九八一年技术经济学术活动课题草案 2页

一个简便灵敏测定尿样苯并(a)芘方法 2页

一个反映图书馆几项统计指标关系的公式及其应.. 2页

高中定积分的应用 26页

《现代邮政》杂志易名为《邮政研究》并将公开.. 2页

《无线电通信技术》1983年全年总目录 2页

“轨枕混凝土变频变幅振捣工艺研究”通过评审.. 2页

“热塑剪切带及其对材料韧性断裂的影响”的研.. 2页

“太阳挑战者”号技术性能简介 2页

带倾斜抄板的水平转鼓内的颗粒输送特性研究 2页

Y9025型圆度仪测量钢球圆度时的调偏心方法 2页

XD系列洗衣机电机工作电容器选配的实验分析 2页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页