可夫斯基所创词汇,是种使用在几何度量空间的几何学用语,用以标明两个点上在标准坐标系上的绝对轴距总和。定义曼哈顿距离的正式意义为L1距离或城市区块距离,也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
f例如在平面上,坐标(x1y1)的点P1与坐标(x2y2)的点P2的曼哈顿距离为:x1x2y1y2要注意的是,曼哈顿距离依赖坐标系统的转度,而非系统在坐标轴上的平移或映射。3说明ope
表和close表如何实现:我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。对于树式搜索来说,CLOSED表中存储的正是一棵不断成长的搜索树;采用一个称为OPEN表的动态数据结构,来专门登记当前待考查的节点。(1)采用结构体数组示例typedefstructi
ti
dex结点序号i
tPare
t父结点序号i
tGridSIZESIZE八数码状态i
tH启发式函数值StateStateOPENMAXSIZE存放已经生成的未考察的节点StateCLOSEMAXSIZE存放已经考察过得节点(2)采用链表存储示例structLNodei
ti
dexi
tHi
tGrid9i
tzeropositio
structLNodepare
tstructLNodechild4structLNode
exttypedefstructLHeadi
t
umstructLNodefirstLHeadLi
kList头结点结点序号启发式函数值八数码状态空格的位置指向父节点指向子节点(最多有四个)普通结点存储八数码信息
fLi
kListLope
,Lclose指针
定义指向ope
、close表的
4说明实验中采用的搜索算法:全局择优启发式算法步1把初始节点S0放入OPEN表中,计算hS0;步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以序号
;步4若目标节点SgN,则搜索成功,结束。步5若N不可扩展,则转步2;步6扩展N,计算每个子节点x的函数值hx,并将所有子节点配以指向N的返回指针后放入OPEN表中,再对OPEN表中的所有子节点按其函数值大小以升序排序,转步2。
六实验结果
一代码分析代码分为以下几个模块:主函数初始化函数(初始化棋盘)输出函数(输出打印棋盘,即输出一个状态)状态转换函数(八数码棋盘状态转换)估价函数(利用估价值进行优化搜索)搜索函数(全局择优启发式算法)二实验结果1实验运行结果【例】初始化棋盘:140372685结果:共需要进行六步转换才可以由初始状态成功转换为目标转移具体运行实例如下截图:目标棋盘:012345678
ff2对不可达状态能进行正确识别【例】初始化棋盘:012345678结果:共需要至少进行超过30r