




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、用a*算法解决八数码问题一、 题目:八数码问题也称为九宫问题。在33的棋盘,有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。二、 问题的搜索形式描述状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。初始状态:任何状态都可以被指定为初始状态。操作符:用来产生4个行动(上下左右移动)。目标测试:用来检测状态是否能匹配上图的目标布局。路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。现在任意给定一
2、个初始状态,要求找到一种搜索策略,用尽可能少的步数得到上图的目标状态算法介绍三、 解决方案介绍1.a*算法的一般介绍a*(a-star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价值,即;这样估价函数f在g值一定的情况下,会或多或少的受估价值h的制约,节点距目标点近,h值小,f值相对就小,能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。a star算法在静态路网中的应用2.算法伪代码创建两个表,open表保存所有已生成而未考察的节点,closed表中记录已访问过的节点。算起点的估价值,将起点放入open表。while(o
3、pen!=null)从open表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当前节点n 的每个子节点x) 算x的估价值;if(x in open) if( x的估价值小于open表的估价值 )把n设置为x的父亲;更新open表中的估价值; /取最小路径的估价值 if(x inclose) if( x的估价值小于close表的估价值 )把n设置为x的父亲;更新close表中的估价值;把x节点放入open /取最小路径的估价值 if(x not inboth)把n设置为x的父亲;求x的估价值;并将x插入open表中; /还没有排序 /end for将n节点插入close表
4、中;按照估价值将open表中的节点排序; /实际上是比较open表内节点f的大小,从最小路径的节点向下进行。/end while(open!=null)保存路径,即 从终点开始,每个节点沿着父节点移动直至起点,这就是你的路径.四、 源程序#include #include #include using namespace std; constint row = 3; constint col = 3; constint maxdistance = 10000; constint maxnum = 10000; int abs(int a) if (a0) return a; else retu
5、rn -a; typedefstruct _node int digitrowcol; intdist; / 距离 intdep; / 深度 int index; / 索引值 node; node src, dest; vectornode_v; / 储存节点boolisemptyofopen() /判断open表是否空 for (inti = 0; inode_v.size(); i+) if (node_vi.dist != maxnum) return false; return true; boolisequal(int index, int digitcol) /判断节点是否与索引值
6、指向的节点相同 for (inti = 0; i row; i+) for (int j = 0; j col; j+) if (node_vindex.digitij != digitij) return false; return true; ostream& operator(ostream&os, node& node) for (inti = 0; i row; i+) for (int j = 0; j col; j+) osnode.digitij ; osendl; returnos; void printsteps(int index, vector&rstep_v)/输出步
7、骤 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; for (inti = rstep_v.size() - 1; i= 0; i-) cout step rstep_v.size() - i endlrstep_vi endl; void swap(int& a, int& b) /交换 int t; t = a; a = b; b = t; void assign(n
8、ode& node, int index) /获取节点 for (inti = 0; i row; i+) for (int j = 0; j col; j+) node.digitij = node_vindex.digitij; intgetminnode() /获取启发值最小的节点 intdist = maxnum; intloc; / the location of minimize node for (inti = 0; inode_v.size(); i+) if (node_vi.dist = maxnum) continue; else if (node_vi.dist + n
9、ode_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; returnloc; boolisexpandable(node& node) /判断是否可扩展 for (inti = 0; inode_v.size(); i+) if (isequal(i, node.digit) return false; return true; int distance(node& node, int digitcol) /计算距离 int distance = 0; bool flag = false; for(inti = 0; i ro
10、w; i+) for (int j = 0; j col; j+) for (int k = 0; k row; k+) for (int l = 0; l col; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance; intmindistance(int a, int b) /二者取小 return (a b ? a : b); void processnode(
11、int index) /展开节点 int x, y; bool flag; for (inti = 0; i row; i+) for (int j = 0; j 0) swap(node_up.digitxy, node_up.digitx - 1y); if (isexpandable(node_up) dist_up = distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_
12、up); node node_down; /下移操作 assign(node_down, index); intdist_down = maxdistance; if (x 0) swap(node_left.digitxy, node_left.digitxy - 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_vindex.dep + 1;
13、 node_v.push_back(node_left); node node_right; /右移操作 assign(node_right, index); intdist_right = maxdistance; if (y 2) swap(node_right.digitxy, node_right.digitxy + 1); if (isexpandable(node_right) dist_right = distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right;
14、node_right.dep = node_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist = maxnum; int main() int number; cout 输入初始状态: endl; for (inti = 0; i row; i+) for (int j = 0; j number;src.digitij = number; src.index = 0; src.dep = 1; cout 输入目标状态 endl; for (int m = 0; m row; m+) for (int n = 0; n number; dest.digitmn = number; node_v.push_back(src); while (1) if (isemptyofopen() cout 找不到解! endl; return -
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/TR 24107:2024 EN Air quality - Validation of air quality measurement methods in the standardization process
- 【正版授权】 ISO 8000-115:2024 EN Data quality - Part 115: Master data: Exchange of quality identifiers: Syntactic,semantic and resolution requirements
- 2025年度地坪工程环保验收服务承包合同样本
- 2025年度汽车贷款担保合同会计处理与风险控制要点
- 2025年度法制副校长履职评价及激励措施合同
- 2025年度老旧城区拆除工程承包合同范本
- 2025感恩广场二期商铺投资合作协议
- 2025年白喉、百日咳、破伤风、乙肝四联制剂项目发展计划
- 文化机构安全隐患排查与防范计划
- 让孩子们爱上数学的活动安排计划
- 建筑材料案例分析
- 2021年新大象版四年级科学下册全册教案(附板书设计、教学反思、总结点评)
- 小班《夏天的服装》
- PI形式发票范文模板
- 城市地理学第二章城乡划分和城市地域
- 中华人民共和国政府信息公开条例解读PPT
- 《陈列展览项目支出预算方案编制规范和预算编制标准试行办法》的通知(财办预〔2017〕56号)
- 《质量手册》培训教材课件
- 2016年输电线路评价与分析报告
- 全名校初二物理期末冲刺30题:力与运动、压强和浮力
- 因公出国(境)管理办法
评论
0/150
提交评论