注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

转 八数码问题A*算法分析  

2011-03-06 16:17:41|  分类: 人工智能 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    一、八数码问题A*问题分析

    1 问题的肢解和攻关

首先,八数码问题包括一个初始状态(START)  目标状态(END),所谓解八数码问题就是在两个状态间寻找一系列可过渡状态(START->STATE1->STATE2->...->END)。这个状态是否存在就是我们要解决的第一个问题。

解决八数码问题,主要面临的问题有:Q1)开始状态S到目标状态D是否可解;Q2)扩展节点的选择;Q3)扩展待扩展节点 Q4)判断是否已达目标节点D

问题Q 1)通过逆序数的奇数偶数来判断。因为在空白移动过程中,数码的逆序数不改变。左右移动,数码序列不变。上下移动,数码序列中某个数字则移动了两位。问题的实质就是:如果是N*N的数码盘的话,左右移动,数码序列不变;上下移动则数码序列变动N-1位。若N为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵,3为奇数,故逆序数不作改变。故可通过判断当前状态S的逆序数以及目标状态SD的数字序列的逆序数的奇偶性是否相同来判断该问题是否可解。

问题Q3)扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去。这里涉及到几个问题:Q5该节点是否已扩展过 Q6扩展是否超过了地图

问题Q4)是否达到目标节点,将当前节点和目标节点进行比较

而在提及八数码问题的几种不同的解法的时候,我们是针对问题Q2提出的不同解法,即不同的扩展新节点的方法:譬如盲目搜索中的宽度优先搜索算法和深度优先搜索算法;譬如启发式搜索的A*算法。

1)     A*算法

A*算法的核心思想参见教材搜索章节,对于A*算法有两大地方可以有不同的选择,Q7)启发函数的选择;Q8OPEN表中取最优的选择

问题Q7)对于f(n)的考虑最简单的便是比较每个状态与目标状态相比错位的牌数。这个启发意味着如果其他条件相同,那么错位的牌数最少的状态可能最接近目标状态。然而这个启发没有使用从棋盘格局中可以得到的所有信息,因为它没有把牌必要的移动距离纳入考虑。一个“更好一点”的启发是对错位的牌必须要移动的距离求和,为了达到这个目的,每张牌必须要移动的每个方格算为一个距离单位。这两种启发都存在一种不足,就是没有认识到点到牌的难度。也就是说,如果两张牌是彼此相邻的,而且目标是要求互相颠倒它们的位置,那么要把它们放到适当的位置需要远不止两次的移动,因为各张牌必须相互绕来绕去。一种把这个问题纳入考虑的启发对每个直接颠倒(两张相邻的牌要满足目标顺序必须交换位置)乘以一个小的数字(比如2。仅仅单独使用上面三种启发的一种显然是不可取的,对于前两种前面已经论述过,对于第三种也很显然,如果一个状态中没有直接颠倒的牌,那么评估函数就是0。所以现在综合上面三种(或者说是后两种)启发,得到第四种启发:把错位牌的距离和与直接颠倒数的二倍相加,这样就克服了单纯颠倒启发的不足。

问题Q8)全局最优:将Open表中的所有节点进行排序选择估价函数f(n)最优的进行扩展。第二种选择就是选择当前层扩展的节点中选择最优的f(n)进行扩展。

2)  小结

       对于八数码问题的解决算法,在上面已经有了不同的讨论,而针对对扩展节点的选择方案上的A*算法,可以有很多种不同的选择,主要取决于f(n)估价函数的选择。


二:八数码之A*算法的实现


1)    数据结构

1.1)现有存储方式 

节点的存储,采用3*3矩阵来实现,而实际上却用不了这么多。而对于矩阵中的每个数字都是不大于8的,对于原本的矩阵,存储空间耗费9int类型的空间,即9*4个字节(80x86处理器),而实际一个int类型即可标识一个类型的状态矩阵。(但不可唯一标识)。

而对于这种数据结构除了节省空间外,在解决八数码问题中的一些操作上也可以节省时间。譬如问题:判断两个状态节点是否相同

现有解决方案:每个状态节点中存储的是一个3*3的矩阵(或大小为9的向量)

For循环判断,两个状态是否相同。

    这种方案的缺点有:

缺点1

实际使用不了这么多的空间,状态节点存储的唯一标识状态的节点是该状态下的矩阵,而对于矩阵中的每个数字都是不大于8的,对于原本的矩阵,存储空间耗费9int类型的空间,而实际一个int类型即可标识一个类型的状态矩阵。(但不可唯一标识)。

缺点2

针对判断两个状态节点中存储的矩阵是否相同,需要for这样的循环语句来进行判断(以及for循环中的if语句等),需要多次进行跳转分支的预测,会降低处理器中流水线的并行性,造成流水阻塞。

综上,无论是在空间消耗上,还是在cpu的执行上都存在着缺陷。

1.2)改进存储方式


  评论这张
 
阅读(718)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017