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年度商铺租赁合同模板(含租赁区域使用限.. 7页

2025年度商场品牌促销活动合作协议 9页

2025年度员工股权期权授予与行使协议 8页

2025年度员工上岗与绩效考核相结合协议 7页

2025年度合同比对技术在国际贸易中的应用合同.. 9页

2025年度合伙人退股协议书:高科技项目股权退.. 8页

2025年度变压器所有权转让与绿色能源项目合作.. 9页

2025年度原创服装设计委托创作合同著作权归属.. 9页

2025年度卫浴产品用户体验设计与优化合同 8页

2025年度医院病理科与检验试剂生产企业合作合.. 9页

2025年度北京市事业单位聘用合同(旅游餐饮类.. 8页

2025年度加油站安全防护设施升级改造工程合同.. 9页

2025年度办公室人员个性化办公设备配置劳动合.. 9页

2025年度分公司合伙人内部协议书:新兴技术引.. 9页

2025年度净水设备远程监控与智能维护服务合同.. 9页

2025年度农村鱼塘承包协议书(涵盖水生植物种.. 8页

2025年度农村旅游民宿建筑设计与施工合同 9页

麦当劳的培训体系 28页

2025年度农机作业服务与农业信息化安全管理合.. 9页

第01讲整式的乘法(知识解读+达标检测)-2024.. 28页

2025年拖把合作协议书 62页

高级PPT制作教程 25页

夹脊穴电针治疗对肩周炎的疗效研究-全面剖析 26页

表型与基因组关联研究(P-GTG)-全面剖析 27页

格兰特船长的儿女读书心得作文(6篇) 7页

法人授权委托书[精华](28篇) 21页

生日答谢词合集(3篇) 5页

2025年大学中国新能源电动汽车消费者调研报告.. 24页

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