人工智能八数码
更新时间:2024-07-07 14:44:01 阅读量: 综合文库 文档下载
基于A星算法解决8数码
问题的编程实现
一、问题描述
8数码问题又称9宫问题。在给定的3?3棋格的9个格子内分别放从1到8互不相等的八个数,剩下的一格即为空格,此程序中空格我们用0来表示。通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时,规则给定一个初始状态和一个目标状态,并要求被试者对棋格内的数字经过若干次移动由初始状态达到目标状态,这个过程中只有空格向附近的棋格移动,且每次只能移动一次。
如我们给定8数码的初始状态和目标状态分别如图1、2所示。
2
1 0 5 6 8 3 1 8 7 2 0 6 3 4 5 4 7
图1 初始状态 图2 目标状态
则要求以图1为初始状态,通过交换0和0的上、下、左、右四个方位的数字(每次只能和其中一个交换),达到图2所示目标状态。
二、算法说明
根据任务要求,本文采用A*搜索算法。
1. 状态的表示
在A*算法中,需要用到open表和closed表,在open表中,待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中,必须要有能指向下一个扩展节点的指针,以完成对open表中元素的索引。从这一点上看,open表中的元素相互间即构成了一个线性表,因此初步选定使用结构体表示问题的状态。
如图3所示,表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。
图3 结构体
现在进一步考虑DATA中包括的内容:
如图1、2所示,8数码问题的提出是以一个3?3数表表示的,因此本文中采用一个3?3的二维数组s[3][3]表示当前状态的具体信息。
另一方面,A*搜索算法是通过考察节点的代价值来决定open表的排序的,
因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。
根据A*算法的定义,当前节点的代价值由估价函数给出,即:
f(n)?d(n)?h(n)
其中:d(n)表示当前节点n在搜索树中的深度;
h(n)是启发函数。
本例h(n)=p(n)+w(n)
其中:p(n)表示每个将牌与其目标位置之间最短距离的总和; w(n)表示不在位的将牌个数。
因此,在DATA还应包括表示当前节点代价、深度和启发信息的f、d、h。 综上所述,问题状态的表示如下图所示。 Eight:
int s[3][3]; //三行三列数组 char direction; //移动方向 int fn; //fn为dep+h(n) struct Eight *next; //下个节点指针 int dep;
图4 问题的状态表示
2.启发函数的设计
根据A*算法的定义,启发函数应满足:h(n)?h*(n)。
其中:h*(n)表示从当前节点currentchess到目标节点aim的最优路径的实际代价。
并且,在满足h(n)?h*(n)的条件下,h(n)的值越大它所携带的启发性信息越多,A*算法搜索时扩展的节点就越少,搜索效率就越高。
在8数码问题中,常用的启发函数为: “不在位”将牌个数,或数码“不在位”的最短距离和。此程序中我采用数码“不在位”的将牌个数与每个将牌与
其目标位置之间最短距离的总和的和作为启发函数。
3. 程序流程
主程序流程图:
开始
N初始化s_0,把s_0送入open表open表为空?Y失败,退出
把open表的首节点(节点n)从open表移出,放入closed表节点n为目标节点?成功,退出扩展节点n:将有效子节点加入open表,无效子节点删除
其中,扩展节点n的具体步骤如下:
a) 首先判断其是否在open表中带扩展, 如果出现过,则删除该节点;如果没有出现过,则转b。
b) 判断其是否已经存在于closed表中已经出现过,如果出现过,则删除该节点;如果没有出现过,则说明该节点为一个全新的节点,转c。
c) 将该节点加入open表。其中加入open表顺序按f(n)值从小到大排列,并且当f(n)相等时,按深度depth由大到小。
三、重点代码
节点结构体 struct Eight{ public:
int s[3][3]; //三行三列数组 char direction; //移动方向 int fn; //fn为dep+h(n)
struct Eight *next; //下个节点指针 int dep; //节点深度 };
执行类Execute.h方法
void exeEight(Eight *eight); //执行八数码问题
bool arrcmp(int s1[3][3],int s2[3][3]); //复制节点从而生成新节点 bool arrequ(int s1[3][3],int s2[3][3]); //判断两个九宫格内数码位置是否相同
bool Insertopen(Eight *list, Eight *item); //将节点插入open表 bool ifIncludeopen(Eight *list, Eight *item); //判断节点是否已经在open表中
bool ifIncludeclosed(Eight *list, Eight *item); //判断节点是否已经在closed表中
节点类EightPuyzzle.h方法
int final_s[3][3]; //最终状态的八数码 bool setStart(int s[3][3]); //输入初始状态 bool outPut(int s[3][3]); //输出节点状态 int f_w(int s[3][3]); //w(n)函数 int f_p(int s[3][3]); //p(n)函数每个将牌与其目标位置之间最短距离的总和
int f_h(int s[3][3]); //h(n)函数在此等于p(n)+w(n)
int move_up(int s1[3][3],int i,int j,char dir); //上移 int move_down(int s1[3][3],int i,int j,char dir); //下移 int move_left(int s1[3][3],int i,int j,char dir); //左移 int move_right(int s1[3][3],int i,int j,char dir); //右移
bool j_s(int s[3][3]); //判断是否是八数码问题
重点函数代码: (1)A*主函数
void Execute::exeEight(Eight *eight)
正在阅读:
人工智能八数码07-07
作业环境与职业健康 - 图文06-13
关于开展“践行文明干部作表率”主题实践活动的实施方案12-22
《前途与理想》主题班会09-01
最新优秀大学生个人求职漂亮简历封面及内页模板下载 6308-19
错那县代理发表职称论文发表-高中化学电极方程式书写技巧论文选04-07
平行四边形的面积—赛课获奖教案09-30
三宝四口五临边方案03-12
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 人工智能
- 数码
- 二级汽车客运站项目可行性研究报告
- 四年级第一学期数学期末测试卷(答案)
- 轮胎介绍
- 如何发挥新闻舆论监督的作用
- 网络摄像头项目可行性研究报告(目录) - 图文
- Linux集群实施手册V2.0(20130617) - new
- 2015-2016学年安徽省安庆市18校联考九年级(上)期中物理试卷和
- 中国古代文学常识全解
- 2014-2018年中国铝合金市场供需预测与发展前景分析报告
- 地理发言材料
- 影视美学试题汇总
- 某实验楼工程量清单与招标控制价编制
- 福师17春秋学期《物流管理概论》在线作业一
- 护理考试题
- 装饰装修工程工程量清单项目及计算规则
- 外文翻译 - 不平衡报价的平衡
- 学校党风廉政建设及反腐败工作自查报告
- 三年级校运会成绩一览表 - 觅渡教育集团-数字化校园
- 压强课标分析、学情分析、教材分析3
- 北师大版教案Unit_3_Celebration_Lesson_3_Weddings